Concept
Automorphisme de graphe
Concepts associés (19)
Graphe fortement régulier
En théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier. Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que Toute paire de sommets adjacents a exactement λ voisins communs. Toute paire de sommets non-adjacents a exactement μ voisins communs. Un graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).
Théorie algébrique des graphes
vignette|Le graphe de Petersen, qui possède 10 sommets et 15 arêtes. Hautement symétrique, il est en particulier distance-transitif. Son groupe d'automorphisme a 120 éléments et est en fait le groupe symétrique S. De diamètre 2, il possède 3 valeurs propres. En mathématiques, la théorie algébrique des graphes utilise des méthodes algébriques pour résoudre des problèmes liés aux graphes, par opposition à des approches géométriques, combinatoires ou algorithmiques.
Graphe semi-symétrique
En théorie des graphes, un graphe non-orienté est semi-symétrique s'il est arête-transitif et régulier, mais pas sommet-transitif. Autrement dit, un graphe est semi-symétrique s'il est régulier et si son groupe d'automorphismes agit transitivement sur ses arêtes, mais pas sur ses sommets. Tout graphe semi-symétrique est biparti, et son groupe d'automorphisme agit transitivement sur les deux sous-ensembles de sommets de la bipartition. Il n'existe aucun graphe semi-symétrique d'ordre 2p ou 2p, où p est un nombre premier.
Théorème de Frucht
Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph. More strongly, for any finite group G there exist infinitely many non-isomorphic simple connected graphs such that the automorphism group of each of them is isomorphic to G. The main idea of the proof is to observe that the Cayley graph of G, with the addition of colors and orientations on its edges to distinguish the generators of G from each other, has the desired automorphism group.
Graphe circulant
En théorie des graphes, un graphe circulant est un graphe non orienté sur lequel agit un groupe cyclique d'automorphismes de graphes qui en fait un graphe sommet-transitif. On trouve aussi l'appellation graphe cyclique mais ce terme aussi d'autres significations. Il y a plusieurs manières équivalentes de définir les graphes circulants ; un graphe est circulant lorsque le groupe d'automorphisme du graphe admet un sous-groupe cyclique qui agit de manière transitive sur les sommets du graphe.
Graphe sommet-transitif
En théorie des graphes, un graphe non-orienté est sommet-transitif si pour tout couple de sommets, il existe un automorphisme de graphe qui envoie le premier sommet sur le deuxième. De manière informelle cette propriété indique que tous les sommets jouent exactement le même rôle à l'intérieur du graphe. Un graphe est sommet-transitif si pour tout couple de sommets, il existe un automorphisme de graphe qui envoie le premier sommet sur le deuxième.
Graphe distance-régulier
En théorie des graphes, un graphe régulier est dit distance-régulier si pour tous sommets distants de , et pour tous entiers naturels , il y a toujours le même nombre de sommets qui sont à la fois à distance de et à distance de . De manière équivalente, un graphe est distance-régulier si pour tous sommets , le nombre de sommets voisins de à distance de et le nombre de sommets voisins de à distance de ne dépendent que de et de la distance entre et . Formellement, tels que et où est l’ensemble des sommets à distance de , et .
Graphe de Rado
En mathématiques, et plus précisément en théorie des graphes, le graphe de Rado, appelé également graphe d'Erdős–Rényi ou graphe aléatoire, est un graphe infini dénombrable étudié au début des années 1960 par Richard Rado, Paul Erdős et Alfréd Rényi, caractérisé par la propriété d’extension, qui implique qu’il contient (en tant que sous-graphe) n'importe quel graphe fini ou dénombrable. Il en existe plusieurs constructions ; c'est en particulier (presque sûrement) le graphe aléatoire obtenu en choisissant au hasard pour chaque paire de sommets s'ils sont connectés ou non.
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
Graphe de Frucht
Le graphe de Frucht est, en théorie des graphes, un graphe 3-régulier possédant 12 sommets et 18 arêtes. C'est le plus petit graphe cubique dont le groupe d'automorphismes ne contienne que l'élément neutre. En d'autre termes, c'est le plus petit graphe régulier de degré trois étant un graphe asymétrique. Il est décrit pour la première fois en 1939 par Robert Frucht, d'où son nom. Le graphe de Frucht est planaire et hamiltonien. C'est aussi un cas de graphe de Halin.