To see the other types of publications on this topic, follow the link: Line graph.
Dissertations / Theses on the topic 'Line graph'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Line graph.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Fausset, Cara Bailey. "On processing line graphs." Thesis, Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24605.
Full text
2
Peternek, Fabian Hans Adolf. "Graph compression using graph grammars." Thesis, University of Edinburgh, 2018. http://hdl.handle.net/1842/31094.
Full textAbstract:
This thesis presents work done on compressed graph representations via hyperedge replacement grammars. It comprises two main parts. Firstly the RePair compression scheme, known for strings and trees, is generalized to graphs using graph grammars. Given an object, the scheme produces a small context-free grammar generating the object (called a “straight-line grammar”). The theoretical foundations of this generalization are presented, followed by a description of a prototype implementation. This implementation is then evaluated on real-world and synthetic graphs. The experiments show that several graphs can be compressed stronger by the new method, than by current state-of-the-art approaches. The second part considers algorithmic questions of straight-line graph grammars. Two algorithms are presented to traverse the graph represented by such a grammar. Both algorithms have advantages and disadvantages: the first one works with any grammar but its runtime per traversal step is dependent on the input grammar. The second algorithm only needs constant time per traversal step, but works for a restricted class of grammars and requires quadratic preprocessing time and space. Finally speed-up algorithms are considered. These are algorithms that can decide specific problems in time depending only on the size of the compressed representation, and might thus be faster than a traditional algorithm would on the decompressed structure. The idea of such algorithms is to reuse computation already done for the rules of the grammar. The possible speed-ups achieved this way is proportional to the compression ratio of the grammar. The main results here are a method to answer “regular path queries”, and to decide whether two grammars generate isomorphic trees.
3
Bergman, Jonas. "Line Graph Utility : A software module for routing." Thesis, Mittuniversitetet, Avdelningen för data- och systemvetenskap, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:miun:diva-26591.
Full textAbstract:
This project was about building a line graph utility, a software module that should read mapdata from a PostGIS database and transform that information into a line graph (edge based graph) that the calling software could use to perform routing decisions. This outer calling application is part of a project (by an anonymized company) for flexible public transportation, that is meant to manage and direct a fleet of vehicles to where the customers actually are, instead of idling at bus stops. The software module should take different kinds of restrictions and conditions into account when building the line graph, to reflect the actual traffic situation.That can be turn restrictions, traffic signs, inclination, or conditions such as temporary hindrances, time of day. Some are static, but others vary dynamically and the state is to befound in the database. This study has found a set of tools that aids in the transformation of OpenStreetMap data into a PostGIS database; for building the topology of the map; querying the database; and data structures for representing the graph and line graph. The result of the project is a piece of working software that can return a line graph as a Boost graph with some restrictions taken into account, but it has not yet implemented the mall, and more specifically, it does not handle conditional restrictions yet. There remains a good deal of work to implement all that complex logic.
4
García, García Grecia. "Improving and assessing students' line graph interpretations : the case of the graph-as-picture interpretation." Thesis, University of Sussex, 2015. http://sro.sussex.ac.uk/id/eprint/53220/.
Full textAbstract:
The “graph-as-picture misconception” (GAPM) occurs when an abstract representation (e.g., a line graph) is interpreted as a picture of an object (e.g., a mountain). Previous research on students' line graph interpretations has focused on secondary school level and above, thus this research extends the investigation of the GAPM to primary school level. Particularly, it investigates: which type of environment is more effective for improving young students' line graph interpretations; and how can be assessed their interpretations. A pilot study involved an improved version of Janvier's (1978) paper-and-pencil tasks (to create an interactive learning environment) and it investigated how to incorporate a card-sort task (to assess students' interpretations). Different touch-screen technologies were considered too. Two experiments were conducted. In experiment one, 37 participants (third to sixth year) were assessed in their graphical knowledge through a picture/diagram card-sort task and a “pictorial group” was formed using participants' interpretations. During the intervention, students performed an active or passive mode of a Racing Car activity in which they moved or watched a car along a track while its speed/distance graph was plotted concurrently alongside. The results suggested that a wide variety of pictorial interpretations exist and students seemed to benefit from the active modality. In experiment two, 38 fifth-year students performed different assessment tests. Extending experiment one, a “drawing the graph” mode and its passive modality were included. In that mode, students modified a plotted line of a speed/distance graph, which was used by the system to race a car along a track. Previous results were not confirmed: only students under the “drawing the graph” modality (including the “pictorial group”) significantly improved their interpretations; and different assessment tests seemed better to observe students' various interpretations. In conclusion, a learning environment that allows interaction with the representation could potentially improve students' interpretations, which might be better assessed through a rich set of tests.
5
Dayson, Gaynor. "Children’s concepts about the slope of a line graph." Thesis, University of British Columbia, 1985. http://hdl.handle.net/2429/25377.
Full textAbstract:
This study is concerned with how children interpret the slope of a line graph. Today with the vast accumulations of data which are available from computers, people are being faced with an ever increasing amount of pictorial representation of this data. Therefore it is of the utmost importance that children understand pictorial representation. Yet in spite of the popularity of graphs as tools of communication, studies show that many adults experience difficulty in reading information presented in a graphical form.
The slope of the graph was chosen for this investigation because it is in this aspect of graphing (as shown by the results of the 1981 B.C. Assessment) that children in British Columbia seem to have the greatest difficulty when they reach Grade 8. The study dealt with positive, negative, zero and infinite slopes, combinations of these slopes, curvilinear graphs and qualitative graphs, that is, graphs that have no numerical data shown on the axes.
The researcher chose to use a structured individual interview as a means of collecting data about how the students interpreted the slope of a line graph. Graphs used in the interviews dealt with temperature, height, weight and distance. Twenty-two students were chosen for this study.
The students were found to have problems mainly with graphs dealing with distance related to time. This problem may be due to the fact that many students read only one axis and when interpreting distance seem to include direction as an added dimension of the graph. Infinite slope graphs were misinterpreted by every student, which may be due to the fact that they ignore the time axis. In general students used two methods of interpreting graphs. In some cases they observed the direction of the graph from left to right, that is, whether the slope went up or down from left to right. In other cases they examined the end points on the graph and drew their conclusions from them. The choice of method varied with the contextual material shown on the graph, which may be due to the children's concept of the parameter in the physical world and whether they see the parameter as being able to increase and decrease over time.
From the study the investigator feels that more discussion of graphing by teachers and students is needed if the misconceptions are to be cleared up. Discussion of the parameters of both axes by teachers might help clear up the misconceptions students have about distance travelled over a period of time when this is expressed as a graph. There would be less chance of a graph being read as a map if the relationships between the two axes were demonstrated to students. Teachers also need to be aware of both methods used by students in interpreting graphs.<br>Education, Faculty of<br>Graduate
6
Sehgal, Nidhi Rodger C. A. "4-cycles systems of line graphs of complete multipartite graphs." Auburn, Ala, 2008. http://repo.lib.auburn.edu/EtdRoot/2008/SUMMER/Mathematics_and_Statistics/Thesis/Sehgal_Nidhi_47.pdf.
Full text
7
MOLINARI, MARIA CHIARA. "Decomposizioni in cicli pari di indice 3 nei line graph 4-regolari." Doctoral thesis, Università degli studi di Modena e Reggio Emilia, 2022. http://hdl.handle.net/11380/1266028.
Full textAbstract:
Una decomposizione in cicli pari (ECD) di un grafo euleriano è una partizione dell'insieme degli spigoli in cicli pari. Coloriamo i cicli pari in modo che i cicli che condividono almeno un vertice ricevano colori distinti.
Se m è il numero minimo di colori richiesti, allora diciamo che la decomposizione in cicli pari ha indice m. La nozione di ECD di indice m è connessa al palette index di un grafo, un parametro cromatico che descrive un grafo a partire dal numero minimo di palette dei suoi vertici.
In particolare, i possibili valori per il palette index di un grafo 4-regolare sono 1, 3, 4 e 5. Il palette index è 3 se e solo se il grafico ha un 2-fattore pari o un ECD di indice 3.
Esistono infinite famiglie di grafi 4-regolari con un ECD di indice 3 .
Per quanto ne sappiamo, non è noto alcun esempio di grafo 4-regolare il cui insieme di spigoli può essere partizionato in cicli pari e ogni ECD ha indice maggiore di 3. Motivati dal problema sull'esistenza di un tale grafo 4-regolare, studiamo ECD in line graph 4-regolari di grafi cubici di classe 2.
Per alcune delle infinite famiglie di grafi cubici di classe 2, caratterizzati da una grande oddness, possiamo trovare un ECD di indice 3 nel line graph corrispondente.<br>An even cycle decomposition (ECD) of an Eulerian graph is a partition of the edge-set into even cycles. We color the even cycles so as two cycles sharing at least one vertex receive distinct colors.
If m is the minimum number of required colors, then we say that the even cycle decomposition has index m. The notion of an ECD of index m is connected to the palette index of a graph, a chromatic parameter describing a graph by the minimum number of palettes of its vertices.
In particular, the possible values for the palette index of a 4-regular graph are 1, 3, 4 and 5. It is 3 if and only if the graph has an even 2-factor or an ECD of index 3.
There exist infinite families of 4-regular graphs with an ECD of index 3 .
As far as we know, no example of 4-regular graph whose edge set can be partitioned into even cycles and every ECDs has index larger than 3 is known. Motivated by the problem on the existence of such a 4-regular graph, we study ECDs in 4-regular line graphs of class 2 cubic graphs. For some of the infinite families of class 2 cubic graphs that are characterized by an arbitrary large oddness, we can find an ECD of index 3 in the corresponding line graph.
8
Yang, Weihua. "Supereulerian graphs, Hamiltonicity of graphes and several extremal problems in graphs." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00877793.
Full textAbstract:
In this thesis, we focus on the following topics: supereulerian graphs, hamiltonian line graphs, fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, and several extremal problems on the (minimum and/or maximum) size of graphs under a given graph property. The thesis includes six chapters. The first one is to introduce definitions and summary the main results of the thesis, and in the last chapter we introduce the furture research of the thesis. The main studies in Chapters 2 - 5 are as follows. In Chapter 2, we explore conditions for a graph to be supereulerian.In Section 1 of Chapter 2, we characterize the graphs with minimum degree at least 2 and matching number at most 3. By using the characterization, we strengthen the result in [93] and we also address a conjecture in the paper.In Section 2 of Chapter 2, we prove that if $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$, then $G$ is collapsible except for several special graphs, where $p(n)=0$ for $n$ even and $p(n)=1$ for $n$ odd. As a corollary, a characterization for graphs satisfying $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$ to be supereulerian is obtained. This result extends the result in [21].In Section 3 of Chapter 2, we focus on a conjecture posed by Chen and Lai [Conjecture~8.6 of [33]] that every 3-edge connected and essentially 6-edge connected graph is collapsible. We find a kind of sufficient conditions for a 3-edge connected graph to be collapsible.In Chapter 3, we mainly consider the hamiltonicity of 3-connected line graphs.In the first section of Chapter 3, we give several conditions for a line graph to be hamiltonian, especially we show that every 3-connected, essentially 11-connected line graph is hamilton- connected which strengthens the result in [91].In the second section of Chapter 3, we show that every 3-connected, essentially 10-connected line graph is hamiltonian-connected.In the third section of Chapter 3, we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is hamiltonian. Moreover, if $G$ has 10 vertices of degree 3 and its line graph is not hamiltonian, then $G$ can be contractible to the Petersen graph.In Chapter 4, we consider edge fault-tolerant hamiltonicity of Cayley graphs generated by transposition trees. We first show that for any $F\subseteq E(Cay(B:S_{n}))$, if $|F|\leq n-3$ and $n\geq4$, then there exists a hamiltonian path in $Cay(B:S_{n})-F$ between every pair of vertices which are in different partite sets. Furthermore, we strengthen the above result in the second section by showing that $Cay(S_n,B)-F$ is bipancyclic if $Cay(S_n,B)$ is not a star graph, $n\geq4$ and $|F|\leq n-3$.In Chapter 5, we consider several extremal problems on the size of graphs.In Section 1 of Chapter 5, we bounds the size of the subgraph induced by $m$ vertices of hypercubes. We show that a subgraph induced by $m$ (denote $m$ by $\sum\limits_{i=0}^ {s}2^{t_i}$, $t_0=[\log_2m]$ and $t_i= [\log_2({m-\sum\limits_{r=0}^{i-1}2 ^{t_r}})]$ for $i\geq1$) vertices of an $n$-cube (hypercube) has at most $\sum\limits_{i=0}^{s}t_i2^{t_i-1} +\sum\limits_{i=0}^{s} i\cdot2^{t_i}$ edges. As its applications, we determine the $m$-extra edge-connectivity of hypercubes for $m\leq2^{[\frac{n}2]}$ and $g$-extra edge-connectivity of the folded hypercube for $g\leq n$.In Section 2 of Chapter 5, we partially study the minimum size of graphs with a given minimum degree and a given edge degree. As an application, we characterize some kinds of minimumrestricted edge connected graphs.In Section 3 of Chapter 5, we consider the minimum size of graphs satisfying Ore-condition.
9
Myers, Richard Oliver. "Genetic algorithms for ambiguous labelling problems." Thesis, University of York, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.310985.
Full text
10
Kumwenda, Khumbo. "Codes, graphs and designs related to iterated line graphs of complete graphs." Thesis, University of the Western Cape, 2011. http://etd.uwc.ac.za/index.php?module=etd&action=viewtitle&id=gen8Srv25Nme4_1742_1320645699.
Full textAbstract:
In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs ôn that are embeddable into the strong product L1(Kn) â K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, ôn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of ôn and Hn and determine their parameters.
11
Keller, Stacy. "LEVELS OF LINE GRAPH QUESTION INTERPRETATION WITH INTERMEDIATE ELEMENTARY STUDENTS OF VARYING SCIENTIFIC AND MATHEMATICAL KNOWLE." Doctoral diss., University of Central Florida, 2008. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/3371.
Full textAbstract:
This study examined how intermediate elementary students' mathematics and science background knowledge affected their interpretation of line graphs and how their interpretations were affected by graph question levels. A purposive sample of 14 6th-grade students engaged in think aloud interviews (Ericsson & Simon, 1993) while completing an excerpted Test of Graphing in Science (TOGS) (McKenzie & Padilla, 1986). Hand gestures were video recorded. Student performance on the TOGS was assessed using an assessment rubric created from previously cited factors affecting students' graphing ability. Factors were categorized using Bertin's (1983) three graph question levels. The assessment rubric was validated by Padilla and a veteran mathematics and science teacher. Observational notes were also collected. Data were analyzed using Roth and Bowen's semiotic process of reading graphs (2001). Key findings from this analysis included differences in the use of heuristics, self-generated questions, science knowledge, and self-motivation. Students with higher prior achievement used a greater number and variety of heuristics and more often chose appropriate heuristics. They also monitored their understanding of the question and the adequacy of their strategy and answer by asking themselves questions. Most used their science knowledge spontaneously to check their understanding of the question and the adequacy of their answers. Students with lower and moderate prior achievement favored one heuristic even when it was not useful for answering the question and rarely asked their own questions. In some cases, if students with lower prior achievement had thought about their answers in the context of their science knowledge, they would have been able to recognize their errors. One student with lower prior achievement motivated herself when she thought the questions were too difficult. In addition, students answered the TOGS in one of three ways: as if they were mathematics word problems, science data to be analyzed, or they were confused and had to guess. A second set of findings corroborated how science background knowledge affected graph interpretation: correct science knowledge supported students' reasoning, but it was not necessary to answer any question correctly; correct science knowledge could not compensate for incomplete mathematics knowledge; and incorrect science knowledge often distracted students when they tried to use it while answering a question. Finally, using Roth and Bowen's (2001) two-stage semiotic model of reading graphs, representative vignettes showed emerging patterns from the study. This study added to our understanding of the role of science content knowledge during line graph interpretation, highlighted the importance of heuristics and mathematics procedural knowledge, and documented the importance of perception attentions, motivation, and students' self-generated questions. Recommendations were made for future research in line graph interpretation in mathematics and science education and for improving instruction in this area.<br>Ed.D.<br>Department of Educational Studies<br>Education<br>Curriculum and Instruction EdD
12
McClain, Christopher. "Edge colorings of graphs and multigraphs." Columbus, Ohio : Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1211904033.
Full text
13
Davison, Benjamin Kenneth. "Universal graph literacy: understanding how blind and low vision students can satisfy the common core standards with accessible auditory graphs." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/47621.
Full textAbstract:
Auditory graphs and active point estimation provide an inexpensive, accessible alternative for low vision and blind K-12 students using number lines and coordinate graphs. In the first phase of this research program, a series of four psychophysics studies demonstrated an interactive auditory number line that enables blind, low vision, and sighted people to find small targets with a laptop, headphones, and a mouse or a keyboard. The Fitts' Law studies showed that, given appropriate auditory feedback, blind people can use a mouse. In addition, auditory feedback can generate target response patterns similar to when people use visual feedback. Phase two introduced SQUARE, a novel method for building accessible alternatives to existing education technologies. The standards-driven and teacher-directed approach generated 17 graphing standards for sixth grade mathematics, all of which emphasized point estimation. It also showed that how only few basic behavioral components are necessary for these graphing problems. The third phase evaluated active point estimation tools in terms of training, classroom situations, and a testing situation. This work shows that students can learn to graph in K-12 environments, regardless of their visual impairment. It also provides several technologies used for graphing, and methods to further develop education accessibility research.
14
Keller, Stacy Kathryn. "Levels of line graph question interpretation with intermediate elementary students of varying scientific and mathematical knowledge and ability a think aloud study /." Orlando, Fla. : University of Central Florida, 2008. http://purl.fcla.edu/fcla/etd/CFE0002356.
Full text
15
He, Weihua. "Cycles in graphs and arc colorings in digraphs." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112352.
Full textAbstract:
Dans cette thèse nous étudions quatre problèmes de théorie des graphes. En particulier,Nous étudions le problème du cycle hamiltonien dans les line graphes, et aussi nous prouvons l’existence de cycles hamiltoniens dans certains sous graphes couvrants d’un line graphe. Notre résultat principal est: Si L(G) est hamiltonien, alors SL(G) est hamiltonien. Grâce à ce résultat nous proposons une conjecture équivalente à des conjectures célèbres. Et nous obtenons deux résultats sur les cycles hamiltoniens disjoints dans les line graphes.Nous considérons alors la bipancyclicité résistante aux pannes des graphes de Cayley engendrés par transposition d’arbres. Nous prouvons que de tels graphes de Cayley excepté le “star graph” ont une bipancyclicité (n − 3)-arête résistante aux pannes.Ensuite nous introduisons la coloration des arcs d’un digraphe sommet distinguant. Nous étudions la relation entre cette notion et la coloration d’arêtes sommet distinguant dans les graphes non orientés. Nous obtenons quelques résultats sur le nombre arc chromatique des graphes orientés (semi-)sommet-distinguant et proposons une conjecture sur ce paramètre. Pour vérifier cette conjecture nous étudions la coloration des arcs d’un digraphe sommet distinguant des graphes orientés réguliers.Finalement nous introduisons la coloration acyclique des arcs d’un graphe orienté. Nous calculons le nombre chromatique acyclique des arcs de quelques familles de graphes orientés et proposons une conjecture sur ce paramètre. Nous considérons les graphes orientés de grande maille et utilisons le Lemme Local de Lovász; d’autre part nous considérons les graphes orientés réguliers aléatoires. Nous prouvons que ces deux classes de graphes vérifient la conjecture<br>In this thesis, we study four problems in graph theory, the Hamiltonian cycle problem in line graphs, the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees, the vertex-distinguishing arc colorings in digraph- s and the acyclic arc coloring in digraphs. The first two problems are the classic problem on the cycles in graphs. And the other two arc coloring problems are related to the modern graph theory, in which we use some probabilistic methods. In particular,We first study the Hamiltonian cycle problem in line graphs and find the Hamiltonian cycles in some spanning subgraphs of line graphs SL(G). We prove that: if L(G) is Hamiltonian, then SL(G) is Hamiltonian. Due to this, we propose a conjecture, which is equivalent to some well-known conjectures. And we get two results about the edge-disjoint Hamiltonian cycles in line graphs.Then, we consider the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees. And we prove that the Cayley graph generated by transposition tree is (n − 3)-edge-fault-tolerant bipancyclic if it is not a star graph.Later, we introduce the vertex-distinguishing arc coloring in digraphs. We study the relationship between the vertex-distinguishing edge coloring in undirected graphs and the vertex-distinguishing arc coloring in digraphs. And we get some results on the (semi-) vertex-distinguishing arc chromatic number for digraphs and also propose a conjecture about it. To verify the conjecture we study the vertex-distinguishing arc coloring for regular digraphs.Finally, we introduce the acyclic arc coloring in digraphs. We calculate the acyclic arc chromatic number for some digraph families and propose a conjecture on the acyclic arc chromatic number. Then we consider the digraphs with high girth by using the Lovász Local Lemma and we also consider the random regular digraphs. And the results of the digraphs with high girth and the random regular digraphs verify the conjecture
16
Matar, Mona. "Node and Edge Importance in Networks via the Matrix Exponential." Kent State University / OhioLINK, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=kent1564590682534316.
Full text
17
Plessas, Demitri Joel. "Topos-like properties in two categories of graphs and graph-like features in an abstract category." CONNECT TO THIS TITLE ONLINE, 2008. http://etd.lib.umt.edu/theses/available/etd-05292008-131250/.
Full text
18
Antony, Albin. "Fault tree analysis for automotive pressure sensor assembly lines." Diss., Online access via UMI:, 2006.
Find full textAbstract:
Thesis (M.S.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Systems Science and Industrial Engineering Department, 2006.<br>Includes bibliographical references.
19
Ehounou, Joseph. "Algorithmes de graphes pour la découverte de la topologie d'un réseau énergétique par la connaissance de ses flots." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLV056/document.
Full textAbstract:
Dans les réseaux énergétiques, la connaissance des équipements, leurs emplacements et leursfonctions sont les prérequis à l’exploitation de l’infrastucture. En effet, tout opérateur disposed’une carte appelée schéma synoptique indiquant les connexions entre les équipements. À partirde cette carte, sont prises des décisions pour un fonctionnement optimal du réseau.Ce schéma synoptique peut être érronné parce que des opérations de maintenance sur le réseaun’auraient pas été retranscrites ou mal saisies. Et cela peut entrainer des coûts supplémentairesd’exploitation du réseau énergetique.Nous considérons le réseau électrique d’un Datacenter. Ce réseau est composé d’une topologiephysique modélisée par un DAG sans circuit et de mesures électriques sur ces arcs. La particularitéde ce réseau est que les mesures contiennent des erreurs et cette topologie est inconnue c’est-à-direles arcs sont connus mais les extrémités des arcs sont inconnues. Dans le cas où ces mesuressont correctes alors la corrélation des arcs induit la matrice d’adjacence du line-graphe du graphenon-orienté sous-jacent de notre DAG. Un line-graphe est un graphe dans lequel chaque sommet etson voisinage peuvent être partitionnés par une ou deux cliques et que chaque arête est couvertepar une clique. Cependant, avec la présence des erreurs de mesures, nous avons un graphe avecdes arêtes en plus ou en moins qui n’est pas nécessairement un line-graphe. Si ce graphe est unline-graphe alors il n’est pas le line-graphe de notre DAG. Notre problème est de découvrir cettetopologie en se basant sur ces mesures électriques.Nous débutons par une étude bibliographique des corrélations de mesures possibles afin dedéterminer celle qui est pertinente pour notre problème. Ensuite nous proposons deux algorithmespour résoudre ce problème. Le premier algorithme est l’algorithme de couverture et il déterminel’ensemble des cliques qui couvre chaque sommet de notre graphe. Le second algorithme estl’algorithme de correction. Il ajoute ou supprime des arêtes au voisinage d’un sommet non couvertde telle sorte que son voisinage soit partitionné en une ou deux cliques. Enfin, nous évaluons lesperformances de nos algorithmes en vérifiant le nombre d’arêtes corrigées et la capacité à retournerle graphe le plus proche du line-graphe de notre DAG<br>In energy network, the knowledge of equipments, their locations and their functions are theimportant information for the distributor service operator. In fact, each operator has a networkplan often named synoptic schema. That schema shows the interconnexion between equipments inthe network. From this schema, some management decisions have taken for ensuring an optimalperformance of a network.Sometimes, a synoptic schema has some mistakes because the maintenance operations, such aschanged the connexion between equipments or replaced equipments, have not been updated orhave been written with errors. And these mistakes increase exploitation cost in the energy network.We consider an electric network of a datacenter. This network consists of physical topologymodelised by a DAG without circuit and measurements are on the edges of a DAG. The mainpoint of the network is that measurements are some mistakes and the topology is unknown i.ewe know edges but the nodes of edges are unknown. When measurements are correct then thecorrelations between pairwise edges provide the adjacency matrix of the linegraph of undirectedgraph of the DAG. A linegraph is a graph in which each node and the neighbor are partitionnedby one or deux cliques. However, with the mistakes in measurements, the obtained graph is nota linegraph because it contains more or less edges. If the obtained graph is a linegraph then it isa linegraph of the other DAG. Our problem is to discovery the topology of the DAG with somemistakes in measurements.We start by the state of art in the measurement correlations in order to choose the good methodfor our problem. Then, we propose two algorithms to resolve our problem. The first algorithmis the cover algorithm and it returns the set of cliques in the graph. The second algorithm is acorrection algorithm which adds or deletes edges in the graph for getting a nearest linegraph ofthe DAG. In the last, we evaluate the performances of the algorithms by checking the number ofedges corrected and the ability to return a nearest linegraph of the DAG
20
Heinz, Adrian. "Algorithms and software systems for learning and research." CardinalScholar 1.0, 2009. http://liblink.bsu.edu/uhtbin/catkey/1536758.
Full textAbstract:
Software systems have experienced an impressive growth in the last few decades
and have impacted a wide variety of areas. In this respect, two elds bene t greatly.
Learning and research. In this work, we present several software systems that we
have created to assist in the process of learning and to help researchers by performing
complex computations and generating data. We demonstrate three web-based educational
video games that we developed to teach science to middle school students. We
also describe several software systems that we created for research in graph theory and
model checking. Finally, we discuss our results, contributions and future directions.<br>Educational perspectives -- Graph algorithms and their applications -- E-learning -- Model checking.<br>Educational perspectives -- Graph algorithms and their applications -- E-learning -- Model checking.<br>Department of Computer Science
21
Wu, Yinghui. "Extending graph homomorphism and simulation for real life graph matching." Thesis, University of Edinburgh, 2011. http://hdl.handle.net/1842/5022.
Full textAbstract:
Among the vital problems in a variety of emerging applications is the graph matching problem, which is to determine whether two graphs are similar, and if so, find all the valid matches in one graph for the other, based on specified metrics. Traditional graph matching approaches are mostly based on graph homomorphism and isomorphism, falling short of capturing both structural and semantic similarity in real life applications. Moreover, it is preferable while difficult to find all matches with high accuracy over complex graphs. Worse still, the graph structures in real life applications constantly bear modifications. In response to these challenges, this thesis presents a series of approaches for ef?ciently solving graph matching problems, over both static and dynamic real life graphs. Firstly, the thesis extends graph homomorphism and subgraph isomorphism, respectively, by mapping edges from one graph to paths in another, and by measuring the semantic similarity of nodes. The graph similarity is then measured by the metrics based on these extensions. Several optimization problems for graph matching based on the new metrics are studied, with approximation algorithms having provable guarantees on match quality developed. Secondly, although being extended in the above work, graph matching is defined in terms of functions, which cannot capture more meaningful matches and is usually hard to compute. In response to this, the thesis proposes a class of graph patterns, in which an edge denotes the connectivity in a data graph within a predefined number of hops. In addition, the thesis defines graph pattern matching based on a notion of bounded simulation relation, an extension of graph simulation. With this revision, graph pattern matching is in cubic-time by providing such an algorithm, rather than intractable. Thirdly, real life graphs often bear multiple edge types. In response to this, the thesis further extends and generalizes the proposed revisions of graph simulation to a more powerful case: a novel set of reachability queries and graph pattern queries, constrained by a subclass of regular path expressions. Several fundamental problems of the queries are studied: containment, equivalence and minimization. The enriched reachability query does not increase the complexity of the above problems, shown by the corresponding algorithms. Moreover, graph pattern queries can be evaluated in cubic time, where two such algorithms are proposed. Finally, real life graphs are frequently updated with small changes. The thesis investigates incremental algorithms for graph pattern matching defined in terms of graph simulation, bounded simulation and subgraph isomorphism. Besides studying the results on the complexity bounds, the thesis provides the experimental study verifying that these incremental algorithms significantly outperform their batch counterparts in response to small changes, using real-life data and synthetic data.
22
Brenas, Jon Haël. "Hoare-like verification of graph transformation." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAM066/document.
Full textAbstract:
En informatique comme dans de multiples autres domaines, les graphes peuvent être trouvés partout. Ils sont utilisés pour représenter des données dans des domaines allant de la chimie à l'architecture, en tant que structures abstraites ou que modèles des données et de leurs évolutions. Dans tous ces domaines, il est prévisible que les graphes évoluent au cours du temps suite à des réactions chimiques, une mise à jour des connaissance ou l'exécution d'un programme. Être capable de traiter ces transformations est une tâche particulièrement importante et difficile. Dans ce travail, notre objectif est d'étudier la vérification de telles transformations de graphes, c'est à dire comment prouver qu'une transformation de graphes est correcte. La correction d'une transformation est plus précisément définie comme la correction d'une spécification pour cette transformation contenant en plus une précondition et une postcondition. Nous avons décidé d'utiliser un calcul à la Hoare générant une plus faible précondition pour une postcondition et une transformation. Si cette plus faible précondition est impliquée par la précondition, la spécification est correcte. Nous avons choisi une approche plus algorithmique pour les transformation de graphes utilisant des actions atomiques. Nous définissons deux moyens de construire des transformations de graphes: en utilisant un langage impératif ou en utilisant des systèmes de règles de réécriture. Le principal ingrédient est la logique qui est choisie pour représenter la précondition, la postcondition et les possibles conditions internes. Pour que la logique puisse interagir avec le calcul, nous demandons que le problème de décision soit décidable, qu'elle soit fermée par substitutions et qu'elle soit capable d'exprimer l'existence ou l'absence d'un sous-graphe affecté par la transformation. Le résultat central de ce travail est l'identification et l'explication de ces conditions<br>In computer science as well as multiple other fields, graphs have become ubiquitous. They are used to represent data in domains ranging from chemistry to architecture, as abstract structures or as models of the data or its evolution. In all these domains, graphs are expected to evolve over time due to chemical reactions, update of the knowledge or programs. Being able to deal with such transformations is an extremely important and difficult task. In this work, our aim is to study the verification of such graph transformation, that is how to prove that a graph transformation is correct. Correctness of a graph transformation is more precisely defines as correctness of a specification for the transformation containing additionally a precondition and a postcondition. We decided to use a Hoare-like calculus generating the weakest precondition for a postcondition and a transformation. If this weakest precondition is implied by the actual precondition, the specification is correct. We chose a more algorithmic approach to graph transformation by using atomic actions.We chose to define two ways to build graph transformations: using an imperative programming language and using rule-base rewriting systems. The main ingredient of the verification of graph transformation is the logic that is chosen to represent the precondition, the postcondition and the possible conditions internal to the transformation. So that the logic can interact with the calculus, we require that the decision problem be decidable, that the logic be closed under the substitutions introduced by the Hoare-like calculus and that it has to be able to express the existence and absence of a match for the transformation. The core result of this work is the identification and explanation of these conditions
23
Lindgren, Sebastian. "A Mobile Graph-Like Visual Programming Language." Thesis, Mälardalens högskola, Akademin för innovation, design och teknik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-36249.
Full textAbstract:
Visual programming is a programming paradigm commonly used for game scripting, it also has applications in other areas such as for example patcher languages for music and animation and even a few languages for general purpose programming. By using visual programming complex tasks can be made easier by abstracting the code and letting the user express a flow of commands instead. This also gives a better overview of the problem and how the different parts connect. By graphically connecting nodes the program flow will be made clear even for those new to programming. Unfortunately, visual programming is mostly limited to laptops and stationary computer systems. Touch enabled mobile devices which perhaps would be even better suited for a visual programming approach are left with textual programming environments, which doesn’t use the capabilities of the touch screen, and a few non-graph-like visual programming languages, which use interlocked blocks to represent code. To explore how well graph-like visual programming would work on mobile devices a study will be conducted in which a lo-fi design is created and iteratively evaluated and improved using a modified NEVO process. The design will be created and improved based on existing visual programming interfaces and research in the area of visual programming, interaction design and information design, combined with the input from the test subjects. In this work a mobile, visual, graph-like, general purpose programming language has been designed. A lo-fi prototype of the language has been created to display how the language would look on a mobile system if realized. The lo-fi prototype was then tested with a method given by Rettig to give an indication of the systems usability measured by its task completion time compared to the task completion time of a mobile textual system. There is also a qualitative analysis on the responses from the test users. The tests were conducted both on people new to programming as well as people who have been programming for a while.
24
Fish, Jocelyn M. "Small cycle double covers and line graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ38584.pdf.
Full text
25
Haubold, Niko. "Compressed Decision Problems in Groups." Doctoral thesis, Universitätsbibliothek Leipzig, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-85413.
Full textAbstract:
Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen.
Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \'komprimiertes Wortproblem\' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist.
Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist.
Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt.
Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt.
Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.
26
Awang, Jennifer S. "Dots and lines : geometric semigroup theory and finite presentability." Thesis, University of St Andrews, 2015. http://hdl.handle.net/10023/6923.
Full textAbstract:
Geometric semigroup theory means different things to different people, but it is agreed that it involves associating a geometric structure to a semigroup and deducing properties of the semigroup based on that structure. One such property is finite presentability. In geometric group theory, the geometric structure of choice is the Cayley graph of the group. It is known that in group theory finite presentability is an invariant under quasi-isometry of Cayley graphs. We choose to associate a metric space to a semigroup based on a Cayley graph of that semigroup. This metric space is constructed by removing directions, multiple edges and loops from the Cayley graph. We call this a skeleton of the semigroup. We show that finite presentability of certain types of direct products, completely (0-)simple, and Clifford semigroups is preserved under isomorphism of skeletons. A major tool employed in this is the Švarc-Milnor Lemma. We present an example that shows that in general, finite presentability is not an invariant property under isomorphism of skeletons of semigroups, and in fact is not an invariant property under quasi-isometry of Cayley graphs for semigroups. We give several skeletons and describe fully the semigroups that can be associated to these.
27
Vasquez, Maria Rosario. "An investigation of super line graphs of hypercubes." Virtual Press, 1993. http://liblink.bsu.edu/uhtbin/catkey/865951.
Full textAbstract:
Graphs, as mathematical objects, play a dominant role in the study of network modeling, VLSI design, data structures, parallel computation, process scheduling and in a variety of other areas of computer science. Hypercubes are one of the preferred architectures for parallel computation, and a study of some properties of the hypercubes motivated this thesis.The concept of super line graphs, introduced by Bagga at el, generalizes the notion of line graphs. In this thesis several graph theoretic properties of super line graphs of hypercubes are studied. In particular the super line graphs of index two of hypercubes are investigated and some exact results and precise characterizations are found.<br>Department of Computer Science
28
Naveed, Ahmed Azam. "On Enumeration of Tree-Like Graphs and Pairwise Compatibility Graphs." Doctoral thesis, Kyoto University, 2021. http://hdl.handle.net/2433/263783.
Full text
29
Spritzer, Andre Suslik. "Supporting the design of custom static node-ling graph visualization." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2015. http://hdl.handle.net/10183/122650.
Full textAbstract:
Visualizações de grafos para comunicação aparecem numa variedade de contextos que vão do acadêmico-científico até o jornalístico e até mesmo artístico. Diferente de visualizações de grafos para exploração e análise de dados, essas imagens são usadas para “contar uma história” que já se conhece ao invés da “procura de uma nova história” nos dados. Apesar de ser possível usar software para desenho de grafos e edição de diagramas para produzí-las, visualizações feitas dessa forma nem sempre preenchem os requisitos visuais impostos pelos seus contextos de uso. Programas de edição de imagens podem ser usados para fazer as melhorias necessárias, mas nem todas as modificações são possíveis e o processo de editar essas imagens pode exigir muito tempo e esforço. Neste trabalho, apresentamos uma investigação de visualizações nodo-aresta estáticas para comunicação e de como facilitar sua criação. A partir de uma desconstrução dessas imagens, identificando seus elementos essenciais, e analisando como são criadas, derivamos um conjunto de requisitos que ferramentas para a criação dessas visualizações devem preencher. Para verificar o efeito da metodologia na melhora do fluxo de trabalho de designers, com mais poder e flexibilidade, foi concebido e implementado um protótipo chamado GraphCoiffure. Com um foco especial em auxiliar usuários na criação de visualizações para publicação, Graph- Coiffure foi projetado como uma aplicação standalone que seria usada como um passo intermediário entre programas de desenho e edição de grafos e editores gráficos. Ele combina ferramentas para manipulação interativa de layouts com estilização similar a CSS para permitir que usuários criem e editem visualizações nodo-aresta estáticas. Ilustramos o funcionamento de GraphCoiffure com quatro casos de uso: a adaptação do layout de uma visualização para fazê-la funcionar em uma dada página, a reprodução do estilo de uma visualização e sua aplicação em outro grafo, e a criação integral de duas novas visualizações. Para obter feedback sobre GraphCoiffure, conduzimos uma avaliação informal através de entrevistas com três potenciais usuários, que disseram achar que GraphCoiffure beneficiaria seu trabalho.<br>Graph visualizations for communication appear in a variety of contexts that range from scientific/ academic to journalistic and even artistic. Unlike graph visualizations for exploration and analysis, these images are used to tell a story that is already known rather than to look for a story within the data. Although graph drawing and diagram editing software can be used to produce them, visualizations made this way do not always meet the visual requirements imposed by their context of use. Graphics authoring software can be used to make the necessary improvements, but not all modifications are possible and the process of editing these images may be very time-consuming and labor-intensive. In this work, we present an investigation of static node-link visualizations for communication and how to better support their creation. We began with a deconstruction of these images, breaking them down into their basic elements and analyzing how they are created. From this, we derived a set of requirements that tools aimed at supporting their creation should meet. To verify if taking all of this into account would improve the workflow and bring more flexibility and power to the users, we created our own prototype, which we named GraphCoiffure. With a special emphasis on helping users on creating visualizations for publication, GraphCoiffure was designed as a standalone application that would serve as an intermediary step between graph drawing and editing software and graphics editors. It combines interactive graph layout manipulation tools with CSS-like styling possibilities to let users create and edit static node-link visualizations for communication. We illustrate the use of GraphCoiffure with four use-case scenarios: the adaptation of a visualization’s layout to make it work on a given page, the reproduction of a visualization’s style and its application on another graph, and the creation of two visualizations from scratch. To obtain feedback on GraphCoiffure, we conducted an informal evaluation by interviewing three potential expert users, who found that it could be useful for their work.
30
Nguyen, Huu-Hiep. "Social Graph Anonymization." Thesis, Université de Lorraine, 2016. http://www.theses.fr/2016LORR0168/document.
Full textAbstract:
La vie privée est une préoccupation des utilisateurs des réseaux sociaux. Les réseaux sociaux sont une source de données précieuses pour des analyses scientifiques ou commerciales. Cette thèse aborde trois problèmes de confidentialité des réseaux sociaux: l'anonymisation de graphes sociaux, la détection de communautés privées et l'échange de liens privés. Nous abordons le problème d'anonymisation de graphes via la sémantique de l'incertitude et l'intimité différentielle. Pour la première, nous proposons un modèle général appelé Uncertain Adjacency Matrix (UAM) qui préserve dans le graphe anonymisé les degrés des nœuds du graphe non-anonymisé. Nous analysons deux schémas proposés récemment et montrons leur adaptation dans notre modèle. Nous aussi présentons notre approche dite MaxVar. Pour la technique d'intimité différentielle, le problème devient difficile en raison de l'énorme espace des graphes anonymisés possibles. Un grand nombre de systèmes existants ne permettent pas de relâcher le budget contrôlant la vie privée, ni de déterminer sa borne supérieure. Dans notre approche nous pouvons calculer cette borne. Nous introduisons le nouveau schéma Top-m-Filter de complexité linéaire et améliorons la technique récente EdgeFlip. L'évaluation de ces algorithmes sur une large gamme de graphes donne un panorama de l'état de l'art. Nous présentons le problème original de la détection de la communauté dans le cadre de l'intimité différentielle. Nous analysons les défis majeurs du problème et nous proposons quelques approches pour les aborder sous deux angles: par perturbation d'entrée (schéma LouvainDP) et par perturbation d'algorithme (schéma ModDivisive)<br>Privacy is a serious concern of users in daily usage of social networks. Social networks are a valuable data source for large-scale studies on social organization and evolution and are usually published in anonymized forms. This thesis addresses three privacy problems of social networks: graph anonymization, private community detection and private link exchange. First, we tackle the problem of graph anonymization via uncertainty semantics and differential privacy. As for uncertainty semantics, we propose a general obfuscation model called Uncertain Adjacency Matrix (UAM) that keep expected node degrees equal to those in the unanonymized graph. We analyze two recently proposed schemes and show their fitting into the model. We also present our scheme Maximum Variance (MaxVar) to fill the gap between them. Using differential privacy, the problem is very challenging because of the huge output space of noisy graphs. A large body of existing schemes on differentially private release of graphs are not consistent with increasing privacy budgets as well as do not clarify the upper bounds of privacy budgets. In this thesis, such a bound is provided. We introduce the new linear scheme Top-m-Filter (TmF) and improve the existing technique EdgeFlip. Thorough comparative evaluation on a wide range of graphs provides a panorama of the state-of-the-art's performance as well as validates our proposed schemes. Second, we present the problem of community detection under differential privacy. We analyze the major challenges behind the problem and propose several schemes to tackle them from two perspectives: input perturbation (LouvainDP) and algorithm perturbation (ModDivisive)
31
Tawfik, Israa. "Links and graphs." Thesis, University of Plymouth, 2013. http://hdl.handle.net/10026.1/2863.
Full textAbstract:
In this thesis we derive some basic properties of graphs G embedded in a surface determining a link diagram D(G), having a specified number μ(D(G)) of components. ( The relationship between the graph and the link diagram comes from the tangle which replaces each edge of the graph). Firstly, we prove that μ (D(G)) ≤ f (G) + 2g, where f (G) is the number of faces in the embedding of G and g is the genus of the surface. Then we focus on the extremal case, where μ (D(G)) = f (G) + 2g. We note that μ (D(G)) does not change when undergoing graph Reidemeister moves or embedded ∆ ↔ Y exchanges. It is also useful that μ(D(G)) changes only very slightly when an edge is added to the graph. We finish with some observations on other possible values of μ(D(G)). We comment on two cases: when μ = 1, and the Petersen and Heawood families of graphs. These two families are obtained from K6 and K7 respectively by using ∆ ↔ Y exchanges.
32
Ma, Fei, and feim@csem flinders edu au. "Registration of mass-like objects in sequential mammograms using graph matching." Flinders University. School of Computer Science, Engineering & Mathematics, 2008. http://catalogue.flinders.edu.au./local/adt/public/adt-SFU20090323.155040.
Full textAbstract:
Sequential mammograms contain important information, such as changes of the breast or developments of the masses, for diagnosis of disease. Comparison of sequential mammograms plays an important part for radiologists in identifying malignant masses. However, currently computer-aided detection (CAD) programs can not use such information eciently. The diculties lie in the registration of sequential mammograms.
Most of current methods register sequential mammograms based on control points and image transformations. For these methods to work, extraction and correspondence of the control points is essential. This thesis presents a new approach in registering mammograms. The proposed method registers mammograms by associating mass-like objects in sequential mammograms directly. The mass-like objects appear in the images of normal breasts as well as images of breast with cancer. When the mass-like objects in sequential mammograms are accurately associated, measurements of changes in mass-like objects over time become possible.
This is an important way to distinguish mass-like objects associated with cancer from cysts or other benign objects.
The proposed method is based on graph matching. It uses the internal structure of the breast represented by the spatial relation between the mass-like objects to establish a correspondence between the sequential mammograms. In this method, the mammogram is firstly segmented into separate components using an adaptive pyramid (AP) segmentation algorithm. A series of filters, based on the features of components, is then applied to the components to remove the undesired ones. The remaining components, the mass-like objects, are represented by a complete graph. The spatial relations between the remaining mass-like objects are expressed by fuzzy spatial relation representation and are associated to the edges of the graph as weights. Association of the mass-like objects of two sequential mammograms is realized by finding a common subgraph of the corresponding two graphs using the backtrack algorithm.
The segmentation methods developed in the course of this work were tested on a separate problem in computer-aided detection of breast cancer, namely the automatic extraction of the pectoral muscle.
The graph matching method was tested independently of the segmentation method on artificially distorted mammograms and the full process, including the segmentation and the graph matching, was evaluated on 95 temporal mammogram pairs. The present implementation indicates only a small improvement in cancer detection rates but also presents opportunities for a substantial development of the basic method in the future.
33
Rahmani, Ahmed. "Etude structurelle des systèmes linéaires par l'approche Bond Graph." Lille 1, 1993. http://www.theses.fr/1993LIL10155.
Full text
34
Mouhri, Abderrahim. "Etude structurelle des systèmes généralisés par l'approche bond graph." Lille 1, 2000. http://www.theses.fr/2000LIL10208.
Full textAbstract:
Ce travail concerne l'etude des systemes lineaires generalises par l'approche bond graph. La modelisation de ces systemes avec choix particulier des vecteurs d'etat ne permet pas de les considerer comme des systemes reguliers surtout lorsqu'ils presentent des impulsions a l'instant initial et a tout instant ulterieur lorsque l'entree n'est pas suffisamment derivable. Une modelisation de ces systemes par bond graph est proposee. Ensuite, une interpretation graphique des elements de chaque matrice composant le modele d'etat generalise est donnee en terme de chemins causaux et de leur gain. Le calcul formel des coefficients du polynome caracteristique generalise a partir du modele bond graph comportant certains elements en causalite derivee, est donne. Ces coefficients peuvent etre ensuite a la base d'une methode de placement de poles formel par retour d'etat statique a partir du modele bond graph. La determination de la matrice de transfert est terminee par le calcul formel des differents numerateurs de cette matrice directement sur le modele bond graph. Le rang bond graph est une propriete interessante dans l'analyse structurelle par l'approche bond graph. Son calcul pour les systemes lineaires generalises est apparu alors comme une extension du resultat enonce pour les systemes reguliers modelises par bond graph. Pour la commandabilite en etat et l'observabilite structurelles, nous avons propose des procedures graphiques permettant de verifier la r- commandabilite et la r- observabilite du systeme generalise associe au modele bond graph<br>Nous avons egalement interprete graphiquement des criteres algebriques associes au sous systeme rapide dans la forme de rosenbrock du systeme generalise initial. La caracteristique principale d'un systeme generalise est ses modes impulsionnels s'ils existent. La modelisation des systemes generalises par bond graph ne permet pas de les faire apparaitre d'un point de vue structurel mais ceci est possible d'un point de vue formel. Une procedure graphique permettant de determiner formellement le nombre de modes impulsionnels que le systeme generalise peut exhiber a ete proposee. La modelisation par bond graph des systemes a commutation a permis de caracteriser leur modes impulsionnels. Nous avons interprete le nombre de ces modes a l'aide des chemins causaux apparus apres commutation entre element commutant et element i ou c statiquement dependant. Aussi, nous avons propose une interpretation graphique basee sur la notion de chemins causaux et de rang bond graph pour l'etude de la i- commandabilite et de la i- observabilite du systeme a commutation modelise par bond graph
35
Lichiardopol, Anca-Maria. "L’approche Bond Graph pour la découverte technologique." Ecole Centrale de Lille, 2007. http://tel.archives-ouvertes.fr/docs/00/28/15/83/PDF/theseAncaVersFin.pdf.
Full textAbstract:
Notre étude se concentre sur les techniques qui offrent un support automatique pour l’adaptation et la révision des modèles dynamiques. L’objectif est d’étudier comment l’outil bond graph peut aider à concevoir des systèmes innovants répondant à un cahier des charges exprimé en termes de comportement temporel ou fréquentiel. Construire un modèle revient toujours à faire une abstraction du système initial. Faire une abstraction du système à modéliser signifie trouver les propriétés les plus pertinentes pour la tâche à résoudre. Pour un modélisateur peu expérimenté c’est une étape difficile, car s’il n’a pas fait les bons choix son modèle se montrera faux, étant trop grossier ou trop simple. Avec notre approche, l’intention est d’indiquer une autre capacité de la méthodologie bond graph, celle d’un outil de reconstruction, qui pourrait suggérer des solutions dans le cas d’un dispositif inconsistant avec les spécifications. Nous désirons aussi que le système proposé dans cette étude puisse être utilisé comme outil dans la phase de conception des dispositifs technologiques soumis à un cahier des charges. En vue de la conception nous proposons un algorithme qui permet de retrouver les solutions proposées par les ingénieurs et si c’est possible des modèles alternatifs<br>Our study concentrates on the techniques which offer an automatic support for the adaptation and the revision of the dynamic models. The objective is to study how bond graphs can help to conceive innovating systems answering a set of specifications expressed in terms of temporal or frequential behavior. The main concern of an engineer confronted with a modelling problem is to make an abstraction of the system he needs to model. It is a difficult task to determine which aspects or properties are relevant for the system at hand. Sometimes these choices may be the source of models with inconsistencies that will fail in the analysis or control phase. Several physical aspects of the system (friction, fluid inertia, etc) that were not taken into consideration may be the cause of an inconsistent model. With our approach the intention was to point out another capability of this method, that of a reconstruction tool, which may indicate to a possible solution in case of an inconsistent with specifications design. We also wish that the system suggested in this study to be used as a tool in conceptual design of technological devices subjected to a set of specifications
36
Behrisch, Michael. "Stochastical models for networks in the life sciences." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2008. http://dx.doi.org/10.18452/15716.
Full textAbstract:
Motiviert durch strukturelle Eigenschaften molekularer Ähnlichkeitsnetzwerke werden die Evolution der größten Komponente eines Netzwerkes in zwei verschiedenen stochastischen Modellen, zufälligen Hypergraphen und zufälligen Schnittgraphen, untersucht. Zuerst wird bewiesen, dass die Anzahl der Knoten in der größten Komponente d-uniformer Hypergraphen einer Normalverteilung folgt. Der Beweis nutzt dabei ausschließlich probabilistische Argumente und keine enumerative Kombinatorik. Diesem grundlegenden Resultat folgen weitere Grenzwertsätze für die gemeinsame Verteilung von Knoten- und Kantenzahl sowie Sätze zur Zusammenhangswahrscheinlichkeit zufälliger Hypergraphen und zur asymptotischen Anzahl zusammenhängender Hypergraphen. Da das Hypergraphenmodell einige Eigenschaften der Realweltdaten nur unzureichend abbildet, wird anschließend die Evolution der größten Komponente in zufälligen Schnittgraphen, die Clustereigenschaften realer Netzwerke widerspiegeln, untersucht. Es wird gezeigt, dass zufällige Schnittgraphen sich von zufälligen (Hyper-)Graphen dadurch unterscheiden, dass (bei einer durchschnittlichen Nachbaranzahl von mehr als eins) weder die größte Komponente linear noch die zweitgrößte Komponente logarithmisch groß in Abhängigkeit von der Knotenzahl ist. Weiterhin wird ein Polynomialzeitalgorithmus zur Überdeckung der Kanten eines Graphen mit möglichst wenigen Cliquen (vollständigen Graphen) beschrieben und seine asymptotische Optimalität im Modell der zufälligen Schnittgraphen bewiesen. Anschließend wird die Entwicklung der chromatischen Zahl untersucht und gezeigt, dass zufällige Schnittgraphen mit hoher Wahrscheinlichkeit mittels verschiedener Greedystrategien optimal gefärbt werden können. Letztendlich zeigen Experimente auf realen Netzen eine Übereinstimmung mit den theoretischen Vorhersagen und legen eine gegenseitige Zertifizierung der Optimalität von Cliquen- und Färbungszahl durch Heuristiken nahe.<br>Motivated by structural properties of molecular similarity networks we study the behaviour of the component evolution in two different stochastic network models, that is random hypergraphs and random intersection graphs. We prove gaussian distribution for the number of vertices in the giant component of a random d-uniform hypergraph. We provide a proof using only probabilistic arguments, avoiding enumerative methods completely. This fundamental result is followed by further limit theorems concerning joint distributions of vertices and edges as well as the connectivity probability of random hypergraphs and the number of connected hypergraphs. Due to deficiencies of the hypergraph model in reflecting properties of the real--world data, we switch the model and study the evolution of the order of the largest component in the random intersection graph model which reflects some clustering properties of real--world networks. We show that for appropriate choice of the parameters random intersection graphs differ from random (hyper-)graphs in that neither the so-called giant component, appearing when the average number of neighbours of a vertex gets larger than one, has linear order nor is the second largest of logarithmic order in the number of vertices. Furthermore we describe a polynomial time algorithm for covering graphs with cliques, prove its asymptotic optimality in a random intersection graph model and study the evolution of the chromatic number in the model showing that, in a certain range of parameters, these random graphs can be coloured optimally with high probability using different greedy algorithms. Experiments on real network data confirm the positive theoretical predictions and suggest that heuristics for the clique and the chromatic number can work hand in hand proving mutual optimality.
37
Kaci, Naouel. "Analyse structurelle et diagnostic robuste des actionneurs électromécaniques : approche Bond Graph." Thesis, Lille 1, 2020. http://www.theses.fr/2020LIL1I067.
Full textAbstract:
L’orientation de l’industrie aéronautique vers des technologies plus propres a conduit à remplacer progressivement les réseaux d’actionneurs hydrauliques classiques par des actionneurs Electromécaniques (EMA). La sureté de fonctionnement imposée dans le domaine aéronautique nécessite une détection précoce et une localisation des défaillances pour assurer la fiabilité et la disponibilité de l’actionneur. L’un des défauts critiques identifié est le grippage (appelé Jamming) qu’il faut alors surveiller en fonction de l’architecture d’instrumentation existante. La résolution de cette problématique, objectif principal de la thèse, a été réalisée en trois étapes par une approche intégrée en utilisant la théorie Bond Graph (BG). Une première étape concerne l’analyse des conditions de surveillabilité structurelle (aptitude à détecter et à isoler les défauts) des modèles Bond Graph (BG) déterministes obtenus de l’EMA. Sur la base des résultats de surveillabilité obtenus, un placement de capteur a été propose par la synthèse d’un observateur pour améliorer les performances de surveillabilité des sous-systèmes (principalement pour surveiller le défaut fixé par l’industriel : le Jamming). L’intérêt scientifique d’une telle approche réside dans le fait qu’elle soit indépendante des valeurs numériques des paramètres à ce niveau en exploitant les propriétés structurelles et causales du BG. Une deuxième partie consiste à la validation analytique des propriétés structurelles obtenues. Pour cela, a été proposé l’implémentation des relations de redondance analytiques robustes aux incertitudes paramétriques déduites sur le modèle BG étendu, appelé BG-LFT. Et enfin une validation industrielle par cosimulation avec le logiciel Amesim© a été réalisée dans la troisième partie<br>The orientation of the aviation industry towards cleaner technologies has led to the gradual replacement of conventional hydraulic actuator networks by Electromechanical actuators (EMA). The operating safety required in the aeronautical domain requires earlier fault detection and isolation to ensure the reliability and availability of the actuator. One of the critical identified failure is a jamming which must then be monitored based on the existing instrumentation architecture. The resolution of this problem which is the main objective of the PhD. thesis, was carried out in three stages using a Bond Graph theory (BG) as an integrated and unified approach. The first step concerns the structural monitorability (ability to detect and isolate faults) analysis based on deterministic Bond Graph (BG) models obtained from the EMA. Based on the structural monitorability conditions results, a sensor placement was proposed by the synthesis of an observer to improve the monitoring performances of the subsystems (mainly to monitor the fault required by the manufacturer: jamming). The scientific interest of such approach lies in the fact that it is independent of the numerical values of the parameters at this level by exploiting the structural and causal properties of the BG. A second step consists in the analytical validation of the obtained structural properties. For this task, the implementation of analytical redundancy relations, robust to parametric uncertainties, deduced from the extended BG model (called BG-LFT), have been proposed. And finally, an industrial validation by cosimulation with the Amesim© software was carried out in the third part
38
Couch, Marshall. "Effects of Curved Lines on Force-Directed Graphs." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/honors/64.
Full textAbstract:
The most common methods for simplifying force-directed graphs are edge-bundling and edge routing. Both of these methods can be done with curved, rather than straight, lines which some researchers have argued. Curved lines have been offered as a solution for clarifying edge resolution. Curved lines were originally thought to be more aesthetically pleasing. 32 computer science students were surveyed and asked questions about straight and curved line graphs. Research conducted by Xu et al. and this study suggests that curved lines make a graph more difficult to understand and slower to read. Research also suggests that curved lines are no more aesthetically pleasing than straight lines. Situations may exist where curved lines are beneficial to a graph’s readability, but it is unclear due to uncontrolled variables in this study. Further study could reveal circumstances when curved lines would be beneficial.
39
Bresch, Didier. "Etude et réalisation d'un outil logiciel de modélisation et de simulation de systèmes automatiques utilisant la représentation des graphes à liens." Mulhouse, 1986. http://www.theses.fr/1986MULH0011.
Full textAbstract:
On montre qu'en utilisant un langage de description graphique universel, il est possible de décrire n'importe quel système dynamique. Ce langage de modélisation est celui des graphes à liens qui présente des similitudes avec les graphes de fluence. On montre qu'avec le langage des graphes à liens tout système linéaire peut être synthétisé à partir de 7 éléments fondamentaux : la capacitance, l'inertance, la résistance, le transformateur, le gyrateur, l'élément de jonction série et parallèle. On propose une méthode de transformation rationnelle et universelle d'un modèle graphique d'un système dynamique multivariable en modèle mathématique utilisant les variables d'état physiques. Le logiciel se présente en 3 parties: après une phase d'expansion des macros et d'édition des liens entre les modules, le graphe final est analysé, la syntaxe et la cohérence des associations d'éléments sont vérifiées. à ce stade on applique la procédure de formulation automatique du modèle en équations d'états; la troisième partie concerne l'exploitation du modèle mathématique
40
Decotte, Benjamin. "Identifiabilité structurelle de modèles bond graphs." Lille 1, 2002. https://pepite-depot.univ-lille.fr/RESTREINT/Th_Num/2002/50376-2002-291.pdf.
Full textAbstract:
Nous développons dans cette thèse un critère en vue de l'analyse de l'identifiabilité d'une forme particulière de modèle, les bond graphs. Ce critère permet de conclure quant à l'identifiabilité globale ou locale de l'ensemble des paramètres d'un bond graph, ou d'un sous-ensemble de ces paramètres. De plus nous proposons une méthode permettant de discerner l'ensemble des paramètres que l'utilisateur peut chercher à identifier, en fonction de la structure du modèle, et en fonction de ses besoins et capacités techniques de placement de capteurs. Nous présentons aussi une méthode de construction de l'ensemble des bond graphs structurellement identifiables, ainsi candidats à l'identification symbolique de leurs paramètres. Enfin nous appliquons ces méthodes à deux exemples concrets, le comportement d'une cale en polyuréthane et le comportement d'une suspension.
41
Mesangeau, Julien. "Figures du « réseautage en ligne » sur les réseaux socionumériques professionnels : le cas d’un groupe d’anciens sur LinkedIn." Thesis, Rennes 2, 2012. http://www.theses.fr/2012REN20065/document.
Full textAbstract:
Notre enquête a été conduite auprès de membres d’un groupe d’anciens élèves hébergé sur le site de réseau social professionnel LinkedIn. Elle a permis de produire deux résultats. Le premier résultat est une typologie des figures du réseautage en ligne. Nous proposons trois figures. Le NetMining, qui relève d’un usage exploratoire du site et oùl’utilisateur cumule de nombreux contacts. Le NetWorking où l’utilisateur sélectionne des relations sur la base de critères précis. Le NetSticking où l’utilisateur reproduit en ligne un réseau personnel basé sur la confiance. Ces trois tendances permettent de souligner deux caractéristiques propres aux pratiques de réseautage en ligne. D’une part, elles reposent surune pluralité de dispositifs de communication où LinkedIn occupe une place tantôt centrale, tantôt marginale. D’autre part, ces pratiques ne reposent pas nécessairement sur la poursuite d’une action planifiée. Le second résultat produit par notre enquête est un dispositif d’étude des pratiques de réseautage. Il associe des techniques de visualisation de graphes et analyses d’entretiens semi-directifs<br>Our study had been carried on members of a social network hosted on the professional social network site, LinkedIn. It produced two main outcomes. The first is a typology of online Networking on three different classes. The first is the NetMining, which is a exploratory use of the website, where the user accumulated contacts. The second category is the NetWorking, where the users select contacts based on defined characteristics. The NetSticking is the third category, in which the user reproduced online a personal network based on trust. Those three categories highlight two main characteristics, specific to online networking. First, networking uses different means of communication, in whichLinkedIn is sometimes central, but sometimes marginal. Those practices are besides not necessarily based on planed actions. The Second result of our enquiry is a study device of the networking practices which associated graphs visualization technics and semi-directed interviews analyses
42
Childs, Liam, Zoran Nikoloski, Patrick May, and Dirk Walther. "Identification and classification of ncRNA molecules using graph properties." Universität Potsdam, 2009. http://opus.kobv.de/ubp/volltexte/2010/4519/.
Full textAbstract:
The study of non-coding RNA genes has received increased attention in recent years fuelled by accumulating evidence that larger portions of genomes than previously acknowledged are transcribed into RNA molecules of mostly unknown function, as well as the discovery of novel non-coding RNA types and functional RNA elements. Here, we demonstrate that specific properties of graphs that represent the predicted RNA secondary structure reflect functional information. We introduce a computational algorithm and an associated web-based tool (GraPPLE) for classifying non-coding RNA molecules as functional and, furthermore, into Rfam families based on their graph properties. Unlike sequence-similarity-based methods and covariance models, GraPPLE is demonstrated to be more robust with regard to increasing sequence divergence, and when combined with existing methods, leads to a significant improvement of prediction accuracy. Furthermore, graph properties identified as most informative are shown to provide an understanding as to what particular structural features render RNA molecules functional. Thus, GraPPLE may offer a valuable computational filtering tool to identify potentially interesting RNA molecules among large candidate datasets.
43
Ho, Yiu Yu. "Global secure sets of trees and grid-like graphs." Doctoral diss., University of Central Florida, 2011. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/4922.
Full textAbstract:
However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in (BDH07) for exactly this purpose. The non-empty set S is a secure set if every subset Xsubset of]S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In (BDH07), the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A non-empty set S is a secure set if and only if for all] X subset of] S, vertical line]N (X) intersection] Svertical line] greater than or equal to] vertical line]N(X) - Svertical line] ((BDH07),Theorem 11). The cardinality of a minimum secure set is the security number of G, denoted s(G). A secure set S is a global secure set if it further satisfies N (S)= V. The cardinality of a minimum global secure set of G is the global security number of G, denoted gamma subscript s](G). In this work, we present results on secure sets and global secure sets. In particular, we treat the computational complexity of finding the security number of a graph, present algorithms and bounds for the global security numbers of trees, and present the exact values of the global security numbers of paths, cycles and their Cartesian products.; Let G = (V, E) be a graph and let S subset of] V be a subset of vertices. The set S is a defensive alliance if for all x element of] S, vertical line]N(x)intersection] Svertical line]greater than or equal to] vertical line]N(x) - Svertical line]. The concept of defensive alliances was introduced in (KHH04), primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if anyone of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x outside the alliance. In a graph model, the vertices of a graph represent nations and the edges represent country boundaries. Thus, if the nation corresponding to a vertex x is attacked by its neighbors outside the alliance, the attack can be thwarted by x with the assistance of its neighbors in the alliance. In a different subject matter, (FLG00) applies graph theory to model the world wide web, where vertices represent websites and edges represent links between websites. A web community is a subset of vertices of the web graph, such that every vertex in the community has at least as many neighbors in the set as it has outside. So, a web community C satisfies for all] x element of] C, vertical line]N(x) intersection] Cvertical line] greater than] vertical line]N(x) - Cvertical line]. These sets are very similar to defensive alliances. They are known as strong defensive alliances in the literature of alliances in graphs. Other areas of application for alliances and related topics include classification, data clustering, ecology, business and social networks. Consider the application of modeling nations in times of war introduced in the first paragraph. In a defensive alliance, any attack on a single member of the alliance can be successfully defended.<br>ID: 030423421; System requirements: World Wide Web browser and PDF reader.; Mode of access: World Wide Web.; Thesis (Ph.D.)--University of Central Florida, 2011.; Includes bibliographical references (p. 206-210).<br>Ph.D.<br>Doctorate<br>Electrical Engineering and Computer Science<br>Engineering and Computer Science
44
Richard, Émile. "Regularization methods for prediction in dynamic graphs and e-marketing applications." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2012. http://tel.archives-ouvertes.fr/tel-00906066.
Full textAbstract:
Predicting connections among objects, based either on a noisy observation or on a sequence of observations, is a problem of interest for numerous applications such as recommender systems for e-commerce and social networks, and also in system biology, for inferring interaction patterns among proteins. This work presents formulations of the graph prediction problem, in both dynamic and static scenarios, as regularization problems. In the static scenario we encode the mixture of two different kinds of structural assumptions in a convex penalty involving the L1 and the trace norm. In the dynamic setting we assume that certain graph features, such as the node degree, follow a vector autoregressive model and we propose to use this information to improve the accuracy of prediction. The solutions of the optimization problems are studied both from an algorithmic and statistical point of view. Empirical evidences on synthetic and real data are presented showing the benefit of using the suggested methods.
45
Bensmail, Julien. "Partitions et décompositions de graphes." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0062/document.
Full textAbstract:
Cette thèse est dédiée à l’étude de deux familles de problèmes de partition de graphe. Nous considérons tout d’abord le problème de sommet-partitionner un graphe en sous-graphesconnexes. Plus précisément, étant donnés p entiers positifs n1; n2; :::; np dont la somme vautl’ordre d’un graphe G, peut-on partitionner V (G) en p parts V1; V2; :::; Vp de sorte que chaque Vi induise un sous-graphe connexe d’ordre ni ? Nous nous intéressons ensuite à des questions plus fortes. Que peut-on dire si l’on souhaite que G soit partitionnable de cette manière quels que soient p et n1; n2; :::; np ? Si l’on souhaite que des sommets particuliers de G appartiennent à des sous-graphes particuliers de la partition ? Et si l’on souhaite que les sous-graphes induits soient plus que connexes ? Nous considérons toutes ces questions à la fois du point de vue structurel (sous quelles conditions structurelles une partition particulière existe-t-elle nécessairement ?) et algorithmique (est-il difficile de trouver une partition particulière ?).Nous nous intéressons ensuite à la 1-2-3 Conjecture, qui demande si tout graphe G admet une 3-pondération voisin-somme-distinguante de ses arêtes, i.e. une 3-pondération par laquelle chaque sommet de G peut être distingué de ses voisins en comparant uniquement leur somme de poids incidents. Afin d’étudier la 1-2-3 Conjecture, nous introduisons notamment la notionde coloration localement irrégulière d’arêtes, qui est une coloration d’arêtes dont chaque classe de couleur induit un sous-graphe dans lequel les sommets adjacents sont de degrés différents.L’intérêt principal de cette coloration est que, dans certaines situations, une pondération d’arêtes voisin-somme-distinguante peut être déduite d’une coloration d’arêtes localement irrégulière. Nospréoccupations dans ce contexte sont principalement algorithmiques (est-il facile de trouver une pondération d’arêtes voisin-somme-distinguante ou une coloration d’arêtes localement irrégulière utilisant le plus petit nombre possible de poids ou couleurs ?) et structurelles (quel est le plus petit nombre de couleurs d’une coloration d’arêtes localement irrégulière ?). Nous considérons également ces questions dans le contexte des graphes orientés<br>This thesis is dedicated to the study of two families of graph partition problems.First, we consider the problem of vertex-partitioning a graph into connected subgraphs.Namely, given p positive integers n1; n2; :::; np summing up to the order of some graph G, canwe partition V (G) into p parts V1; V2; :::; Vp so that each Vi induces a connected subgraph withorder ni? We then consider stronger questions. Namely, what if we want G to be partitionablewhatever are p and n1; n2; :::; np? What if we also want specific vertices of G to belong to somespecific subgraphs induced by the vertex-partition? What if we want the subgraphs induced bythe vertex-partition to be more than connected? We consider all these questions regarding boththe structural (are there structural properties ensuring that a specific vertex-partition necessarilyexists?) and algorithmic (is it hard to deduce a specific vertex-partition?) points of view.Then, we focus on the so-called 1-2-3 Conjecture, which asks whether every graph G admitsa neighbour-sum-distinguishing 3-edge-weighting, i.e. a 3-edge-weighting by which all adjacentvertices of G get distinguished by their sums of incident weights. As a tool to deal with the1-2-3 Conjecture, we notably introduce the notion of locally irregular edge-colouring, which isan edge-colouring in which every colour class induces a subgraph whose adjacent vertices havedistinct degrees. The main point is that, in particular situations, a neighbour-sum-distinguishingedge-weighting of G can be deduced from a locally irregular edge-colouring of it. Our concernsin this context are mostly algorithmic (can we easily find a neighbour-sum-distinguishing edgeweightingor locally irregular edge-colouring using the least number of weights or colours?) andstructural (what is the least number of colours in a locally irregular edge-colouring?). We alsoconsider similar matters in the context of oriented graphs
46
Abu-Ata, Muad Mustafa. "Tree-Like Structure in Graphs and Embedability to Trees." Kent State University / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=kent1397345185.
Full text
47
Mendu, Prasad Reddy. "Link Prediction in Time-Evolving Graphs." University of Cincinnati / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470757663.
Full text
48
Djeziri, Mohand Arab. "Diagnostic des systèmes incertains par l’approche Bond Graph." Ecole Centrale de Lille, 2007. http://tel.archives-ouvertes.fr/docs/00/20/00/30/PDF/These-Djeziri-07-12-2007.pdf.
Full textAbstract:
Le travail de thèse concerne la conception d’un système de surveillance robuste aux incertitudes paramétriques à base de modèles bond graph sous forme LFT ( Linear Fractional Transformations). Une procédure de génération automatique de résidus robustes et de seuils adaptatifs de fonctionnement normal a été développée et implémentée à l’aide d’outils logiciels appropriés. Les performances du diagnostic sont contrôlées par une analyse de la sensibilité de ces résidus, permettant de définir des indices de sensibilité aux incertitudes paramétriques, et des indices de détectabilité des défauts. L’outil bond graph permet par sa nature physique d’estimer à priori les valeurs détectables (en terme de puissance) des défauts physiques. Outre l’implémentation informatique, les résultats de recherche sont validés par deux applications industrielles de complexité différente :Un système électromécanique pour détecter isoler des défauts telle que la variation anormale de l'amplitude du jeu dans la partie réducteur, tout en distinguant le défaut des variations paramétriquesUn procédé énergétique de génération de vapeur, qui constitue un système non stationnaire, où l'espace paramétrique est plus complexe<br>This work deals with robust fault diagnosis in presence of parameter uncertainties using bond graph model in LFT form (Linear Fractional Transformations). An approach for ARRs and adaptive thresholds generation is developed and implemented on appropriate software. The diagnosis performances are improved using a residual sensitivity analysis, which allows defining sensitivity indexes of parameter uncertainties and fault delectability indexes. The fault detectable value can be estimated (in puissance terms) due to the energetic aspect of the bond graph tools. The developed method is applied in real time on two industrial applications with different complexities: Mechatronic system, in order to detect and to isolate backlash phenomenon by distinguishing fault from parameter uncertaintiesEnergetic process of steam generation, which is a no stationary system with a complex parameter space
49
Bergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.
Full textAbstract:
Nous étudions des problèmes NP-difficiles portant sur les graphes contenant des blocages.Nous traitons les problèmes de coupes du point de vue de la complexité paramétrée. La taille p de la coupe est le paramètre. Étant donné un ensemble de sources {s1,...,sk} et une cible t, nous proposons un algorithme qui construit une coupe de taille au plus p séparant au moins r sources de t. Nous nommons ce problème NP-complet Partial One-Target Cut. Notre algorithme est FPT. Nous prouvons également que la variante de Partial One-Target Cut, où la coupe est composée de noeuds, est W[1]-difficile. Notre seconde contribution est la construction d'un algorithme qui compte les coupes minimums entre deux ensembles S et T en temps $2^{O(plog p)}n^{O(1)}$.Nous présentons ensuite plusieurs résultats sur le ratio de compétitivité des stratégies déterministes et randomisées pour le problème du voyageur canadien.Nous prouvons que les stratégies randomisées n'utilisant pas de mémoire ne peuvent pas améliorer le ratio 2k+1. Nous apportons également des éléments concernant les bornes inférieures de compétitivité de l'ensemble des stratégies randomisées. Puis, nous étudions la compétitivité en distance d'un groupe de voyageurs avec et sans communication. Enfin, nous nous penchons sur la compétitivité des stratégies déterministes pour certaines familles de graphes. Deux stratégies, avec un ratio inférieur à 2k+1 sont proposées: une pour les graphes cordaux avec poids uniformes et l'autre pour les graphes où la taille de la plus grande coupe minimale séparant s et t est au plus k<br>We study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1
50
Fotsu, Ngwompo Roger. "Contribution au dimensionnement des systèmes sur des critères dynamiques et énergétiques : approche par bond graph." Lyon, INSA, 1997. http://www.theses.fr/1997ISAL0023.
Full textAbstract:
L'objet de ce mémoire est la présentation d'une méthodologie de dimensionnement des systèmes sur' des critères dynamiques et énergétiques. Un cahier des charges étant imposé et une structure choisie pour la chaîne d'actionnement, il s'agit de vérifier que les composants du système sont susceptibles de suivre les dynamiques imposées tout en respectant les contraintes de puissance. L'outil de modélisation adopté est le bond graph pour ses propriétés de représentation des transferts de puissance et des interconnexions entre les éléments d'un système. Les liens entre le dimensionnement et l'inversion des systèmes nous ont conduit à étudier les problèmes d'inversion d'abord par les méthodes classiques. Ensuite, nous proposons des critères d'étude de l'inversibilité et des procédures de construction des modèles inverses par une approche bond graph en utilisant le concept de bicausalité. Quelques analyses structurelles sur le modèle bond graph inverse sont menées en exploitant les propriétés des liens bicausaux. A partir de ces outils théoriques pour la représentation graphique des m9dèles inverses, nous présentons une méthode de vérification de l'adéquation d'un ensemble d'actionnement à des spécifications imposées par un cahier des charges en remontant des sorties de la chaîne aux entrées par étages successifs. L'illustration de la méthode est faite sur la validation des actionneurs d'un manipulateur deux axes et il est ainsi possible d'analyser les causes d'éventuelles saturations ou de détecter les composantes qui imposent les limitations aux performances du système<br>The purpose of this work is to present a methodology to validate the size of a system components for its proper operation based on dynamic and energetic criteria. If some specifications of a desired performance are given and a structure of actuator system is chosen, then the problem considered here is to check that components of the actuator system are able to follow the desired dynamic while satisfying the power constraints. The modelling tool adopted is bond graph for its property of representing power transfer and interconnections between elements of a system. The links between sizing problem and inverse system have led us to study the problem of system inversion firstly using classical theory. We then propose a bond graph based method for invertibility study and a procedure for construction of inverse bond graph using the concept of bicausality. Some structural anal y sis on the inverse bond graph are carried out by exploiting the properties of bicausal bonds. These theoretical tools and the graphic representation of inverse model then allow us to develop a method for verification of the appropriateness of an actuator system to some performance specifications by checking the proper operation of the system at each lev el from the output to the input. For illustration, the proposed method is applied to the validation of a two-link manipulator actuators and it is thus possible to analyse the causes of saturations and to detect components which impose limitations to the performance of the system