To see the other types of publications on this topic, follow the link: Connection graph.
Dissertations / Theses on the topic 'Connection graph'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 36 dissertations / theses for your research on the topic 'Connection 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
Sato, Cristiane Maria. "Homomorfismos de grafos." Universidade de São Paulo, 2008. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07082008-105246/.
Full textAbstract:
Homomorfismos de grafos são funções do conjunto de vértices de um grafo no conjunto de vértices de outro grafo que preservam adjacências. O estudo de homomorfismos de grafos é bastante abrangente, existindo muitas linhas de pesquisa sobre esse tópico. Nesta dissertação, apresentaremos resultados sobre homomorfismos de grafos relacionados a pseudo-aleatoriedade, convergência de seqüência de grafos e matrizes de conexão de invariantes de grafos. Esta linha tem se mostrado muito rica, não apenas pelos seus resultados, como também pelas técnicas utilizadas nas demonstrações. Em especial, destacamos a diversidade das ferramentas matemáticas que são usadas, que incluem resultados clássicos de álgebra, probabilidade e análise.Graph homomorphisms are functions from the vertex set of a graph to the vertex set of another graph that preserve adjacencies. The study of graph homomorphisms is very broad, and there are several lines of research about this topic. In this dissertation, we present results about graph homomorphisms related to convergence of graph sequences and connection matrices of graph parameters. This line of research has been proved to be very rich, not only for its results, but also for the proof techniques. In particular, we highlight the diversity of mathematical tools used, including classical results from Algebra, Probability and Analysis.
2
Berg, Deborah. "Connections Between Voting Theory and Graph Theory." Scholarship @ Claremont, 2005. https://scholarship.claremont.edu/hmc_theses/178.
Full textAbstract:
Mathematical concepts have aided the progression of many different fields of study. Math is not only helpful in science and engineering, but also in the humanities and social sciences. Therefore, it seemed quite natural to apply my preliminary work with set intersections to voting theory, and that application has helped to focus my thesis. Rather than studying set intersections in general, I am attempting to study set intersections and what they mean in a voting situation. This can lead to better ways to model preferences and to predict which campaign platforms will be most popular. Because I feel that allowing people to only vote for one candidate results in a loss of too much information, I consider approval voting, where people can vote for as many platforms as they like.
3
Zini, Roger. "Placement, routage conjoints et hierarchiques de reseaux prediffuses." Paris 6, 1987. http://www.theses.fr/1987PA066116.
Full textAbstract:
Cette these propose un algorithme original de construction hierarchique d'arbres de steiner ainsi qu'une technique d'estimation de longueur au fur et a mesure de cette construction. Deux algorithmes de partitionnement d'hypergraphes, de maniere gloutonne ou par recuit simule sans rejets, y sont exposes. Elle introduit enfin un concept de directions d'attraction permettant d'effectuer un placement routage de circuits vlsi, a implanter sur des reseaux prediffuses, sous forme de systeme regule par retroaction entre le placement, le routage et l'analyse temporelle, afin d'obtenir du circuit, par un placement-routage adequat, les performances temporelles souhaitees
4
Mirza, Batul J. "Jumping Connections: A Graph-Theoretic Model for Recommender Systems." Thesis, Virginia Tech, 2001. http://hdl.handle.net/10919/31370.
Full textAbstract:
Recommender systems have become paramount to customize
information access and reduce information overload. They serve multiple
uses, ranging from suggesting products and artifacts (to consumers), to
bringing people together by the connections induced by (similar) reactions
to products and services. This thesis presents a graph-theoretic model that
casts recommendation as a process of 'jumping connections' in a graph. In
addition to emphasizing the social network aspect, this viewpoint provides a
novel evaluation criterion for recommender systems. Algorithms for
recommender systems are distinguished not in terms of predicted ratings of
services/artifacts, but in terms of the combinations of people and artifacts
that they bring together. We present an algorithmic framework drawn from
random graph theory and outline an analysis for one particular form of jump
called a 'hammock.' Experimental results on two datasets collected over the
Internet demonstrate the validity of this approach.Master of Science
5
Chaudhuri, Sanjay. "Using the structure of d-connecting paths as a qualitative measure of the strength of dependence /." Thesis, Connect to this title online; UW restricted, 2005. http://hdl.handle.net/1773/8948.
Full text
6
Candel, Gaëlle. "Connecting graphs to machine learning." Electronic Thesis or Diss., Université Paris sciences et lettres, 2022. http://www.theses.fr/2022UPSLE018.
Full textAbstract:
L’objet de cette thèse est de proposer des approches nouvelles permettant l’utilisation d’algorithmes d’apprentissage automatique travaillant usuellement des données tabulaires aux graphes. Un graphe est une structure de donnée composée de nœuds reliés entre eux par des liens. Cette structure peut être représentée sous la forme d’une matrice, où chaque connexion entre de nœuds est représentée par une valeur non nulle, permettant une manipulation des données plus facile. Néanmoins, par leurs différences structurelles, la transposition d’un algorithme exploitant des données tabulaires aux graphes ne donne pas les résultats escomptés. Deux caractéristiques rendent cette adaptation difficile : la faible connectivité des nœuds ainsi que la distribution en loi de puissance du degré des nœuds. Ces caractéristiques conduisent toutes les deux à des matrices creuses pauvres en information tout en nécessitant beaucoup de mémoire de stockage. Dans ces travaux, nous proposons plusieurs manières de prendre en compte ces différences pour deux types de graphes particuliers. Dans la première partie, nous nous intéressons aux graphes de citations et à leur représentation dans l’optique de la veille technologique, tandis que la seconde partie s’adresse aux graphes bipartites utilisés principalement par les systèmes de recommandation. Ces adaptations permettent la réalisation de taches usuelles en apprentissage automatique, telle que le partitionnement et la visualisation des données. Pour le cas des graphes bipartites, des algorithmes spécifiques de co-partitionnement sont proposés pour la segmentation conjointe des deux parties. La troisième partie prend un revers différent. La méthode développée exploite le graphe des k plus proches voisins construit à partir des données tabulaires afin de corriger des erreurs de classifications. Les différentes méthodes développées utilisent diverses approches pour emmagasiner plus d’information dans un vecteur par rapport à l’encodage binaire habituel, permettant de travailler les graphes avec des algorithmes usuel d’apprentissage automatiqueThis thesis proposes new approaches to process graph using machine learning algorithms designed for tabular data. A graph is a data structure made of nodes linked to each others by edges. This structure can be represented under a matrix form where the connection between two nodes is represented by a non-zero value, simplifying the manipulation of the data. Nonetheless, the transposition of an algorithm adapted to tabular data to graphs would not give the expected results because of the structural differences. Two characteristics make the transposition difficult: the low nodes’ connectivity and the power-law distribution of nodes’ degree. These two characteristics both lead to sparse matrices with low information content while requiring a large memory. In this work, we propose several methods that consider these two graph’s specificities. In the first part, we focus on citation graphs which belong to the directed acyclic graph category and can be exploited for technical watch, while the second part is dedicated to bipartite graphs mainly use by recommender systems. These adaptations permit the achievement of usual machine learning tasks, such as clustering and data visualization. Specific co-clustering algorithms were designed to segment jointly each side of a bipartite graph and identify groups of similar nodes. The third part approaches graphs from a different perspective. The developed approach exploits the k nearest neighbours graph built from the tabular data to help correcting classification errors. These different methods use diverse methods to embed more information in a vector compared to the usual binary encoding, allowing to process graphs with usual machine learning algorithm
7
Marshall, Oliver. "Search Engine Optimization and the connection with Knowledge Graphs." Thesis, Högskolan i Gävle, Företagsekonomi, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:hig:diva-35165.
Full textAbstract:
Aim: The aim of this study is to analyze the usage of Search Engine Optimization and Knowledge Graphs and the connection between them to achieve profitable business visibility and reach. Methods: Following a qualitative method together with an inductive approach, ten marketing professionals were interviewed via an online questionnaire. To conduct this study both primary and secondary data was utilized. Scientific theory together with empirical findings were linked and discussed in the analysis chapter. Findings: This study establishes current Search Engine Optimization utilization by businesses regarding common techniques and methods. We demonstrate their effectiveness on the Google Knowledge Graph, Google My Business and resulting positive business impact for increased visibility and reach. Difficulties remain in accurate tracking procedures to analyze quantifiable results. Contribution of the thesis: This study contributes to the literature of both Search Engine Optimization and Knowledge Graphs by providing a new perspective on how these subjects have been utilized in modern marketing. In addition, this study provides an understanding of the benefits of SEO utilization on Knowledge Graphs. Suggestions for further research: We suggest more extensive investigation on the elements and utilization of Knowledge Graphs; how the structure can be affected; which techniques are most effective on a bigger scale and how effectively the benefits can be measured. Key Words: Search Engine, Search Engine Optimization, SEO, Knowledge Graphs, Google My Business, Google Search Engine, Online Marketing.
8
Moens, Theodore Warren Bernelot. "Approaches to procedural adequacy in logic programming using connection graphs." Thesis, University of British Columbia, 1987. http://hdl.handle.net/2429/26499.
Full textAbstract:
Kowalski's connection graph method provides a representation for logic programs which allows for the incorporation of better procedural control techniques than standard logic programming languages. A proposed search strategy for visual recognition which combines top-down and bottom-up techniques has been incorporated in a connection graph implementation.
The connection graph representation also allows for the natural incorporation of constraint satisfaction techniques in logic programming. Kowalski's approach to incorporating constraint satisfaction techniques in connection graphs is examined in detail. It is shown that his approach is not efficient enough to be used as a general preprocessing algorithm but that a modified version may be of use.
Increased control of search and the incorporation of consistency techniques increase the procedural adequacy of logic programs for representing knowledge without compromising the descriptive capacity of the form.Science, Faculty of
Computer Science, Department of
Graduate
9
Hennayake, Kamal P. "Generalized edge connectivity in graphs." Morgantown, W. Va. : [West Virginia University Libraries], 1998. http://etd.wvu.edu/templates/showETD.cfm?recnum=383.
Full textAbstract:
Thesis (Ph. D.)--West Virginia University, 1998.Title from document title page. Document formatted into pages; contains v, 87 p. : ill. Includes abstract. Includes bibliographical references (p. 64-72).
10
Camby, Eglantine. "Connecting hitting sets and hitting paths in graphs." Doctoral thesis, Universite Libre de Bruxelles, 2015. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209048.
Full textAbstract:
Dans cette thèse, nous étudions les aspects structurels et algorithmiques de différents problèmes de théorie des graphes. Rappelons qu’un graphe est un ensemble de sommets éventuellement reliés par des arêtes. Deux sommets sont adjacents s’ils sont reliés par une arête.Tout d’abord, nous considérons les deux problèmes suivants :le problème de vertex cover et celui de dominating set, deux cas particuliers du problème de hitting set. Un vertex cover est un ensemble de sommets qui rencontrent toutes les arêtes alors qu’un dominating set est un ensemble X de sommets tel que chaque sommet n’appartenant pas à X est adjacent à un sommet de X. La version connexe de ces problèmes demande que les sommets choisis forment un sous-graphe connexe. Pour les deux problèmes précédents, nous examinons le prix de la connexité, défini comme étant le rapport entre la taille minimum d’un ensemble répondant à la version connexe du problème et celle d’un ensemble du problème originel. Nous prouvons la difficulté du calcul du prix de la connexité d’un graphe. Cependant, lorsqu’on exige que le prix de la connexité d’un graphe ainsi que de tous ses sous-graphes induits soit borné par une constante fixée, la situation change complètement. En effet, pour les problèmes de vertex cover et de dominating set, nous avons pu caractériser ces classes de graphes pour de petites constantes.
Ensuite, nous caractérisons en termes de dominating sets connexes les graphes Pk- free, graphes n’ayant pas de sous-graphes induits isomorphes à un chemin sur k sommets. Beaucoup de problèmes sur les graphes sont étudiés lorsqu’ils sont restreints à cette classe de graphes. De plus, nous appliquons cette caractérisation à la 2-coloration dans les hypergraphes. Pour certains hypergraphes, nous prouvons que ce problème peut être résolu en temps polynomial.
Finalement, nous travaillons sur le problème de Pk-hitting set. Un Pk-hitting set est un ensemble de sommets qui rencontrent tous les chemins sur k sommets. Nous développons un algorithme d’approximation avec un facteur de performance de 3. Notre algorithme, basé sur la méthode primal-dual, fournit un Pk-hitting set dont la taille est au plus 3 fois la taille minimum d’un Pk-hitting set.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
11
Bywaters, Timothy Peter. "Connections Between Willis' Theory for Totally Disconnected Locally Compact Groups and Graph Automorphisms." Thesis, The University of Sydney, 2019. http://hdl.handle.net/2123/21148.
Full textAbstract:
We investigate the tidy subgroups, scale function and related invariants of totally disconnected locally compact groups. Our focus is on relating these ideas to combinatorial and geometric aspects of the group. After giving necessary background, we study the scale function and tidy subgroups of an endomorphism of a totally disconnected locally compact group. Our results are inspired by a similar investigation for automorphisms by Möller (Can. J. Math., 54(4), 795-827). We characterise when a compact open subgroup is tidy for an endomorphism in terms of a graph constructed from the subgroups and the endomorphism. Using this characterisation, we develop a tidying procedure which produces from a compact open subgroup, a tidy subgroup. We also use our characterisation to prove a tree representation theorem for endomorphisms, inspired by a similar theorem of Baumgartner and Willis (Isr. J. Math., 142(1), 221-248) for automorphisms. We then study restricted Burger-Mozes groups. These are algebraic subgroups of the autmorphism group of a regular tree but are not equipped with the permutation topology. The stabiliser of a vertex in these groups is open but not compact. We calculate invariants for these groups and relate them to similar calculations done for the automorphism group of a regular tree. This gives insight on how results for the automorphism group of a regular tree may generalise to a larger class of totally disconnected locally compact groups. We investigate the space of directions for a totally disconnected locally compact group acting vertex transitively with compact open vertex stabilisers on a hyperbolic graph. Generalising the discrete case, we call such groups hyperbolic. We show that the space of directions for a hyperbolic group is a discrete metric space and that asymptotic classes are determined by fixed points on the boundary of the hyperbolic graph. This verifies a conjecture of Baumgartner, Möller and Willis (Isr. J. Math., 190(1), 365-388).
12
Montero, Leandro Pedro. "Graphes et couleurs : graphes arêtes-coloriés, coloration d'arêtes et connexité propre." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00776899.
Full textAbstract:
Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément, 1) Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$. 2) Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc. 3) Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux. 4) Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$.
13
Croona, Joakim, and Natalie Strömdahl. "Keyword connections between scientific papers written by KTH researchers." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229754.
Full textAbstract:
There is an increasing interest in understanding and visualising interactions between researchers and scientific fields. Depicting the interactions can be done multiple ways. Furthermore, when many elements are involved, graphs is a good way to illustrate the interactions. Therefore, this report will investigate the interactions between scientific fields and how the interactions may reveal the emergence of new research fields and subdisciplines. Keyword networks is a growing research field that can show a great deal about the different trends in science. The purpose of this study is more specifically to produce a keyword network based on the articles in the database DiVA, which KTH Royal Institute of Technology and other universities in Sweden use to store scientific reports. All articles published by KTH researchers between 2010-2017 were collected from DiVA by web crawling. The collected data was then used to create graphs where articles were represented by nodes and an edge between nodes was made if two articles had one or more keywords in common. The method was based on the earlier scientific study conducted by Li et al. The results showed that the number of connections between articles in-creased when more articles shared one or more keywords from the year 2010 until 2016. The year 2017 was an exception since the results drastically differed. Finally, the conclusion was that KTH’s connections in research has increased between the years 2010 and 2016. Scientists are also immersing themselves in fields rather than exploring new ones as was indicated by a decrease in new keywords associated with the papers.Det finns ett ökat intresse för att förstå och visualisera samspel mellan forskareoch vetenskapliga områden. Att synligöra dessa samband kan göras på ett flertal sätt. Fortsättningsvis, vid ett stort antal element att ta hänsyn till är grafer ett bra sätt att visa interaktionerna. Den här rapporten kommer således utforska samspelet mellan vetenskapliga områden och hur dessa samband resulterar i nya ämnen och subdiscipliner. Nyckelordsnätverk blir ett allt vanligare forskningsområde som kan berätta mycket om vad det finns för trender inom vetenskapen. Syftet med den här studien var mer specificerat att framställa ett nyckelordsnätverk baserat på rapporterna i databasen DiVA, där Kungliga Tekniska Högskolan och även andra universitet i Sverige lagrar sina vetenskapliga rapporter. Alla avhandlingar hämtades från DiVA med hjälp av web crawling för att sedan lagras i en databas. Den insamlade datan användes i sin tur till att bilda grafer, där avhandlingarna representerades som noder och en kant mellan två noder bildades ifall avhandlingar hade ett eller flera nyckelord gemensamt. Metoden baserades på den tidigare vetenskapliga studien av Li et al. Resultaten visade att antalet kopplingar mellan rapporter ökade då ett ökat antal rapporter delade ett eller mera nyckelord från år 2010 fram till 2016. 2017 var en avvikelse där resultaten skiljde sig drastiskt. Slutsatsen som drogs var att sammankopplingen av KTH:s forskning har ökat mellan åren 2010 till 2016. Forskare börjar även fördjupa sig i ämnen snarare än att utforska nya.
14
Halftermeyer, Pierre. "Connexité dans les Réseaux et Schémas d’Étiquetage Compact d’Urgence." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0140/document.
Full textAbstract:
L’objectif de cette thèse est d’attribuer à chaque sommet x d’un graphe G à n sommets une étiquette L(x) de taille compacte O(log n) bits afin de pouvoir :1. construire, à partir des étiquettes d’un ensemble de sommets en panne X C V (G), une structure de donnée S(X)2. décider, à partir de S(X) et des étiquettes L(u) et L(v), si les sommets u et v sont connectés dans le graphe G n X.Nous proposons une solution à ce problème pour la famille des graphes 3-connexes de genre g (via plusieurs résultats intermédiaires).— Les étiquettes sont de taille O(g log n) bits— Le temps de construction de la structure de donnée S(X) est O(Sort([X]; n)).— Le temps de décision est O(log log n). Ce temps est optimal.Nous étendons ce résultat à la famille des graphes excluant un mineur H fixé. Les étiquettes sont ici de taille O(polylog n) bitsWe aim at assigning each vertex x of a n-vertices graph G a compact O(log n)-bit label L(x) in order to :1. construct, from the labels of the vertices of a forbidden set X C V (G), a datastructure S(X)2. decide, from S(X), L(u) and L(v), whether two vertices u and v are connected in G n X.We give a solution to this problem for the family of 3-connected graphs whith bounded genus.— We obtain O(g log n)-bit labels.— S(X) is computed in O(Sort([X]; n)) time.— Connection between vertices is decided in O(log log n) optimal time.We finally extend this result to H-minor-free graphs. This scheme requires O(polylog n)-bit labels
15
Doan, Trung Duy [Verfasser], Ingo [Akademischer Betreuer] Schiermeyer, Ingo [Gutachter] Schiermeyer, and Arnfried [Gutachter] Kemnitz. "Proper connection number of graphs / Trung Duy Doan ; Gutachter: Ingo Schiermeyer, Arnfried Kemnitz ; Betreuer: Ingo Schiermeyer." Freiberg : Technische Universität Bergakademie Freiberg, 2018. http://d-nb.info/1226100597/34.
Full text
16
Zetterberg, Andreas. "Connecting the dots : Network analysis, landscape ecology, and practical application." Doctoral thesis, KTH, Miljöbedömning och -förvaltning, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-48491.
Full textAbstract:
Humans have a profound impact on ecosystems, and land-use change constitutes a primary driving force in the loss of biodiversity. Habitat loss and fragmentation are key factors in this process by seriously impeding the habitat availability and movement of species, leading to a significant decrease in population viability. Landscape connectivity management able of crossing administrative and ecological spatial and temporal scales has been identified as one of the most important measures to counteract these negative impacts. The use of graph-theory and network-based landscape-ecological tools has become established as a promising way forward to address these issues. Despite urgent needs to adapt and implement such tools in planning, assessment and decision-making, surprisingly little attention has been paid to developing approaches for their effective practical application. This thesis presents the development of a toolbox with network-based, landscape-ecological methods and graph-theoretic indicators, which can be effectively implemented by practitioners within environmental assessment, physical planning and design, to analyze landscape connectivity. Recent advances in network analysis and landscape ecology are brought together and adapted for practical application, bridging the gap between science and practice. The use of participatory approaches was identified as key to successful development, and several workshops, meetings, interviews, as well as prototype testing of the developed software were conducted throughout the study. Input data and selection of species were based on the experience gained through seven real-world cases, commissioned by different governmental organizations within Stockholm County. The practitioners’ perspectives on effective practical application of the proposed toolbox were then assessed through an interview-study. The respondents anticipated improved communication with other actors in addition to being able to better assess critical ecological structures within the landscape. The toolbox was finally tested in a large-scale network analysis of impacts of the regional development plan (RUFS 2010), leading to important insights on the planning of connectivity in an urbanizing region.QC 20111125
17
Sartipi, Kamran. "Software Architecture Recovery based on Pattern Matching." Thesis, University of Waterloo, 2003. http://hdl.handle.net/10012/1122.
Full textAbstract:
Pattern matching approaches in reverse engineering aim to incorporate domain knowledge and system documentation in the software architecture extraction process, hence provide a user/tool collaborative environment for architectural design recovery. This thesis presents a model and an environment for recovering the high level design of legacy software systems based on user defined architectural patterns and graph matching techniques.
In the proposed model, a high-level view of a software system in terms of the system components and their interactions is represented as a query, using a description language. A query is mapped onto a pattern-graph, where a module and its interactions with other modules are represented as a group of graph-nodes and a group of graph-edges, respectively. Interaction constraints can be modeled by the description language as a part of the query. Such a pattern-graph is applied against an entity-relation graph that represents the information extracted from the source code of the software system. An approximate graph matching process performs a series of graph edit operations (i. e. , node/edge insertion/deletion) on the pattern-graph and uses a ranking mechanism based on data mining association to obtain a sub-optimal solution. The obtained solution corresponds to an extracted architecture that complies with the given query.
An interactive prototype toolkit implemented as part of this thesis provides an environment for architecture recovery in two levels. First the system is decomposed into a number of subsystems of files. Second each subsystem can be decomposed into a number of modules of functions, datatypes, and variables.
18
Bach, Benjamin. "Connections, changes, and cubes : unfolding dynamic networks for visual exploration." Phd thesis, Université Paris Sud - Paris XI, 2014. http://tel.archives-ouvertes.fr/tel-01020535.
Full textAbstract:
Networks are models that help us understanding and thinking about relationships between entities in the real world. Many of these networks are dynamic, i.e. connectivity changes over time. Understanding changes in connectivity means to understand interactions between elements of complex systems; how people create and break up friendship relations, how signals get passed in the brain, how business collaborations evolve, or how food-webs restructure after environmental changes. However, understanding static networks is already difficult, due to size, density, attributes and particular motifs; changes over time very much increase this complexity. Quantification of change is often insufficient, but beyond an analysis that is driven by technology and algorithms, humans dispose a unique capability of understanding and interpreting information in data, based on vision and cognition. This dissertation explores ways to interactively explore dynamic networks by means of visualization. I develop and evaluate techniques to unfold the complexity of dynamic networks, making them understandable by looking at them from different angles, decomposing them into their parts and relating the parts in novel ways. While most techniques for dynamic network visualization rely on one particular type of view on the data, complementary visualizations allow for higher-level exploration and analysis. Covering three aspects Tasks, Visualization Design and Evaluation, I develop and evaluate the following unfolding techniques: (i) temporal navigation between individual time steps of a network and improved animated transitions to better understand changes, (ii) designs for the comparison of weighted graphs, (iii) the Matrix Cube, a space-time cube based on adjacency matrices, allowing to visualize dense dynamic networks by, as well as GraphCuisine, a system to (iv) generate synthetic networks with the primary focus on evaluating visualizations in user studies. In order to inform the design and evaluation of visualizations, we (v) provide a task taxonomy capturing users' tasks when exploring dynamic networks. Finally, (vi) the idea of unfolding networks with Matrix Cubes is generalized to other data sets that can be represented in space-time cubes (videos, geographical data, etc.). Visualizations in these domains can inspire visualizations for dynamic networks, and vice-versa. We propose a taxonomy of operations, describing how 3D space-time cubes are decomposed into a large variety of 2D visualizations. These operations help us exploring the design space for visualizing and interactively unfolding dynamic networks and other spatio-temporal data, as well as may serve users as a mental model of the data.
19
Abdulrasul, Zahraa. "Bråktal, decimaltal och procent : En kvalitativ studie om hur sambandet mellan bråktal, decimaltal och procent undervisas i årskurs 4-6." Thesis, Södertörns högskola, Lärarutbildningen, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:sh:diva-34031.
Full textAbstract:
The aim of this study is to investigate how the connection between fractions, decimals and percent are taught in grade 4-6 with more focuson the fractions. The empirical data was obtained by qualitative methods comprising interviews with four mathematic elementary school teachers, in addition to two observations with two classrooms in grade 6. The data presented is from one school. The theoretical framework is based on Liping Ma profound understanding of fundamental mathematics and theories of subject didactic concepts of Kilborn, Löwing, Karlsson & Kilborn and MacIntosh. The results of the interviews and observations show that the connection between fractions, decimals and percent is being taught without illuminating how the mentioned are connected. The aspect of fractions, which has been taught to show the relation between fractions and decimals, was division as metaphor. While there was no aspect of fractions has been taught to show the relation between it and percent except that a percent is a hundredth. Such as 40% is equal with 40/100. In addition, fractions has been taught by using visual aids, but never taught by using number line. In conclusion the connection between fractions, decimals and percent has not been related clearly with basic concept fractions.
20
Arunselvan, R. "Rainbow Connection Number Of Graph Power And Graph Products." Thesis, 2011. https://etd.iisc.ac.in/handle/2005/2383.
Full textAbstract:
The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.
21
Arunselvan, R. "Rainbow Connection Number Of Graph Power And Graph Products." Thesis, 2011. http://etd.iisc.ernet.in/handle/2005/2383.
Full textAbstract:
The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.
22
Lin, Ting Chun, and 林鼎鈞. "Implicit Connection Graph Maze Routing for Layout Migration." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/49609235325364201357.
Full textAbstract:
碩士國立清華大學
資訊工程學系
103
With advanced Very-Large-Scale Integration (VLSI) technology, migration method is more important in analog circuit or some special custom design. Sometimes two blocks in circuit will be migrated with different scale factor, and result in some connection between two blocks broken. To solve the problem described before, we propose a scanline base break point detection method that can construct the connection between polygons efficient. After compare the connection between non-sizing and sizing, we can obtain all break point what we need to route. To route the break point, an implicit connection graph base maze router is proposed, it can fully use the routing resource and get a small bend solution. As the result, our router use in layout migration method has a DRC clean solution in a real case. ii
23
Doan, Trung Duy. "Proper connection number of graphs." Doctoral thesis, 2018. https://tubaf.qucosa.de/id/qucosa%3A31245.
Full textAbstract:
The concept of \emph{proper connection number} of graphs is an extension of proper colouring and is motivated by rainbow connection number of graphs. Let $G$ be an edge-coloured graph. Andrews et al.\cite{Andrews2016} and, independently, Borozan et al.\cite{Borozan2012} introduced the concept of proper connection number as follows: A coloured path $P$ in an edge-coloured graph $G$ is called a \emph{properly coloured path} or more simple \emph{proper path} if two any consecutive edges receive different colours. An edge-coloured graph $G$ is called a \emph{properly connected graph} if every pair of vertices is connected by a proper path. The \emph{proper connection number}, denoted by $pc(G)$, of a connected graph $G$ is the smallest number of colours that are needed in order to make $G$ properly connected. Let $k\geq2$ be an integer. If every two vertices of an edge-coloured graph $G$ are connected by at least $k$ proper paths, then $G$ is said to be a \emph{properly $k$-connected graph}. The \emph{proper $k$-connection number} $pc_k(G)$, introduced by Borozan et al. \cite{Borozan2012}, is the smallest number of colours that are needed in order to make $G$ a properly $k$-connected graph.
The aims of this dissertation are to study the proper connection number and the proper 2-connection number of several classes of connected graphs. All the main results are contained in Chapter 4, Chapter 5 and Chapter 6.
Since every 2-connected graph has proper connection number at most 3 by Borozan et al. \cite{Borozan2012} and the proper connection number of a connected graph $G$ equals 1 if and only if $G$ is a complete graph by the authors in \cite{Andrews2016, Borozan2012}, our motivation is to characterize 2-connected graphs which have proper connection number 2. First of all, we disprove Conjecture 3 in \cite{Borozan2012} by constructing classes of 2-connected graphs with minimum degree $\delta(G)\geq3$ that have proper connection number 3. Furthermore, we study sufficient conditions in terms of the ratio between the minimum degree and the order of a 2-connected graph $G$ implying that $G$ has proper connection number 2. These results are presented in Chapter 4 of the dissertation.
In Chapter 5, we study proper connection number at most 2 of connected graphs in the terms of connectivity and forbidden induced subgraphs $S_{i,j,k}$, where $i,j,k$ are three integers and $0\leq i\leq j\leq k$ (where $S_{i,j,k}$ is the graph consisting of three paths with $i,j$ and $k$ edges having an end-vertex in common).
Recently, there are not so many results on the proper $k$-connection number $pc_k(G)$, where $k\geq2$ is an integer. Hence, in Chapter 6, we consider the proper 2-connection number of several classes of connected graphs. We prove a new upper bound for $pc_2(G)$ and determine several classes of connected graphs satisfying $pc_2(G)=2$. Among these are all graphs satisfying the Chv\'tal and Erd\'{o}s condition ($\alpha({G})\leq\kappa(G)$ with two exceptions). We also study the relationship between proper 2-connection number $pc_2(G)$ and proper connection number $pc(G)$ of the Cartesian product of two nontrivial connected graphs.
In the last chapter of the dissertation, we propose some open problems of the proper connection number and the proper 2-connection number.
24
Rajendraprasad, Deepak. "Rainbow Colouring and Some Dimensional Problems in Graph Theory." Thesis, 2013. https://etd.iisc.ac.in/handle/2005/3336.
Full textAbstract:
This thesis touches three different topics in graph theory, namely, rainbow colouring, product dimension and boxicity.
Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices is connected by atleast one path in which no two edges are coloured the same. The rainbow connection number of a graph is the minimum number of colours required to rainbow colour it. In this thesis we give upper bounds on rainbow connection number based on graph invariants like minimum degree, vertex connectivity, and radius. We also give some computational complexity results for special graph classes.
Product dimension The product dimension or Prague dimension of a graph G is the smallest natural number k such that G is an induced subgraph of a direct product of k complete graphs. In this thesis, we give upper bounds on the product dimension for forests, bounded tree width graphs and graphs of bounded degeneracy.
Boxicity and cubicity The boxicity (cubicity of a graph G is the smallest natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes(axis-parallel unit cubes) in Rk .In this thesis, we study the boxicity and the cubicity of Cartesian, strong and direct products of graphs and give estimates on the boxicity and the cubicity of a product graph based on invariants of the component graphs.
Separation dimension The separation dimension of a hypergraph H is the smallest natural number k for which the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyper plane normal to one of the axes. While studying the boxicity of line graphs, we noticed that a box representation of the line graph of a hypergraph has a nice geometric interpretation. Hence we introduced this new parameter and did an extensive study of the same.
25
Rajendraprasad, Deepak. "Rainbow Colouring and Some Dimensional Problems in Graph Theory." Thesis, 2013. http://etd.iisc.ernet.in/2005/3336.
Full textAbstract:
This thesis touches three different topics in graph theory, namely, rainbow colouring, product dimension and boxicity.
Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices is connected by atleast one path in which no two edges are coloured the same. The rainbow connection number of a graph is the minimum number of colours required to rainbow colour it. In this thesis we give upper bounds on rainbow connection number based on graph invariants like minimum degree, vertex connectivity, and radius. We also give some computational complexity results for special graph classes.
Product dimension The product dimension or Prague dimension of a graph G is the smallest natural number k such that G is an induced subgraph of a direct product of k complete graphs. In this thesis, we give upper bounds on the product dimension for forests, bounded tree width graphs and graphs of bounded degeneracy.
Boxicity and cubicity The boxicity (cubicity of a graph G is the smallest natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes(axis-parallel unit cubes) in Rk .In this thesis, we study the boxicity and the cubicity of Cartesian, strong and direct products of graphs and give estimates on the boxicity and the cubicity of a product graph based on invariants of the component graphs.
Separation dimension The separation dimension of a hypergraph H is the smallest natural number k for which the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyper plane normal to one of the axes. While studying the boxicity of line graphs, we noticed that a box representation of the line graph of a hypergraph has a nice geometric interpretation. Hence we introduced this new parameter and did an extensive study of the same.
26
Lai, Pei-Chun. "Causal Connection Search and Structural Demand Modeling on Retail-Level Scanner Data." Thesis, 2010. http://hdl.handle.net/1969.1/ETD-TAMU-2010-12-8922.
Full textAbstract:
Many researchers would be interested in one question: If a change of X is made, will Y be influenced in response? However, while a lot of statistical methods are developed to analyze association between variables, how to find a causal relationship among variables is relatively neglected.
The PC algorithm, developed on the basis of Pearl, Sprites, Glymour, and Scheines‟s studies, is used to find the causal pattern of the real-world observed data. However, PC in Tetrad produces a class of directed acyclic graphs (DAGs) that are statistically equivalent under a normal distribution, and therefore such a distributional assumption causes a series of unidentifiable DAGs because of the same joint probability.
In 2006 Shimizu, Hoyer, Hyvärinen, and Kerminen developed the Linear Independent Non-Gaussian Model (LiNGAM) to do a causal search based on the independently non-Gaussian distributed disturbances by applying higher-order moment structures. The research objective of this dissertation is to examine whether the LiNGAM is helpful relative to the PC algorithm, to detect the causal relation of non-normal data. The LiNGAM algorithm is implemented by first doing independent component analysis (ICA) estimation and then discovering the correct ordering of variables. Thus, the procedures of ICA estimation and the process of finding the correct causal orderings in LiNGAM are illustrated. Next, we do a causal search on the retail-level scanner data to investigate the pricing interaction between the manufacturer and the retailer by applying these two algorithms. While PC generates the set of indistinguishable DAGs, LiNGAM gives more exact causal patterns. This work demonstrates the algorithm based on the non-normal distribution assumption makes causal associations clearer. In Chapter IV, we apply a classical structural demand model to investigate the consumer purchase behavior in the carbonated soft drink market. Unfortunately, when further restrictions are imposed, we cannot get reasonable results as most researchers require. LiNGAM is applied to prove the existence of endogeneity for the brand‟s retail price and verify that the brand‟s wholesale price is not a proper instrument for its retail price. Therefore, consistent estimates cannot be derived as the theories suggest. These results imply that economic theory is not always found in restriction applied to observational data.
27
"Connection-switch box design and optimal MST-based graph algorithm on FPGA segmentation design." 2004. http://library.cuhk.edu.hk/record=b5891958.
Full textAbstract:
Zhou Lin.Thesis (M.Phil.)--Chinese University of Hong Kong, 2004.
Includes bibliographical references (leaves 50-53).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Motivation --- p.1
Chapter 1.2 --- Aims and Contribution --- p.3
Chapter 1.3 --- Thesis Overview --- p.4
Chapter 2 --- Field-Programmable Gate Array and Routing Algorithm in VPR --- p.6
Chapter 2.1 --- Commercially Available FPGAs --- p.6
Chapter 2.2 --- FPGA Logic Block Architecture --- p.7
Chapter 2.2.1 --- Logic Block Functionality vs. FPGA Area-Efficiency --- p.7
Chapter 2.2.2 --- Logic Block Functionality vs. FPGA Delay-Performance --- p.7
Chapter 2.2.3 --- Lookup Table-Based FPGAs --- p.8
Chapter 2.3 --- FPGA Routing Architecture --- p.8
Chapter 2.4 --- Design Parameters of FPGA Routing Architecture --- p.10
Chapter 2.5 --- CAD for FPGAs --- p.10
Chapter 2.5.1 --- Synthesis and Logic Block Packing --- p.11
Chapter 2.5.2 --- Placement --- p.11
Chapter 2.5.3 --- Routing --- p.12
Chapter 2.5.4 --- Delay Modelling --- p.13
Chapter 2.5.5 --- Timing Analysis --- p.13
Chapter 2.6 --- FPGA Programming Technologies --- p.13
Chapter 2.7 --- Routing Algorithm in VPR --- p.14
Chapter 2.7.1 --- Pathfinder Negotiated Congestion Algorithm --- p.14
Chapter 2.7.2 --- Routing Algorithm Used by VPR --- p.16
Chapter 3 --- Connection-Switch Box Design --- p.17
Chapter 3.1 --- Introduction --- p.17
Chapter 3.2 --- Connection-Switch Box Design Algorithm --- p.19
Chapter 3.2.1 --- Connection between Logic Pins and Tracks --- p.20
Chapter 3.2.2 --- Connection between Pad Pins and Tracks --- p.25
Chapter 3.3 --- Switch Number Comparisons --- p.26
Chapter 3.4 --- Experimental Results --- p.29
Chapter 3.5 --- Summary --- p.32
Chapter 4 --- Optimal MST-Based Graph Algorithm on FPGA Segmenta- tion Design --- p.37
Chapter 4.1 --- Introduction --- p.37
Chapter 4.2 --- MST-Based Graph Algorithm on FPGA Channel Segmentation Design --- p.39
Chapter 4.2.1 --- Net Merging Problem of Row-Based FPGAs --- p.41
Chapter 4.2.2 --- Extended Net Merging Problem of Symmetrical Array FPGAs --- p.44
Chapter 4.3 --- Experimental Results --- p.46
Chapter 4.4 --- Summary --- p.46
Chapter 5 --- Conclusions --- p.48
Bibliography --- p.50
28
LEE, CHIA-CHENG, and 李家政. "Modeling and Testing of Connection Fault Handling Behaviors in Distributed Systems with AND/OR Graph." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/6cpt5z.
Full textAbstract:
博士國立臺北科技大學
資訊工程系
107
It is very common to have an exception during a program's interactions with other programs. This thesis focus on dealing with the connection fault. The availability and reliability of a system are highly dependent on how well a system handles the exceptions. To build a robust system, the architect should provide the exception handling behaviors model of the target system, so developers have a specification to follow. This thesis makes two contributions to modeling and testing of exception handling. First, this thesis extends AND/OR graph to support the try-catch-finally construct, which is widely supported by most of the programming languages. The extension is made so we can describe the common connection fault handling behavior: communicating failure, ignoring failure, retrying with the original, and retrying with an alternative. The model is not only a specification of the system but also the input of model-based testing for generating tests to verify whether the system is consistent with the model. Second, since third-party libraries are widely used, to build a robust system, developers should understand what exception handling behaviors of the third-party application programming interface (API) they used. For this purpose, this thesis proposes to explore the connection fault handling behaviors by dynamic analysis and build a classifier by machine learning to reduce the exploration time. The result shows that the classifier has 82% true positive rate and 92.4% true negative rate.
29
Mohamed, ATEF. "Software Architecture-Based Failure Prediction." Thesis, 2012. http://hdl.handle.net/1974/7538.
Full textAbstract:
Depending on the role of software in everyday life, the cost of a software failure can sometimes be unaffordable. During system execution, errors may occur in system components and failures may be manifested due to these errors. These errors differ with respect to their effects on system behavior and consequent failure manifestation manners. Predicting failures before their manifestation is important to assure system resilience. It helps avoid the cost of failures and enables systems to perform corrective actions prior to failure occurrences. However, effective runtime error detection and failure prediction techniques encounter a prohibitive challenge with respect to the control flow representation of large software systems with intricate control flow structures. In this thesis, we provide a technique for failure prediction from runtime errors of large software systems. Aiming to avoid the possible difficulties and inaccuracies of the existing Control Flow Graph (CFG) structures, we first propose a Connection Dependence Graph (CDG) for control flow representation of large software systems. We describe the CDG structure and explain how to derive it from program source code. Second, we utilize the proposed CDG to provide a connection-based signature approach for control flow error detection. We describe the monitor structure and present the error checking algorithm. Finally, we utilize the detected errors and erroneous state parameters to predict failure occurrences and modes during system runtime. We craft runtime signatures based on these errors and state parameters. Using system error and failure history, we determine a predictive function (an estimator) for each failure mode based on these signatures. Our experimental evaluation for these techniques uses a large open-source software (PostgreSQL 8.4.4 database system). The results show highly efficient control flow representation, error detection, and failure prediction techniques. This work contributes to software reliability by providing a simple and accurate control flow representation and utilizing it to detect runtime errors and predict failure occurrences and modes with high accuracy.Thesis (Ph.D, Computing) -- Queen's University, 2012-09-25 23:44:12.356
30
Chen, Hsin-Yu, and 陳新育. "Nemo: A New Implicit Connection Graph-Based Gridless Router with Multi-Layer Planes and Pseudo-Tile Propagation." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/56450206679083813229.
Full textAbstract:
碩士國立交通大學
資訊科學系所
94
This study presents a new multilayer implicit connection graph-based gridless router called NEMO. Unlike the first implicit connection graph-based router that embeds all routing layers onto a routing plane, NEMO constructs a routing plane for each routing layer. Furthermore, each routing plane is composed of tiles, not an array of grid points as well as their connecting edges, and, consequently, the complexity of routing problem decreases. Each grid then exactly represents one tile (its left bottom corner), and grid maze becomes tile propagation; moreover, to further speedup in path searching, continuous space tiles are combined as a pseudo maximum horizontally or vertically stripped tile. Experimental results indicate that NEMO conducts point-to-point path searching on about 10 times faster than the implicit connection graph-based router. Full-chip routing by NEMO also outperforms all multi-level gridless routing with about twofold to fivefold speedup.
31
Yung-Shiang, Ho. "Connection Estimate on Minimal Graphs." 2006. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0001-2706200614034300.
Full text
32
Ho, Yung-Shiang, and 何永翔. "Connection Estimate on Minimal Graphs." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/64421080235060919076.
Full textAbstract:
碩士國立臺灣大學
數學研究所
94
In this paper,We prove that if the minimal surface Sigma^2 contains in R^3 is a graph, then there exists an orthonormal frame such that the norm of Levi-Civita connection one form defined on this frame has an upper bound -K which is the Guassian curvature.With this upper bound, we can find another prove on the theorem of Bernstein.
33
余和哲. "Wire Re-connections Based on Implication Flow Graph." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/54086848791699663884.
Full textAbstract:
碩士國立中正大學
資訊工程研究所
89
ATPG based synthesis algorithms[2][3][4][5][6][8][9][10][13][15] have been very popular because of low memory usage and their ability to consider implicit don’t cares during optimization. Although the objectives of ATPG synthesis algorithms can be different, most ATPG algorithms perform optimization by adding and removing redundant connections. Unlike other algorithms to add one wire and then remove others, the Global Flow Optimization (GFO) algorithm can add and remove many wires at the same time. Basically, there are two types of GFO, one performs the fanout re-connection and the other performs the fanin re-connection. The fanout GFO re-connects the fanouts of a node to the inputs of other nodes while the fanin GFO re-connects the fanins of a node from the outputs of other nodes. The GFO algorithm models the problem of the fanout/fanin re-connections by a flow graph and then solves the problem using the maxflow-mincut algorithm on the flow graph. However, the flow graph cannot fully characterize the wire re-connections that cause GFO to lose optimality on several obvious cases. In addition, we find that the fanin re-connection can have more optimization power than the fanout re-connection but requires more sophisticated modeling. In this paper, we re-formulate the problem of the fanout/fanin re-connections by a new graph called the implication flow graph. We show that the problem of wire re-connections on the implication flow graph is NP complete and also propose an efficient heuristic on the new graph. Our experimental results are very exciting.
34
Liang, Yu-Jung, and 梁育榮. "Rainbow connection numbers of Cartesian product of graphs." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/4xzvg3.
Full textAbstract:
碩士國立東華大學
應用數學系
100
Given a connected graph G together with a coloring f from the edge set of G to a set of colors, where adjacent edges may be colored the same, a u-v path P in G is said to be a rainbow path if no two edges of P are colored the same. A u-v path P in G is said to be a rainbow u-v geodesic in G if P is a rainbow u-v path whose length equals to the distance of u and v. The graph G is rainbow-connected(resp., strongly rainbow-connected) if G contains a rainbow u-v path(resp,. rainbow u-v geodesic) for every two vertices u and v of G. In this case, the coloring f is called a rainbow coloring(resp,. strong rainbow coloring) of G. A rainbow coloring(resp., strong rainbow coloring) of G using k colors is a rainbow k-coloring(resp., strong rainbow k-coloring) of G. The minimum k for which there exists a rainbow k-coloring(resp., strong rainbow k-coloring) of G is called the rainbow connection number(resp., strong rainbow connection number) of G and is denoted by rc(G)(resp., src(G)). We study the rainbow connection numbers and the strong rainbow connection numbers of Cartesian product of graphs, where both of the two graphs are in F={G:G is a path, a cycle, or a complete graph}, or both of the two graphs are in T={T:T is a tree}, in this thesis. We show that if G is the Cartesian product of two graphs G₁ and G₂, in F, then diam(G)=rc(G)=src(G), except that both G₁ and G₂ are odd cycles. And we prove that if G is the Cartesian product of two trees T₁ and T₂, then rc(G)=diam(G), except that T₂ is the path P₂, and T₁ satisfies some special conditions, in which case the rainbow connection number of G equals diam(G)+1.
35
Silva, André Filipe Freitas da. "A representação gráfica na aprendizagem de tópicos de funções de alunos do 10º ano." Master's thesis, 2019. http://hdl.handle.net/1822/62139.
Full textAbstract:
Relatório de estágio de mestrado em Ensino de Matemática no 3.º ciclo do Ensino Básico e no Ensino SecundárioEste estudo pretende averiguar o contributo da representação gráfica na aprendizagem de tópicos de funções de alunos do 10.º ano. Para a concretização desse objetivo foram formuladas as seguintes questões de investigação: (1) Como os alunos utilizam a representação gráfica nas atividades de aprendizagem de tópicos de funções? (2) Que dificuldades manifestam os alunos na aprendizagem de tópicos de funções através da representação gráfica? (3) Que perceções têm os alunos sobre a representação gráfica na aprendizagem de tópicos de funções? Para dar resposta a estas questões foram utilizados vários métodos de recolha de dados: ficha de diagnóstico, gravações áudio e vídeo, produções dos alunos, questionários (inicial e final) e questões do teste de avaliação. A intervenção pedagógica foi realizada numa turma do 10.º ano de uma escola da cidade de Braga. As minhas principais preocupações na dinamização das atividades de ensino e de aprendizagem foram as tarefas, o ensino exploratório, o modelo de Joyce e Weil e a utilização de materiais tecnológicos. Os resultados obtidos mostram que a representação gráfica foi essencialmente utilizada pelos alunos na verificação de resultados obtidos analiticamente ou na resolução gráfica de tarefas. Os alunos também utilizaram a representação gráfica para escolherem o método de resolução analítico de tarefas. A representação gráfica foi utilizada também como prova (contraexemplo) e como forma de resolver conflitos entre soluções obtidas analiticamente e algumas das suas ideias intuitivas. Os alunos utilizaram também esta representação para estabelecer definições e propriedades de conceitos sobre funções. Os alunos apresentaram diversas dificuldades na interpretação e na construção de gráficos. Uma destas dificuldades está associada à identificação de funções em relações representadas por diferentes tipos de representação, onde os alunos apresentam mais dificuldades quando estas relações são representadas por gráficos. Os alunos também têm dificuldades em identificar imagens e imagens inversas em gráficos de funções, em representar determinas características gráficas de funções associadas a alguns conceitos abordados e na escolha da janela de visualização na calculadora gráfica. Os alunos fazem confusão entre intervalo e ponto e por vezes não percebem os próprios gráficos que representam. As perceções dos alunos sobre a representação gráfica na aprendizagem de tópicos de funções destacam o seu contributo na sua aprendizagem, referindo que melhoraram a interpretação e a construção de gráficos e que permitiu compreender e estabelecer definições e propriedades.
This study intends to investigate the contribution of graphical representation in learning of functions topics of students of the10th year. To achieve this goal, the following research questions were formulated: (1) How do students use graphical representation in the learning activities of functions topics? (2)What difficulties do students manifest in learning of functions topics through graphical representation? (3)What are the perceptions that students have about the graphical representation in learning of function topics? To find answers to these questions were used several methods of data collection: diagnostic test, audio and video recording, students’ productions, questionnaires (initial and final) and questions of evaluation test. The pedagogical intervention was carried out in a class of the 10th year of a school in the city of Braga. My main concerns in the dynamism of teaching and learning activities were the tasks, exploratory teaching, the Joyce and Weil model and the use of technological materials. The results show that the graphical representation was mainly used by the students in the verification of the results obtained analytically or in the graphical resolution of tasks. Students also used the graphical representation to choose the method of analytical resolution of tasks. The graphical representation was also used as proof (counterexample)and as a way of solving conflicts between analytical solutions and some of their intuitive ideas. The students also used this representation to establish definitions and properties of concepts about functions. The students presented several difficulties in the interpretation and construction of graphs. One of these difficulties is associated to the identification of functions in relations represented by different types of representation, where students present more difficulties when these relations are represented by graphs. Students also have difficulties in identifying images and inverse images in function graphs, in representing determined graphic characteristics of functions associated to some concepts covered and in choosing the visualization window in the graphing calculator. Students make confusion between interval and point and sometimes do not understand the graphs that they themselves drew. The students' perceptions about the graphical representation in the learning of function topics high light their contribution in their learning, noting that they improved the interpretation and the construction of graphs and that allowed to understand and to establish definitions and properties.
36
Hahmann, Torsten. "Model-Theoretic Analysis of Asher and Vieu's Mereotopology." Thesis, 2008. http://hdl.handle.net/1807/10432.
Full textAbstract:
In the past little work has been done to characterize the models of various mereotopological systems. This thesis focuses on Asher and Vieu's first-order mereotopology which evolved from Clarke's Calculus of Individuals. Its soundness and completeness proofs with respect to a topological translation of the axioms provide only sparse insights into structural properties of the mereotopological models. To overcome this problem, we characterize these models with respect to mathematical
structures with well-defined properties - topological spaces, lattices, and graphs.
We prove that the models of the subtheory RT− are isomorphic to p-ortholattices
(pseudocomplemented, orthocomplemented). Combining the advantages of lattices
and graphs, we show how Cartesian products of finite p-ortholattices with one multiplicand being not uniquely complemented (unicomplemented) gives finite models of the full mereotopology. Our analysis enables a comparison to other mereotopologies, in particular to the RCC, of which lattice-theoretic characterizations exist.