Concept
Cage (théorie des graphes)
Concepts associés (6)
Nombre de croisements (théorie des graphes)
vignette| Une représentation du graphe de Heawood avec trois croisements. C'est le nombre minimum de croisements parmi toutes les représentations de ce graphe, qui a donc un nombre de croisements . En théorie des graphes, le nombre de croisements d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes.
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.
Maille (théorie des graphes)
En théorie des graphes, la maille d'un graphe est la longueur du plus court de ses cycles. Un graphe acyclique est généralement considéré comme ayant une maille infinie (ou, pour certains auteurs, une maille de −1). La maille d'un graphe est la longueur du plus court de ses cycles. Image:Petersen graph blue.svg|Le [[graphe de Petersen]] a une maille de 5 et est une cage. Image:Heawood_Graph.svg|Le [[graphe de Heawood]] a une maille de 6 et est une cage. Image:Frucht_graph.neato.
Graphe de Petersen
Le graphe de Petersen est, en théorie des graphes, un graphe particulier possédant et . Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois auparavant, en 1886.
Lexique de la théorie des graphes
NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.
Graphe complet
En théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens). Un graphe complet est un graphe dont tous les sommets sont adjacents. À isomorphisme près, il n'existe qu'un seul graphe complet non orienté d'ordre n, que l'on note .