To see the other types of publications on this topic, follow the link: Simple graph.
Dissertations / Theses on the topic 'Simple graph'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 42 dissertations / theses for your research on the topic 'Simple 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
CRUCIANI, EMILIO. "Simple Randomized Distributed Algorithms for Graph Clustering." Doctoral thesis, Gran Sasso Science Institute, 2019. http://hdl.handle.net/20.500.12571/9951.
Full textAbstract:
Label Propagation Algorithms are a class of heuristics for the problem of graph clustering, i.e., the problem of detecting groups of nodes whose connections are dense within each group and sparse between the groups. At the onset, a label is assigned to each node of the graph; then, each node iteratively updates its label according to a function of the labels of its neighbors. Empirical studies show that, after only a few rounds, nodes in the same cluster share the same label while nodes in different clusters have different labels. Although they are widely used in practice given their simplicity, efficiency, and effectiveness, there is no theoretical foundation to explain why such simple algorithms are able to perform such a hard task. The absence of theoretical progress in the analysis of Label Propagation Algorithms is due to the lack of mathematical techniques for handling the interplay between the non-linearity of their update rule and the topology of the underlying graph.
In this thesis we contextualize Label Propagation Algorithms in the framework of computational dynamics, simple dynamical processes on networks whose behavior has been formally characterized on some classes of graphs. The analyses of computational dynamics were mainly focused on graphs with good connectivity properties, such as cliques or expanders, and on the problem of consensus, showing that they naturally converge to a configuration in which all the nodes agree on some value. We move a step forward in this direction by rigorously analyzing two simple dynamics, the 2-Choices dynamics and the Averaging dynamics, reaching a more fine-grained comprehension of their consensus behavior in classes of graphs that exhibit a clustered structure. In particular we formally prove that, with non-negligible probability, the two dynamics quickly bring the graph in a configuration where each cluster reaches an internal consensus on a value that is different among the clusters, and then enters a long metastable phase in which the internal consensus are maintained.
We show how to exploit such metastable behavior to design simple randomized distributed algorithms for graph clustering.
2
Matos, Jody Maick Araujo de. "Graph based algorithms to efficiently map VLSI circuits with simple cells." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2018. http://hdl.handle.net/10183/174523.
Full textAbstract:
Essa tese introduz um conjunto de algoritmos baseados em grafos para o mapeamento eficiente de circuitos VLSI com células simples. Os algoritmos propostos se baseiam em minimizar de maneira eficiente o número de elementos lógicos usados na implementação do circuito. Posteriormente, uma quantidade significativa de esforço é aplicada na minimização do número de inversores entre esses elementos lógicos. Por fim, essa representação lógica é mapeada para circuitos compostos somente por células NAND e NOR de duas entradas, juntamente com inversores. Células XOR e XNOR de duas entradas também podem ser consideradas. Como nós também consideramos circuitos sequenciais, flips-flops também são levados em consideração. Com o grande esforço de minimização de elementos lógicos, o circuito gerado pode conter algumas células com um fanout impraticável para os nodos tecnológicos atuais. Para corrigir essas ocorrências, nós propomos um algoritmo de limitação de fanout que considera tanto a área sendo utilizada pelas células quanto a sua profundidade lógica. Os algoritmos propostos foram aplicados sobre um conjunto de circuitos de benchmark e os resultados obtidos demonstram a utilidade dos métodos. Essa tese introduz um conjunto de algoritmos baseados em grafos para o mapeamento eficiente de circuitos VLSI com células simples. Os algoritmos propostos se baseiam em minimizar de maneira eficiente o número de elementos lógicos usados na implementação do circuito. Posteriormente, uma quantidade significativa de esforço é aplicada na minimização do número de inversores entre esses elementos lógicos. Por fim, essa representação lógica é mapeada para circuitos compostos somente por células NAND e NOR de duas entradas, juntamente com inversores. Células XOR e XNOR de duas entradas também podem ser consideradas. Como nós também consideramos circuitos sequenciais, flips-flops também são levados em consideração. Com o grande esforço de minimização de elementos lógicos, o circuito gerado pode conter algumas células com um fanout impraticável para os nodos tecnológicos atuais. Para corrigir essas ocorrências, nós propomos um algoritmo de limitação de fanout que considera tanto a área sendo utilizada pelas células quanto a sua profundidade lógica. Os algoritmos propostos foram aplicados sobre um conjunto de circuitos de benchmark e os resultados obtidos demonstram a utilidade dos métodos. Adicionalmente, algumas aplicações Morethan-Moore, tais como circuitos baseados em eletrônica impressa, também podem ser beneficiadas pela abordagem proposta.This thesis introduces a set of graph-based algorithms for efficiently mapping VLSI circuits using simple cells. The proposed algorithms are concerned to, first, effectively minimize the number of logic elements implementing the synthesized circuit. Then, we focus a significant effort on minimizing the number of inverters in between these logic elements. Finally, this logic representation is mapped into a circuit comprised of only two-input NANDs and NORS, along with the inverters. Two-input XORs and XNORs can also be optionally considered. As we also consider sequential circuits in this work, flip-flops are taken into account as well. Additionally, with high-effort optimization on the number of logic elements, the generated circuits may contain some cells with unfeasible fanout for current technology nodes. In order to fix these occurrences, we propose an area-oriented, level-aware algorithm for fanout limitation. The proposed algorithms were applied over a set of benchmark circuits and the obtained results have shown the usefulness of the method. We show that efficient implementations in terms of inverter count, transistor count, area, power and delay can be generated from circuits with a reduced number of both simple cells and inverters, combined with XOR/XNOR-based optimizations. The proposed buffering algorithm can handle all unfeasible fanout occurrences, while (i) optimizing the number of added inverters; and (ii) assigning cells to the inverter tree based on their level criticality. When comparing with academic and commercial approaches, we are able to simultaneously reduce the average number of inverters, transistors, area, power dissipation and delay up to 48%, 5%, 5%, 5%, and 53%, respectively. As the adoption of a limited set of simple standard cells have been showing benefits for a variety of modern VLSI circuits constraints, such as layout regularity, routability constraints, and/or ultra low power constraints, the proposed methods can be of special interest for these applications. Additionally, some More-than-Moore applications, such as printed electronics designs, can also take benefit from the proposed approach.
3
Bereczki, Márk. "Graph Neural Networks for Article Recommendation based on Implicit User Feedback and Content." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-300092.
Full textAbstract:
Recommender systems are widely used in websites and applications to help users find relevant content based on their interests. Graph neural networks achieved state- of-the- art results in the field of recommender systems, working on data represented in the form of a graph. However, most graph- based solutions hold challenges regarding computational complexity or the ability to generalize to new users. Therefore, we propose a novel graph- based recommender system, by modifying Simple Graph Convolution, an approach for efficient graph node classification, and add the capability of generalizing to new users. We build our proposed recommender system for recommending the articles of Peltarion Knowledge Center. By incorporating two data sources, implicit user feedback based on pageview data as well as the content of articles, we propose a hybrid recommender solution. Throughout our experiments, we compare our proposed solution with a matrix factorization approach as well as a popularity- based and a random baseline, analyse the hyperparameters of our model, and examine the capability of our solution to give recommendations to new users who were not part of the training data set. Our model results in slightly lower, but similar Mean Average Precision and Mean Reciprocal Rank scores to the matrix factorization approach, and outperforms the popularity- based and random baselines. The main advantages of our model are computational efficiency and its ability to give relevant recommendations to new users without the need for retraining the model, which are key features for real- world use cases.Rekommendationssystem används ofta på webbplatser och applikationer för att hjälpa användare att hitta relevant innehåll baserad på deras intressen. Med utvecklingen av grafneurala nätverk nådde toppmoderna resultat inom rekommendationssystem och representerade data i form av en graf. De flesta grafbaserade lösningar har dock svårt med beräkningskomplexitet eller att generalisera till nya användare. Därför föreslår vi ett nytt grafbaserat rekommendatorsystem genom att modifiera Simple Graph Convolution. De här tillvägagångssätt är en effektiv grafnodsklassificering och lägga till möjligheten att generalisera till nya användare. Vi bygger vårt föreslagna rekommendatorsystem för att rekommendera artiklarna från Peltarion Knowledge Center. Genom att integrera två datakällor, implicit användaråterkoppling baserad på sidvisningsdata samt innehållet i artiklar, föreslår vi en hybridrekommendatörslösning. Under våra experiment jämför vi vår föreslagna lösning med en matrisfaktoriseringsmetod samt en popularitetsbaserad och en slumpmässig baslinje, analyserar hyperparametrarna i vår modell och undersöker förmågan hos vår lösning att ge rekommendationer till nya användare som inte deltog av träningsdatamängden. Vår modell resulterar i något mindre men liknande Mean Average Precision och Mean Reciprocal Rank poäng till matrisfaktoriseringsmetoden och överträffar de popularitetsbaserade och slumpmässiga baslinjerna. De viktigaste fördelarna med vår modell är beräkningseffektivitet och dess förmåga att ge relevanta rekommendationer till nya användare utan behov av omskolning av modellen, vilket är nyckelfunktioner för verkliga användningsfall.
4
Kaykobad, M. Tanvir. "Transforming Plane Triangulations by Simultaneous Diagonal Flips." Thesis, Université d'Ottawa / University of Ottawa, 2020. http://hdl.handle.net/10393/40499.
Full textAbstract:
We explore the problem of transforming plane triangulations using simultaneous
diagonal flips. Wagner showed that any n-vertex plane triangulation can be transformed to any other plane triangulation on equal number of vertices using a finite
sequence of diagonal flips. Later on it has been established that O(n) individual flips
suffice to complete this transformation. Bose et al. showed that the transformation
can also be done in 4 × (
2 /
log 54/53
+ 2 /
log 6/5
) logn + 2 ≈ 327.1 log n simultaneous flips. This
bound is asymptotically tight.
We present two algorithms to improve the leading coefficient of this bound for
transforming any plane triangulation into any other. The first of the two algorithms
lowers this bound down to 4 × (
2 /
log 12/11
+ 2 /
log 9/7
) logn + 2 ≈ 85.8 log n. By processing
and preprocessing the interior and exterior of the triangulation’s Hamiltonian cycle
parallelly in an interlaced fashion, we make further improvement of the algorithm
from ≈ 327.1 log n down to 12 /
log 6/5
logn + 2 ≈ 45.6 log n.
5
Islam, Md Kamrul. "Explainable link prediction in large complex graphs - application to drug repurposing." Electronic Thesis or Diss., Université de Lorraine, 2022. http://www.theses.fr/2022LORR0203.
Full textAbstract:
De nombreux systèmes complexes du monde réel peuvent être représentés par des graphes, où les nœuds représentent des entités et les liens des relations entre les paires de nœuds. La prédiction de liens (LP) est l'un des problèmes les plus intéressants et les plus anciens dans le domaine de l'exploration de graphes ; elle prédit la probabilité d'un lien entre deux nœuds non connectés. Cette thèse étudie le problème LP dans les graphes simples et les graphes de connaissances (KGs). La première partie de cette thèse se concentre sur le problème LP dans les graphes simples. Dans la première étude, des approches basées sur la similarité et sur l'encastrement sont évaluées et comparées sur des graphes simples de différents domaines. L'étude a également identifié la difficulté de fixer le seuil du score de similarité pour calculer la métrique de précision des approches basées sur la similarité et a proposé une nouvelle méthode pour calculer la métrique. Les résultats ont montré la supériorité attendue des approches basées sur l'intégration. Cependant, chaque approche basée sur la similarité s'est avérée compétitive sur des graphes aux propriétés spécifiques. Nous avons pu vérifier expérimentalement que les approches basées sur la similarité sont explicables mais manquent de généralisation, tandis que les approches basées sur l'encastrement sont générales mais non explicables. La deuxième étude tente de surmonter la limitation de l'inexplicabilité des approches basées sur l'encastrement en découvrant des connexions intéressantes entre elles et les approches basées sur la similarité. La troisième étude démontre comment les approches basées sur la similarité peuvent être assemblées pour concevoir une approche LP supervisée explicable. Il est intéressant de noter que l'étude montre des performances LP élevées pour l'approche supervisée sur différents graphes, ce qui est très satisfaisant. La deuxième partie de la thèse se concentre sur les LP dans les KGs. Un KG est représenté comme une collection de triplets RDF, (head,relation,tail) où les entités head et tail sont reliées par une relation spécifique. Le problème de LP dans un KG est formulé comme la prédiction de la tête ou de la queue manquante dans un triplet. La LP basée sur l'incorporation de KG est devenue très populaire ces dernières années, et la génération de triplets négatifs est une tâche importante dans les méthodes d'incorporation. La quatrième étude traite d'une nouvelle méthode appelée SNS pour générer des triplets négatifs de haute qualité. Nos résultats montrent une meilleure performance LP lorsque SNS est utilisé que lorsque d'autres méthodes d'échantillonnage négatif sont utilisées. La deuxième étude traite d'une nouvelle méthode d'extraction de règles neuro-symboliques et d'une stratégie d'abduction pour expliquer les LP par une approche basée sur l'intégration en utilisant les règles apprises. La troisième étude applique notre LP explicable pour développer une nouvelle approche de repositionnement des médicaments pour COVID-19. L'approche apprend un ensemble d'enchâssements d'entités et de relations dans un KG centré sur COVID-19 pour obtenir un meilleur enchâssement des éléments du graphe. Pour la première fois à notre connaissance, des méthodes de criblage virtuel sont ensuite utilisées pour évaluer les prédictions obtenues à l'aide des embeddings. L'évaluation moléculaire et les chemins explicatifs apportent de la fiabilité aux résultats de prédiction et sont de nouvelles méthodes complémentaires et réutilisables pour mieux évaluer les molécules proposées pour le repositionnement. La dernière étude propose une architecture distribuée pour l'apprentissage des KG embeddings dans des environnements distribués et parallèles. Les résultats révèlent que l'apprentissage dans l'environnement distribué proposé, par rapport à un apprentissage centralisé, réduit considérablement le temps de calcul des méthodes d'incorporation KG sans affecter les performances des LPMany real-world complex systems can be well-represented with graphs, where nodes represent objects or entities and links/relations represent interactions between pairs of nodes. Link prediction (LP) is one of the most interesting and long-standing problems in the field of graph mining; it predicts the probability of a link between two unconnected nodes based on available information in the current graph. This thesis studies the LP problem in graphs. It consists of two parts: LP in simple graphs and LP knowledge graphs (KGs). In the first part, the LP problem is defined as predicting the probability of a link between a pair of nodes in a simple graph. In the first study, a few similarity-based and embedding-based LP approaches are evaluated and compared on simple graphs from various domains. he study also criticizes the traditional way of computing the precision metric of similarity-based approaches as the computation faces the difficulty of tuning the threshold for deciding the link existence based on the similarity score. We proposed a new way of computing the precision metric. The results showed the expected superiority of embedding-based approaches. Still, each of the similarity-based approaches is competitive on graphs with specific properties. We could check experimentally that similarity-based approaches are fully explainable but lack generalization due to their heuristic nature, whereas embedding-based approaches are general but not explainable. The second study tries to alleviate the unexplainability limitation of embedding-based approaches by uncovering interesting connections between them and similarity-based approaches to get an idea of what is learned in embedding-based approaches. The third study demonstrates how the similarity-based approaches can be ensembled to design an explainable supervised LP approach. Interestingly, the study shows high LP performance for the supervised approach across various graphs, which is competitive with embedding-based approaches.The second part of the thesis focuses on LP in KGs. A KG is represented as a collection of RDF triples, (head,relation,tail) where the head and the tail are two entities which are connected by a specific relation. The LP problem in a KG is formulated as predicting missing head or tail entities in a triple. LP approaches based on the embeddings of entities and relations of a KG have become very popular in recent years, and generating negative triples is an important task in KG embedding methods. The first study in this part discusses a new method called SNS to generate high-quality negative triples during the training of embedding methods for learning embeddings of KGs. The results we produced show better LP performance when SNS is injected into an embedding approach than when injecting state-of-the-art negative triple sampling methods. The second study in the second part discusses a new neuro-symbolic method of mining rules and an abduction strategy to explain LP by an embedding-based approach utilizing the learned rules. The third study applies the explainable LP to a COVID-19 KG to develop a new drug repurposing approach for COVID-19. The approach learns ”ensemble embeddings” of entities and relations in a COVID-19 centric KG, in order to get a better latent representation of the graph elements. For the first time to our knowledge, molecular docking is then used to evaluate the predictions obtained from drug repurposing using KG embedding. Molecular evaluation and explanatory paths bring reliability to prediction results and constitute new complementary and reusable methods for assessing KG-based drug repurposing. The last study proposes a distributed architecture for learning KG embeddings in distributed and parallel settings. The results of the study that the computational time of embedding methods improves remarkably without affecting LP performance when they are trained in the proposed distributed settings than the traditional centralized settings
6
Lehbab, Imène. "Problèmes métriques dans les espaces de Grassmann." Electronic Thesis or Diss., Mulhouse, 2023. http://www.theses.fr/2023MULH6508.
Full textAbstract:
Il s'agit d'une contribution dans le domaine de la géométrie métrique du plan projectif complexe CP2 et de la variété de Grassmann réelle des plans dans R6. On s'intéresse à l'étude de tous les p-uplets, p ≥ 3, de droites équiangulaires dans C3 et des p-uplets de plans équi-isoclins dans R6. Sachant que 9 est le nombre maximum de droites équiangulaires que l'on peut construire dans C3, on décrit une méthode qui permet de construire tous les p-uplets de droites équiangulaires pour tout pϵ[3,9]. En particulier, on construit dans C3 cinq classes de congruence de quadruplets de droites équiangulaires dont une dépend d'un paramètre réel ɣ que l'on étend à une famille infinie de sextuplets de droites équiangulaires dépendant du même paramètre réel ɣ. En outre, on donne les angles pour lesquels nos sextuplets s'étendent au-delà et jusqu'aux 9-uplets. On sait qu'il existe un p-uplet, p≥3, de plans équi-isoclins engendrant Rr, r≥4, de paramètre c, 0This work contributes to the field of metric geometry of the complex projective plane CP2 and the real Grassmannian manifold of the planes in R6. More specifically, we study all p-tuples, p ≥ 3, of equiangular lines in C3 or equidistant points in CP2, and p-tuples of equi-isoclinic planes in R6. Knowing that 9 is the maximum number of equiangular lines that can be constructed in C3, we develop a method to obtain all p-tuples of equiangular lines for all p ϵ [3,9]. In particular, we construct in C3 five congruence classes of quadruples of equiangular lines, one of which depends on a real parameter ɣ, which we extend to an infinite family of sextuples of equiangular lines depending on the same real parameter ɣ. In addition, we give the angles for which our sextuples extend beyond and up to 9-tuples. We know that there exists a p-tuple, p ≥ 3, of equi-isoclinic planes generating Rr, r ≥ 4, with parameter c, 0< c <1, if and only if there exists a square symmetric matrix, called Seidel matrix, of p × p square blocks of order 2, whose diagonal blocks are all zero and the others are orthogonal matrices in O(2) and whose smallest eigenvalue is equal to - 1/c and has multiplicity 2p-r. In this thesis, we investigate the case r=6 and we also show that we can explicitly determine the spectrum of all Seidel matrices of order 2p, p ≥ 3 whose off-diagonal blocks are in {R0, S0} where R0 and S0 are respectively the zero-angle rotation and the zero-angle symmetry. We thus show an unexpected link between some p-tuples of equi-isoclinic planes in Rr and simple graphs of order p
7
Montanaro, William M. Jr. "Character Degree Graphs of Almost Simple Groups." Kent State University / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=kent1398345504.
Full text
8
Soames, Kieron, and Jonas Lind. "Detecting Cycles in GraphQL Schemas." Thesis, Linköpings universitet, Institutionen för datavetenskap, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-156174.
Full textAbstract:
GraphQL is a database handling API created by Facebook, that provides an effective al-ternative to REST-style architectures. GraphQL provides the ability for a client to spec-ify exactly what data it wishes to receive. A problem with GraphQL is that the freedomof creating customized requests allows data to be included several times in the response,growing the response’s size exponentially. The thesis contributes to the field of GraphQLanalysis by studying the prevalence of simple cycles in GraphQL schemas. We have im-plemented a locally-run tool and webtool using Tarjan’s and Johnson’s algorithms, thatparses the schemas, creates a directed graph and enumerates all simple cycles in the graph.A collection of schemas was analysed with the tool to collect empirical data. It was foundthat 39.73 % of the total 2094 schemas contained at least one simple cycle, with the averagenumber of cycles per schema being 4. The runtime was found to be on average 11 mil-liseconds, most of which consisted of the time for parsing the schemas. It was found that44 out of the considered schemas could not be enumerated due to containing a staggeringamount of simple cycles. It can be concluded that it is possible to test schemas for cyclicityand enumerate all simple cycles in a given schema efficiently.
9
Yan, Chenyu. "APPROXIMATING DISTANCES IN COMPLICATED GRAPHS BY DISTANCES IN SIMPLE GRAPHS WITH APPLICATIONS." Kent State University / OhioLINK, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=kent1184639623.
Full text
10
Okeke, Nnamdi, and University of Lethbridge Faculty of Arts and Science. "Character generators and graphs for simple lie algebras." Thesis, Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2006, 2006. http://hdl.handle.net/10133/532.
Full textAbstract:
We study character generating functions (character generators) of simple Lie algebras. The
expression due to Patera and Sharp, derived from the Weyl character formula, is ¯rst re-
viewed. A new general formula is then found. It makes clear the distinct roles of \outside"
and \inside" elements of the integrity basis, and helps determine their quadratic incompati-
bilities. We review, analyze and extend the results obtained by Gaskell using the Demazure
character formulas. We ¯nd that the fundamental generalized-poset graphs underlying the
character generators can be deduced from such calculations. These graphs, introduced by
Baclawski and Towber, can be simpli¯ed for the purposes of constructing the character
generator. The generating functions can be written easily using the simpli¯ed versions,
and associated Demazure expressions. The rank-two algebras are treated in detail, but we
believe our results are indicative of those for general simple Lie algebras.vii, 92 leaves ; 29 cm.
11
Mahfoudh, Mariem. "Adaptation d'ontologies avec les grammaires de graphes typés : évolution et fusion." Thesis, Mulhouse, 2015. http://www.theses.fr/2015MULH1519/document.
Full textAbstract:
Étant une représentation formelle et explicite des connaissances d'un domaine, les ontologies font régulièrement l'objet de nombreux changements et ont ainsi besoin d'être constamment adaptées pour notamment pouvoir être réutilisées et répondre aux nouveaux besoins. Leur réutilisation peut prendre différentes formes (évolution, alignement, fusion, etc.), et présente plusieurs verrous scientifiques. L'un des plus importants est la préservation de la consistance de l'ontologie lors de son changement. Afin d'y répondre, nous nous intéressons dans cette thèse à étudier les changements ontologiques et proposons un cadre formel capable de faire évoluer et de fusionner des ontologies sans affecter leur consistance. Premièrement, nous proposons TGGOnto (Typed Graph Grammars for Ontologies), un nouveau formalisme permettant la représentation des ontologies et leurs changements par les grammaires de graphes typés. Un couplage entre ces deux formalismes est défini afin de profiter des concepts des grammaires de graphes, notamment les NAC (Negative Application Conditions), pour la préservation de la consistance de l'ontologie adaptée.Deuxièmement, nous proposons EvOGG (Evolving Ontologies with Graph Grammars), une approche d'évolution d'ontologies qui se base sur le formalisme GGTOnto et traite les inconsistances d'une manière a priori. Nous nous intéressons aux ontologies OWL et nous traitons à la fois : (1) l'enrichissement d'ontologies en étudiant leur niveau structurel et (2) le peuplement d'ontologies en étudiant les changements qui affectent les individus et leurs assertions. L'approche EvOGG définit des changements ontologiques de différents types (élémentaires, composées et complexes) et assure leur implémentation par l'approche algébrique de transformation de graphes, SPO (Simple PushOut). Troisièmement, nous proposons GROM (Graph Rewriting for Ontology Merging), une approche de fusion d'ontologies capable d'éviter les redondances de données et de diminuer les conflits dans le résultat de fusion. L'approche proposée se décompose en trois étapes : (1) la recherche de similarité entre concepts en se basant sur des techniques syntaxiques, structurelles et sémantiques ; (2) la fusion d'ontologies par l'approche algébrique SPO ; (3) l'adaptation de l'ontologie globale résultante par le biais des règles de réécriture de graphes.Afin de valider les travaux menés dans cette thèse, nous avons développé plusieurs outils open source basés sur l'outil AGG (Attributed Graph Grammar). Ces outils ont été appliqués sur un ensemble d'ontologies, essentiellement sur celles développées dans le cadre du projet européen CCAlps (Creatives Companies in Alpine Space) qui a financé les travaux de cette thèseOntologies are a formal and explicit knowledge representation. They represent a given domain by their concepts and axioms while creating a consensus between a user community. To satisfy the new requirements of the represented domain, ontologies have to be regularly updated and adapted to maintain their consistency. The adaptation may take different forms (evolution, alignment, merging, etc.), and represents several scientific challenges. One of the most important is to preserve the consistency of the ontology during the changes. To address this issue, we are interested in this thesis to study the ontology changes and we propose a formal framework that can evolve and merge ontologies without affecting their consistency.First we propose TGGOnto (Typed Graph Grammars for Ontologies), a new formalism for the representation of ontologies and their changes using typed graph grammars (TGG). A coupling between ontologies and TGG is defined in order to take advantage of the graph grammars concepts, such as the NAC (Negative Application Conditions), in preserving the adapted ontology consistency. Second, we propose EvOGG (Evolving Ontologies with Graph Grammars), an ontology evolution approach that is based on the TGGOnto formalism that avoids inconsistencies using an a priori approach. We focus on OWL ontologies and we address both : (1) ontology enrichment by studying their structural level and (2) ontology population by studying the changes affecting individuals and their assertions. EvOGG approach defines different types of ontology changes (elementary, composite and complex) and ensures their implementation by the algebraic approach of graph transformation, SPO (Single pushout).Third, we propose GROM (Graph Rewriting for Ontology Merging), an ontologies merging approach that avoids data redundancy and reduces conflict in the merged result. The proposed approach consists of three steps: (1) the similarity search between concepts based on syntactic, structural and semantic techniques; (2) the ontologies merging by the algebraic approach SPO; (3) the global ontology adaptation with graph rewriting rules.To validate our proposals, we have developed several open source tools based on AGG (Attributed Graph Grammar) tool. These tools were applied to a set of ontologies, mainly on those developed in the frame of the CCAlps (Creatives Companies in Alpine Space) European project, which funded this thesis work
12
Sander, Torsten [Verfasser]. "On simply structured bases of graph eigenspaces / Torsten Sander." [Clausthal-Zellerfeld] : [Univ.-Bibliothek], 2009. http://d-nb.info/997062517/34.
Full text
13
Everett, Alistaire Duncan Fraser. "Commuting involution graphs of certain finite simple classical groups." Thesis, University of Manchester, 2011. https://www.research.manchester.ac.uk/portal/en/theses/commuting-involution-graphs-of-certain-finite-simple-classical-groups(dd54ee3d-8c94-42cd-87e1-d34770756466).html.
Full textAbstract:
For a group G and X a subset of G, the commuting graph of G on X, denoted by C(G,X), is the graph whose vertex set is X with x, y joined by an edge if x not equal to y and x and y commute. If the elements in X are involutions, then C(G,X) is called a commuting involution graph. This thesis studies C(G,X) when G is either a 4-dimensional projective symplectic group; a 3-dimensional unitary group; 4-dimensional unitary group over a field of characteristic 2; a 2-dimensional projective general linear group; or a 4-dimensional affne orthogonal group, and X a G-conjugacy class of involutions. We determine the diameters and structure of thediscs of these graphs.
14
Bosi, Gianluca <1991>. "Simple random walks on some partially directed planar graphs." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amsdottorato.unibo.it/8914/1/bosi_gianluca_tesi.pdf.
Full textAbstract:
In this thesis we analyze the recurrence behavior of simple random walks on some classes of directed planar graphs. Our first model is a version of the honeycomb lattice, where the horizontal edges are randomly oriented according to families of random variables: depending on their distribution, we prove a.s. transience in some cases, and a.s. recurrence in other ones. Our results extend those obtained by Campanino and Petritis (’03 and ’14) for partially oriented square grid lattices.
Furthermore, we consider two directed square grid lattices on which, because of the direction imposed by the oriented edges, the simple random walk is bound to revolve clockwise: we prove recurrence for one of the graphs, solving a conjecture of Menshikov et al. (’17), and we give a new proof of transience for the other one.
15
Kimmel, Jason. "Simple Games on Networks." Oberlin College Honors Theses / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1307994412.
Full text
16
Fallahtoori, Sahar. "Distributed Graph Clustering: Study of DiDiC and Some Simpler Forms." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-174831.
Full textAbstract:
The size of global electronic data in need of storage and retrieval is growing with an increasing rate. As a result of this growth, the development of technologies to process such data is a necessity. The data is developing in both complexity and connectivity, particularly for social networks. Connectivity of data means that the records to be stored are highly interdependent. Conventional relational databases are poorly suited for processing highly connected data. On the contrary, graph databases are inherently suited for such dependencies. This is mainly due to the fact that graph databases try to preserve locality and store adjacent records close to one another. This allows retrieval of adjacent elements, regardless of graph size, in constant time. Furthermore, with the everyday growth of data volume these databases won’t fit on single server any longer and need more (distributed) resources. Thus, partitioning of the data to be stored is required. Graph partitioning, based on its aim, can be divided into two major subcategories; a) Balanced partitioning where the aim is to find a predefined, N, number of equally sized clusters and b) Community detection where the aim is to find all underlying dense subgraphs. In this thesis we investigate and improve one particular graph partitioning algorithm, namely DiDiC, which is designed for balanced partitioning. DiDiC is short for diffusive and distributed graph partitioning. The algorithm is independently implemented in this thesis. The main testbeds of our work are real-world social network graphs such as Wikipedia or Facebook and synthetically generated graphs. DiDiC's various aspects and performance are further examined in different situations (i.e. types of graph) and using various sets of parameters (i.e. DiDiC hyperparameters). Our experiments indicate that DiDiC fails to partition the input graphs to the desired number of clusters in more than 70% of cases. In most failure cases it returns the whole graph as a single cluster. We noticed that the diffusive aspects of DiDiC is minimally constrained. Inspired by these observations, we propose two diffusive variants of the DiDiC to address this issue and consequently improve the success rate. This is done mainly by constraining the diffusive aspect of DiDiC. The modifications are straightforward to implement and can be easily incorporated into existing graph databases. We show our modifications consistently outperforms DiDiC with a margin of ~30% success rate in various scenarios. The different scenarios include various sizes of graphs, with different connectivity and structure of underlying clusters. Furthermore, we demonstrate the effectiveness 5 of DiDiC in discovering underlying high density regions of graph a.k.a. “community detection”. In fact, we show that it is more successful in “community detection” (60% success rate) than "balanced clustering" (35% success rate). Finally, we investigate the importance of random initialization of DiDiC algorithm. We observe, while different initialization (and keeping the best performing one) can help the final performance, there is a diminishing return when the algorithm is randomly initialized more than 4 times.
17
Wright, Benjamin. "Graphs associated with the sporadic simple groups Fi₂₄ and BM." Thesis, University of Manchester, 2011. https://www.research.manchester.ac.uk/portal/en/theses/graphs-associated-with-the-sporadic-simple-groups-fi24-and-bm(dcdd493b-929d-4f91-a6bc-48c6b5fda3ba).html.
Full textAbstract:
Our aim is to calculate some graphs associated with two of the larger sporadicsimple groups, Fi₂₄ and the Baby Monster. Firstly we calculate the point line collinearity graph for a maximal 2-local geometry of Fi₂₄. If T is such a geometry, then the point line collinearity graph G will be the graph whose vertices are the points in T, with any two vertices joined by an edge if and only if they are incident with a common line. We found that the graph has diameter 5 and we give its collapsed adjacency matrix. We also calculate part of the commuting involution graph, C, for the class 2C of the Baby Monster, whose vertex set is the conjugacy class 2C, with any two elements joined by an edge if and only if they commute. We have managed to place all vertices inside C whose product with a fixed vertex t does not have 2 power order, with all evidence pointing towards C having diameter 3.
18
Silva, Allan Kardec Messias da. "O degree graph dos grupos alternados e de outros grupos simples." reponame:Repositório Institucional da UnB, 2013. http://repositorio.unb.br/handle/10482/13601.
Full textAbstract:
Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2013.Submitted by Luiza Silva Almeida (luizaalmeida@bce.unb.br) on 2013-07-17T20:41:38Z No. of bitstreams: 1 2013_AllanKardecMessiasdaSilva.pdf: 811006 bytes, checksum: d150f5332d05a0c2ccff34412c37b29f (MD5)
Approved for entry into archive by Leandro Silva Borges(leandroborges@bce.unb.br) on 2013-07-17T21:22:19Z (GMT) No. of bitstreams: 1 2013_AllanKardecMessiasdaSilva.pdf: 811006 bytes, checksum: d150f5332d05a0c2ccff34412c37b29f (MD5)
Made available in DSpace on 2013-07-17T21:22:19Z (GMT). No. of bitstreams: 1 2013_AllanKardecMessiasdaSilva.pdf: 811006 bytes, checksum: d150f5332d05a0c2ccff34412c37b29f (MD5)
O presente trabalho é uma introdução ao estudo de um grafo chamado Degree Graph. Este grafo é associado aos graus dos caracteres de um grupo nito no seguinte modo: os vértices são os primos que dividem os graus dos caracteres irredutíveis e dois vértices p; q são conexos com uma aresta se o grupo possui um caráter irredutível cujo grau é divisível pelo produto pq. O Degree Graph foi estudado inicialmente em grupos solúveis e apenas a pouco teve seus estudos avançados para grupos não solúveis. Donald L. White completou o estudo para grupos simples em 2009 com o artigo `Degree Graphs of Simple Groups', onde ele descreve para todos os grupos nitos simples os correspondentes Degree Graphs. Vamos neste trabalho mostrar estes estudos para todos os grupos alternados, e alguns grupos simples lineares, simpléticos e unitários. O principal resultado que vamos ilustrar em detalhes é o fato que, se n 9, o Degree Graph do grupo alternado An é um grafo completo. Este resultado usa uma conjectura de Alvis, provada por Barry e Ward. _______________________________________________________________________________________ ABSTRACT
The present work is an introduction to the study of a graph called Degree Graph. This graph is associated to the degrees of the characters of a nite group in the following way: the vertices are the primes that divide the degrees of the irreducible characters and two vertices p; q are connected with an edge if the group has an irreducible character whose degree is divisible the product pq. O Degree Graph was initially studied for soluble groups and only recently also for non soluble groups. In 2009 Donald L. White completed the study for simple groups in the paper `Degree Graph of Simple Groups', where he describes for all nite simple groups the corresponding Degree Graphs. In this work, we will illustrate these studies for all alternating groups and some simple linear, symplectic and unitary groups. The main result that we will describe in detail is the fact that if n 9, the Degree Graph of the alternating group An is a complete graph. This result makes use of a conjecture of Alvis, proved by Barry Ward.
19
Frondana, Iara Moreira. "Model selection for discrete Markov random fields on graphs." Universidade de São Paulo, 2016. http://www.teses.usp.br/teses/disponiveis/45/45133/tde-02022018-151123/.
Full textAbstract:
In this thesis we propose to use a penalized maximum conditional likelihood criterion to estimate the graph of a general discrete Markov random field. We prove the almost sure convergence of the estimator of the graph in the case of a finite or countable infinite set of variables. Our method requires minimal assumptions on the probability distribution and contrary to other approaches in the literature, the usual positivity condition is not needed. We present several examples with a finite set of vertices and study the performance of the estimator on simulated data from theses examples. We also introduce an empirical procedure based on k-fold cross validation to select the best value of the constant in the estimators definition and show the application of this method in two real datasets.Nesta tese propomos um critério de máxima verossimilhança penalizada para estimar o grafo de dependência condicional de um campo aleatório Markoviano discreto. Provamos a convergência quase certa do estimador do grafo no caso de um conjunto finito ou infinito enumerável de variáveis. Nosso método requer condições mínimas na distribuição de probabilidade e contrariamente a outras abordagens da literatura, a condição usual de positividade não é necessária. Introduzimos alguns exemplos com um conjunto finito de vértices e estudamos o desempenho do estimador em dados simulados desses exemplos. Também propomos um procedimento empírico baseado no método de validação cruzada para selecionar o melhor valor da constante na definição do estimador, e mostramos a aplicação deste procedimento em dois conjuntos de dados reais.
20
González, Ruiz Jacobo Leonardo 502510, and Ruiz Jacobo Leonardo González. "Calculo del clique-width en graficas simples de acuerdo a su estructura." Tesis de doctorado, Universidad Autónoma del Estado de México, 2018. http://hdl.handle.net/20.500.11799/95286.
Full textAbstract:
El cálculo del cliquewidth, un número entero que es un invariante para gráficas, ha sido estudiado de manera activa, ya que existen problemas catalogados como NP-Completos que tienen complejidad baja si su representación en gráficas tiene cliquewidth acotado. De cierta manera este parametro mide la dificultad de descomponer una gráfica en una estructura llamada árbol (por su topología). La importancia de este invariante radica en que si un problema de gráficas puede ser acotado por ella entonces puede ser resuelto en tiempo polinomial según el teorema principal de Courcelle. Por otra parte el cliquewidth tiene una relación directa con el invariante tree-width con la distinción de que el primero es más general que el segundo. Para calcular este tipo de invariantes se han propuesto en la literatura diferentes procedimientos que dividen la gráfica original en subgráficas las cuales determinan la complejidad, por lo que en la investigación aquí reportada se ha utilizado una descomposición particular de una gráfica simple, la cual consiste en descomponer la gráfica en ciclos simples y árboles. Las gráficas que consisten de ciclos simples y árboles se denominan cactus, sobre las cuales hemos demostrado que el clique-width es menor o igual a 4 lo que mejora la cota establecida por la relación entre el clique-width y el invariante treewidth la cual establece que el cwd(G) ≤ 3·2twd(G)−1. De igual manera se han estudiado otro tipo de gráficas denominadas poligonales, formadas por polígonos con mismo número de lados los cuales comparten entre si una única arista; sobre este tipo de gráficas en esta investigación se ha demostrado que el cliquewidth es igual a 5, de igual manera mejorando la cota conocida por la relación de las invariantes mencionadas anteriormente. Finalmente, estudiando el comportamiento de operaciones de union de estas subgráficas se ha propuesto un método de aproximación para el cálculo del cliquewidth de una gráfica simple de manera general. El algoritmo esta basado en el clásico algoritmo de Disjktra que encuentra el camino mas corto entre dos vértices de una gráfica. Del planteamiento de los algoritmos mencionados anteriormente se obtuvo la publicación de tres artículos, en los que se incluye el desarrollo de las demostraciones para el cálculo del clique-width en los diferentes escenarios de estudio.CONACyT
21
De, Saedeleer Julie. "The residually weakly primitive and locally two-transitive rank two geometries for the groups PSL(2, q)." Doctoral thesis, Universite Libre de Bruxelles, 2010. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210037.
Full textAbstract:
The main goal of this thesis is a contribution to the classification of all incidence geometriesof rank two on which some group PSL(2,q), q a prime power, acts flag-transitively.
Actually we require that the action be RWPRI (residually weakly primitive) and (2T)1
(doubly transitive on every residue of rank one). In fact our definition of RWPRI requires
the geometry to be firm (each residue of rank one has at least two elements) and RC
(residually connected).
The main goal is achieved in this thesis.
It is stated in our "Main Theorem". The proof of this theorem requires more than 60pages.
Quite surprisingly, our proof in the direction of the main goal uses essentially the classification
of all subgroups of PSL(2,q), a famous result provided in Dickson’s book "Linear groups: With an exposition of the Galois field theory", section 260, in which the group is called Linear Fractional Group LF(n, pn).
Our proof requires to work with all ordered pairs of subgroups up to conjugacy.
The restrictions such as RWPRI and (2T)1 allow for a complete analysis.
The geometries obtained in our "Main Theorem" are bipartite graphs; and also locally 2-arc-transitive
graphs in the sense of Giudici, Li and Cheryl Praeger. These graphs are interesting in their own right because of
the numerous connections they have with other fields of mathematics.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
22
Schuhmacher, Michael Verfasser], and Simone Paolo [Akademischer Betreuer] [Ponzetto. "Knowledge Graph Exploration for Natural Language Understanding in Web Information Retrieval / Michael Schuhmacher ; Betreuer: Simone Paolo Ponzetto." Mannheim : Universitätsbibliothek Mannheim, 2016. http://d-nb.info/1120302587/34.
Full text
23
Schuhmacher, Michael [Verfasser], and Simone Paolo [Akademischer Betreuer] Ponzetto. "Knowledge Graph Exploration for Natural Language Understanding in Web Information Retrieval / Michael Schuhmacher ; Betreuer: Simone Paolo Ponzetto." Mannheim : Universitätsbibliothek Mannheim, 2016. http://d-nb.info/1120302587/34.
Full text
24
Biswas, Arindam. "Théorie des groupes approximatifs et ses applications." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLS573.
Full textAbstract:
Dans la premier partie de cette thèse, nous étudions la structure des sous-groupes approximatifs dans les groupes metabéliens (groupes résolubles de classe de résolubilité 2) et montrons que si A est un tel sous-groupe K approximatif, il est K^⁰(r) contrôlée (au sens du Tao) par un groupe nilpotent où $ r désigne le rang de $ G=Fit (G) et Fit (G) $ est le sous-groupe de fitting de G. La deuxième partie est consacrée à l'étude de la croissance des ensembles dans GLn(Fq) où Fq est un corps fini. Nous montrons une borne sur le diamètre (par rapport à n'importe quel système des générateurs) pour tous sous-groupes simples finis de ce groupe. Si G est un groupe fini simple de type Lie de rang n, et son corps de base est de taille borné, le diamètre du graphe du Cayley Gamma (G;S) serait borné par exp (O (n (log n) ^ 3)) . Si la taille du corps fini Fq n'est pas borné, notre méthode donne une borne de q ^ {O (n ( log nq) ^ 3) pour le diamètre.Dans la troisième partie nous nous sommes intéressés à la croissance des ensembles dans les boucles de Moufang commutatifs. Ceux-ci sont les boucles commutatifs respectant les identités de Moufang mais sans être (nécessairement) associatifs. Nous montrons que, si les tailles des ensembles des associateurs sont bornées alors la croissance des sous-structures approximatifs dans ces boucles est similaire à celle des groupes ordinaires. De cette façon dans le cadre des boucles de moufang commutatifs finiment engendré on a un théorème de structure pour ses sous-boucles approximatifs.Mots-clefs -sous-groupes approximatifs, groupes résolubles, diamètres des groupes, boucles de moufang commutatifsIn the first part of this thesis, we study the structure of approximate subgroups inside metabelian groups (solvable groups of derived length 2) and show that if A is such a K-approximate subgroup, then it is K^(O(r)) controlled (in the sense of Tao) by a nilpotent group where r denotes the rank of G=Fit(G) and Fit(G) is the fitting subgroup of G.The second part is devoted to the study of growth of sets inside GLn(Fq) , where we show a bound on the diameter (with respect to any set of generators) for all finite simple subgroups of this group. What we have is - if G is a finite simple group of Lie type with rank n, and its base field has bounded size, then the diameter of the Cayley graph C(G; S) would be bounded by exp(O(n(logn)^3)). If the size of the base field Fq is not bounded then our method gives a bound of q^(O(n(log nq)3)) for the diameter.In the third part we are interested in the growth of sets inside commutative Moufang loops which are commutative loops respecting the moufang identities but without (necessarily)being associative. For them we show that if the sizes of the associator sets are bounded then the growth of approximate substructures inside these loops is similar to those in ordinary groups. In this way for the subclass of finitely generated commutative moufang loops we have a classification theorem of its approximate subloops
25
Mattos, Bruno Donadelli Trajano. "Cálculo de áreas sem o uso do Teorema Fundamental do Cálculo." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/55/55136/tde-02022018-090342/.
Full textAbstract:
Desenvolvemos uma estratégia natural e acessível aos estudantes do Ensino Médio para o cálculo de áreas planas sem as ferramentas mais avançadas do Cálculo Diferencial e Integral.We developed a natural strategy, achievable by high school students, for the computation of area of limited regions of the cartesian plane, without making use of more advanced resources of Differential and Integral Calculus.
26
Hwang, Joe, and 黃守偉. "Automatic Graph Drawing for Simple Graphs." Thesis, 1998. http://ndltd.ncl.edu.tw/handle/62852007564092722674.
Full text
27
Chang, Chia-Yi, and 張嘉益. "Two Efficient Graph Representations for SimpleTwo Efficient Graph Representations for Simple Graphs." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/91938888012934084888.
Full textAbstract:
碩士國立臺灣科技大學
資訊管理系
93
Representing graphs is a fundamental data-structuring problem. Adjacency matrices and adjacency lists are two well known representations. The operations on an adjacency matrix which contain adjacency test, inserting/deleting an edge can be done in constant time. However, finding all adjacency vertices of a given vertex will take θ(n) time by using an adjacent matrix. On the other hand, to test adjacency on adjacency lists will take O(deg(i)) time, where deg(i) is the degree of vertex i. In this thesis, we propose two efficient representations which not only support adjacency test in constant time, but also support the adjacency test of a given vertex in θ(deg(i)). Our representation will take θ(n2) time to initialize. However, inserting/deleting an edge only takes constant time. The proposed representations will be very efficient for the problems with a lot of inserting/deleting edge operations.
28
Papoutsakis, Ioannis. "Tree Spanners of Simple Graphs." Thesis, 2013. http://hdl.handle.net/1807/35920.
Full textAbstract:
A tree $t$-spanner $T$ of a simple graph $G$ is a spanning tree of $G$,
such that for every pair of vertices of $G$ their distance in $T$ is at
most $t$ times their distance in $G$, where $t$ is called a stretch
factor of $T$ in $G$. It has been shown that there is a linear time
algorithm to find a tree 2-spanner in a graph;
it has also been proved that, for each $t>3$, determining whether a graph
admits a tree $t$-spanner is an NP-complete problem. This thesis studies
tree $t$-spanners from both theoretical and algorithmic perspectives.
In particular, it is proved that a nontree graph admits a unique tree
$t$-spanner for at
most one value of stretch factor $t$. As a corollary, a nontree
bipartite graph cannot admit a unique tree $t$-spanner for any $t$.
But, for each $t$, there are infinitely many nontree graphs that admit
exactly one tree $t$-spanner. Furthermore, for each $t$, let U($t$) be
the set of graphs being the union of two tree $t$-spanners of a graph.
Although graphs in U(2) do not have cycles of length greater than 4,
graphs in U(3) may contain cycles of arbitrary length. It turns out that
any even cycle is an induced subgraph of a graph in U(3), while no graph in
U(3) contains an induced odd cycle other than a triangle; graphs in U(3)
are shown to be perfect. Also, properties of induced even cycles of graphs
in U(3) are presented. For each $t>3$, though, graphs in U($t$) may
contain induced odd cycles of any length.
Moreover, there is an efficient algorithm to recognize graphs that admit a
tree 3-spanner of diameter at most 4, while it is proved that, for
each $t>3$, determining whether a graph admits a tree $t$-spanner of
diameter at most $t+1$ is an NP-complete problem. It is not known if it
is hard to recognize graphs that admit a tree 3-spanner of general diameter;
however integer programming is employed to provide certificates of tree
3-spanner inadmissibility for a family of graphs.
29
邱建綸. "On the Book-thickness of a simple graph." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/07580213763515161824.
Full textAbstract:
碩士國立中正大學
數學系研究所
105
We went to discuss the book embedding of a simple G into a book B is a drawing of this G on the pages of the book B such that there are no edge crossings on each page of this book B. Then, use Bounds of Book-thickness to discuss some special graphs. Finally, classified all the finite local rings with planar zero-divisor graphs of Book-thickness.
30
Rahmati, Zahed. "Simple, Faster Kinetic Data Structures." Thesis, 2014. http://hdl.handle.net/1828/5627.
Full textAbstract:
Proximity problems and point set embeddability problems are fundamental and well-studied in computational geometry and graph drawing. Examples of such problems that are of particular interest to us in this dissertation include: finding the closest pair among a set P of points, finding the k-nearest neighbors to each point p in P, answering reverse k-nearest neighbor queries, computing the Yao graph, the Semi-Yao graph and the Euclidean minimum spanning tree of P, and mapping the vertices of a planar graph to a set P of points without inducing edge crossings.
In this dissertation, we consider so-called kinetic version of these problems, that is, the points are allowed to move continuously along known trajectories, which are subject to change. We design a set of data structures and a mechanism to efficiently update the data structures. These updates occur at critical, discrete times. Also, a query may arrive at any time. We want to answer queries quickly without solving problems from scratch, so we maintain solutions continuously. We present new techniques for giving kinetic solutions with better performance for some these problems, and we provide the first kinetic results for others. In particular, we provide:
• A simple kinetic data structure (KDS) to maintain all the nearest neighbors and the closest pair. Our deterministic kinetic approach for maintenance of all the nearest neighbors improves the previous randomized kinetic algorithm.
• An exact KDS for maintenance of the Euclidean minimum spanning tree, which improves the previous KDS.
• The first KDS's for maintenance of the Yao graph and the Semi-Yao graph.
• The first KDS to consider maintaining plane graphs on moving points.
• The first KDS for maintenance of all the k-nearest neighbors, for any k ≥ 1.
• The first KDS to answer the reverse k-nearest neighbor queries, for any k ≥ 1 in any fixed dimension, on a set of moving points.Graduate
31
Sutuntivorakoon, Kanes. "Maximal Clique Scheduling: A Simple Algorithm to Bound Maximal Independent Graph Scheduling." Thesis, 2012. http://hdl.handle.net/1911/64702.
Full textAbstract:
In this paper, we consider interference networks where the connectivity is known globally while the channel gains are known up to a particular distance from each node. In this setting, we provide a new achievability, called Maximal Clique Scheduling (MCS), which is a special case of Maximal Independent Graph Scheduling (MIG Scheduling) proposed earlier. The strategy is evaluated using the notion of normalized sum rate which is a metric to evaluate performance of networks with mismatched knowledge. The achievable normalized sum rate of the proposed MCS strategy is easier to analyze for certain classes of networks and can be used to bound the normalized sum rate of MIG Scheduling. We investigate the normalized sum rate achieved by MCS for two classes of networks. The first class is formed by interference networks where each link is connected with probability $p$. The second class is derived from Wyner 1-D model of placements of base stations and mobile nodes. We find that increasing knowledge about the network leads to increasing normalized sum-rate. However, in a random network, the increase is slower as compared to Wyner network because most nodes are far away from a node and hence learning more helps less until the whole network is known.
32
Chiang, Wei-Ling, and 江韋伶. "A Linear Time Algorithm for the Simple Moplex Ordering of a Strongly Chordal Graph." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/26826356427901784124.
Full textAbstract:
碩士國立臺北商業技術學院
資訊與決策科學研究所
102
Berry [A. Berry, J. P. Bordat, Moplex elimination orderings, Electronic Notes in Discrete Mathematics, 8 (2001) 6--9] proved that a graph G is choral if and only if G admits a moplex ordering. In this thesis, we also prove that a strongly chordal graph has a similar ordering namely simple moplex ordering. Then, we propose an algorithm that can be run in linear time to find such an ordering.
33
Dona, Daniele. "Growth in finite groups and the Graph Isomorphism Problem." Doctoral thesis, 2020. http://hdl.handle.net/21.11130/00-1735-0000-0005-145F-B.
Full text
34
Liao, Chia-Ying, and 廖家瑩. "The Effect of Trigger-based Animated Instruction on Learning Achievement and Cognitive Load in Simple Quadratic Functions Graph." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/01176774279264291417.
Full textAbstract:
碩士國立交通大學
理學院科技與數位學習學程
98
Trigger-based Animated Instruction is based on the concept of cognitive load theory and multimedia learning theory. Based on the Trigger-based Animated Instruction, instructors design teaching materials corresponded to classroom instructions, which contribute to guiding attention more easily; and help students take the initiative to search, select and organize information; reduce the burden on working memory as well as cognitive load; and enhance learning. This study adopted a quasi-experimental design by using the simple quadratic function graph of mathematics teaching material, to examine learning achievement and cognitive load cross two different instructions, i.e. the trigger-base animated instruction and the traditional methodology. The result of this study shows that adopting the trigger-based animated instruction significantly helps students learn more effectively, and reduces the cognitive load. Additionally, the effect was more pronounced for high-achieving students.
35
黃楷智. "A Study on the Effect of GeoGebra on Math Learning Achievement and Cognitive Diagnosis – a Case of Simple Quadratic Functions Graph." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/60743840479873938966.
Full textAbstract:
碩士國立交通大學
理學院科技與數位學習學程
99
GeoGebra (dynamic geometry system) is an interactive software that combines algebraic calculation and geometric construction. The main feature focuses on students’ own initiatives to operate and observe mathematical objects through interactive methods. It facilitates building mathematical concepts through tangible experiences. With properly designed teaching materials, it can focus students’ attentions, promote cognitive learning and encourage student-teacher interactions. Using the quasi-experimental method, the study uses simple quadratic function as the particular case to investigate whether GeoGebra’s teaching design can achieve better learning outcomes compared to the typical PowerPoint presentations and the common traditional teachings; and to provide further analysis on cognitive diagnostic assessment. The main conclusion can be summarized as follows: 1.GeoGebra’s instructional design helps students with low to mid academic abilities to improve their mathematical learning. 2.GeoGebra’s instructional design has the apparent effect in aiding students form mathematical concepts and turn hands-on skills into new knowledge stored in the long-term memory. 3.GeoGebra’s instructional design helps students to increase their proficiencies in acquiring mathematical skills and enhance the concept of pictorial reprentations.
36
Kynčl, Jan. "Kombinatorické otázky v geometrii." Doctoral thesis, 2013. http://www.nusl.cz/ntk/nusl-328681.
Full text
37
Rodrigues, Bernardo Gabriel. "Codes of designs and graphs from finite simple groups." Thesis, 2002. http://hdl.handle.net/10413/3895.
Full textAbstract:
Discrete mathematics has had many applications in recent years and this is
only one reason for its increasing dynamism. The study of finite structures is
a broad area which has a unity not merely of description but also in practice,
since many of the structures studied give results which can be applied to other, apparently dissimilar structures. Apart from the applications, which themselves generate problems, internally there are still many difficult and interesting problems in finite geometry and combinatorics. There are still many puzzling features about sub-structures of finite projective spaces, the minimum weight of the dual codes of polynomial codes, as well as about finite projective planes. Finite groups are an ever strong theme for several reasons. There is still much work to be done to give a clear geometric identification of the finite simple groups. There are also many problems in characterizing structures which either have a particular group acting on them or which have some degree of symmetry from a group action.
Codes obtained from permutation representations of finite groups have been given particular attention in recent years. Given a representation of group elements of a group G by permutations we can work modulo 2 and obtain a representation of G on a vector space V over lF2 . The invariant subspaces (the subspaces of V taken into themselves by every group element) are then all the binary codes C for which G is a subgroup of Aut(C). Similar methods produce codes over arbitrary fields. Through a module-theoretic approach, and based on a study of monomial actions and projective representations, codes with given transitive permutation group were determined by various authors. Starting with well known simple groups and defining designs and codes through the primitive actions of the groups will give structures that have this group in their automorphism groups. For each of the primitive representations, we construct the permutation group and form the orbits of the stabilizer of a point.
Taking these ideas further we have investigated the codes from the primitive permutation representations of the simple alternating and symplectic groups of odd characteristic in their natural rank-3 primitive actions. We have also investigated alternative ways of constructing these codes, and these have come about by noticing that the codes constructed from the primitive permutations of the groups could also be obtained from graphs. We achieved this by constructing codes from the span of adjacency matrices of graphs. In particular we have constructed codes from the triangular graphs and from the graphs on triples.
The simple symplectic group PSp2m(q), where m is at least 2 and q is any prime power, acts as a primitive rank-3 group of degree q2m-1/q-1 on the points of the projective (2m-1)-space PG2m-1(IFq ). The codes obtained from the primitive rank-3 action of the simple projective symplectic groups PSp2m(Q), where Q= 2t with t an integer such that t ≥ 1, are the well known binary subcodes of the
projective generalized Reed-Muller codes. However, by looking at the simple symplectic groups PSp2m(q), where q is a power of an odd prime and m ≥ 2, we observe that in their rank-3 action as primitive groups of degree q2m-1/q-1 these groups have 2-modular representations that
give rise to self-orthogonal binary codes whose properties can be linked to those of
the underlying geometry. We establish some properties of these codes, including
bounds for the minimum weight and the nature of some classes of codewords.
The knowledge of the structures of the automorphism groups has played a key
role in the determination of explicit permutation decoding sets (PD-sets) for the
binary codes obtained from the adjacency matrix of the triangular graph T(n) for n ≥ 5 and similarly from the adjacency matrices of the graphs on triples.
The successful decoding came about by ordering the points in such a way that the
nature of the information symbols was known and the action of the automorphism
group apparent.
Although the binary codes of the triangular graph T(n) were known, we have
examined the codes and their duals further by looking at the question of minimum weight generators for the codes and for their duals. In this way we find bases
of minimum weight codewords for such codes. We have also obtained explicit
permutation-decoding sets for these codes.
For a set Ω of size n and Ω{3} the set of subsets of Ω of size 3, we investigate the binary codes obtained from the adjacency matrix of each of the three graphs with
vertex set Ω{3}1 with adjacency defined by two vertices as 3-sets being adjacent if they have zero, one or two elements in common, respectively. We show that
permutation decoding can be used, by finding PD-sets, for some of the binary codes obtained from the adjacency matrix of the graphs on (n3) vertices, for n ≥ 7.Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 2002.
38
Huang, Wei-Chih, and 黃韋誌. "Dynamic Monopoly in Simple Directed Graphs with Girth g." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/79606676945973446482.
Full textAbstract:
碩士國立臺灣大學
資訊工程學研究所
99
Suppose G(V,E) is a simple directed graph, where there is at most one directed edge between each pair of vertices. We say G(V,E) has girth g if the length of the shortest cycle in is . We shall require that each vertex in a simple directed graph have at least one in-neighbor. Now, consider a process of propagations in a directed graph G(V,E) as follows. Some vertices, called seeds, in V are initially active, and the others are inactive. Later, an inactive vertex is activated if over half of its in-neighbors are active, and such activations end while no more vertices can be activated. In dynamic monopoly problems, we focus on such a set of seeds in V that all vertices will be activated at the end of propagations. In this thesis, we derive an upper bound, floor(|V|/2)+ceiling(|V|/2g), on size of such a set of seeds for any simple directed graph G(V,E) with girth g.
39
Chang, Ting-Chung, and 張庭鈞. "A graph-based simplex method for performance-driven layout compaction." Thesis, 1993. http://ndltd.ncl.edu.tw/handle/56936939712251087832.
Full textAbstract:
碩士國立成功大學
電機工程研究所
81
As the increasing requirement of high speed circuit, the performance issue must be addressed at layout compaction. In this thesis, a new layout compaction approach which aims at this purpose is considered. This compaction approach consists of two stages: In the first stage, the upper bound of delay on a set of timing critical path is minimized; and in the second stage, the area of the layout is minimized while all the timing cirtical paths are compelled to the obtained delay upper bound. This approach considers the performance with higher priority than the layout size. Both stages in this approach can be formulated as linear programming (LP) problems. Although the well -known simplex algorithm can be used to solve the LP problems, however, the execution time will be intolerable for practical applications. In order to handle these problems efficiently, we propose a graph- based simplex algorithm. This algorithm fully utilizes the sparse structure of the problem and shift most of the work in the LP domain into the graph domain. It can be proved that this algorithm has lower time complexity than the typical simplex method, and experimental results also show that this algorithm is quite promising.
40
Alallah, Fouad Shoie. "OA-Graphs: Orientation Agnostic Graphs for improving the legibility of simple visualizations on horizontal displays." 2011. http://hdl.handle.net/1993/4451.
Full textAbstract:
Horizontal displays, such as tabletop systems, are emerging as the de facto platform for engaging participants in collaborative tasks. Despite significant efforts in improving the interactivity of information on such systems, very little research has been invested in understanding how groups of people view data visualizations in such environments. Numerous studies introduced different techniques to support viewing visualization for groups of people, such as duplicating or reorienting the visual displays. However, when visualizations compete for pixels on the display, prior solutions do not work effectively.
In this thesis, I explore whether orientation on horizontal displays impacts the legibility of simple visualizations such as graphs. I have found that users are best at reading a graph when it is right side up, and takes them 20% less time than when it is read upside down. The main objective of this thesis was to investigate whether the readability and understandability of simple graphs can be improved. I have introduced the Orientation Agnostic Graph (OA-Graph) which is legible regardless of orientation. The OA-Graph uses a radial layout which has several interesting properties such as implicit orientation, points equidistant to center, and flexible rearrangement. OA-Graphs perform better than graphs that are presented upside down. I have converted several popular types of graphs into their OA counterpart for improved legibility on tabletop systems. Guidelines are presented that describe how other visualizations can be converted to being orientation agnostic.
41
Chen, Yu-Chih, and 陳育志. "A simple scheme of generating Faulty-tolerant bipartite graphs with Hamiltonian properties." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/6c9872.
Full textAbstract:
碩士中原大學
應用數學研究所
91
In this paper, we introduce a simple scheme for generating ``{sl good}" bipartite graphs. A bipartite graph $G$ with bipartition $W$ and $B$ is a good graph if it is {sl 1-hamiltonian} and {sl hamiltonian laceable}. More specifically, $G$ is good if $G-F$ remains hamiltonian where $F$ consists of an edge or a pair of vertices ${v_1,v_2mid v_1in W, v_2in B}$, and if there exists a hamiltonian path joining $u$ to $v$ for any $uin W, vin B$. This scheme is called ``{sl edge replacement}". Simple examples of good bipartite graphs, as well as the family of {sl brother trees} $BT(n)$ with $nge 1$ cite{KaoBT}, are obtained as an application of edge replacement.
42
Chin-Chien, Hsieh, and 謝謹謙. "A Study of Instructional Design by Trigger-based Animation on Learning Achievement by Cognitively Diagnostic Assessment-Graphs of Simple Quadratic Functions as an Example." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/35178586906271850088.
Full textAbstract:
碩士國立交通大學
理學院科技與數位學習學程
99
There are some questions to explore in multimedia teaching on this study. Are the materials designed by Trigger-based Animated Instruction different from those designed with slides? Is there significant difference to different academic achievement students in those teaching? Is there significant difference to test the students in attribute prevalence levels and cognitive levels by Cognitively Diagnostic Assessment? How do students perform in each attribute prevelence levels and in cognitive levels in the posttest and the postpone test? Overall, in the posttest, the teaching effectiveness of the materials designed by Trigger-based Animated Instruction is better than the teaching with slides in the high-achievement students at “conceptual understanding” and “problem solving”. In the postpone test, the teaching effectiveness of the materials designed by Trigger-based Animated Instruction is better than the teaching with slides and the traditional teaching on the blackboard in the low-achievement students at the 10th skill ( To understand the coordinate of a point in the quadratic function is the solution to the equation.), in the high-achievement students at the 5th skill (To judge whether there is the highest or the lowest point in the quadratic function gragh), and in the high-achieving students at “procedural knowledge”.