Concept
Graphe complet
Concepts associés (29)
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 sommet-connexe
En théorie des graphes, un graphe connexe . Un graphe autre qu'un graphe complet est de degré de sommet-connexité k s'il est k-sommet-connexe sans être k+1-sommet-connexe, donc si k est la taille du plus petit sous-ensemble de sommets dont la suppression déconnecte le graphe. Les graphes complets ne sont pas inclus dans cette version de la définition car ils ne peuvent pas être déconnectés en supprimant des sommets. Le graphe complet à n sommets est de degré de connexité n-1.
Famille de Petersen
thumb|300px|La famille de Petersen. Le graphe complet K6 est en haut de l'illustration, et le graphe de Petersen est en bas. Les liaisons bleues indiquent des transformations Δ-Y ou Y-Δ entre les graphe s de la famille. En mathématiques, et plus précisément en théorie des graphes, la famille de Petersen est un ensemble de sept graphes non orientés contenant le graphe de Petersen et le graphe complet K6. Cette famille a été découverte et étudiée par le mathématicien danois Julius Petersen.
Linkless embedding
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.
Orientation (graph theory)
In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. A directed graph is called an oriented graph if none of its pairs of vertices is linked by two symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of (x, y) and (y, x) may be arrows of the graph). A tournament is an orientation of a complete graph. A polytree is an orientation of an undirected tree.
Pál Turán
Pál Turán, né le à Budapest et décédé le , est un mathématicien hongrois connu comme l'auteur du théorème de Turán. Son nombre d'Erdős est 1. Il était l'époux de Vera Sós Turán, mathématicienne elle aussi. Théorème d'Erdős-Kac Histoire de la fonction zêta de Riemann Université Loránd Eötvös Prix Kossuth Théorème de Szemerédi Conjecture d'Erdős-Turán sur les bases additives Inégalité d'Erdős-Turán Graphe de Turán Catégorie:Naissance à Budapest Catégorie:Naissance en août 1910 Catégorie:Naissance dans le roya
Graphe grille
In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space \mathbb{R}^n, forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lattice in the group-theoretical sense. Typically, no clear distinction is made between such a graph in the more abstract sense of graph theory, and its drawing in space (often the plane or 3D space). This type of graph may more shortly be called just a lattice, mesh, or grid.
Graphe de Moore
En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F. Moore, qui avait tenté de décrire et classifier ces graphes. Un graphe de Moore est un graphe régulier de degré d et de diamètre k qui possède un nombre de sommets égal à la borne supérieure : De façon générale, le nombre de sommets d'un graphe de degré maximal d et de diamètre k est inférieur ou égal à cette valeur.
Cage (théorie des graphes)
En théorie des graphes, une cage est un graphe régulier minimal pour une maille donnée. Plus précisément, une (r,g)-cage est un graphe régulier minimal de degré r et de maille g. Quand le terme de g-cage est employé, il s'agit en fait d'une cage cubique, c'est-à-dire d'une (3,g)-cage. Un graphe degré-un n'a pas de cycle, et un graphe degré-deux connexe a une circonférence égale à son nombre de sommets, donc les cages ne présentent un intérêt que pour r ≥ 3.