Mineur (théorie des graphes)La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. Soit un graphe non orienté fini. Un graphe est un mineur de s'il peut être obtenu en contractant des arêtes d'un sous-graphe de .
William TutteWilliam Thomas Tutte ( – ) est un mathématicien et cryptanalyste britannique, puis canadien. Pendant la Seconde Guerre mondiale, il décrypte l'un des principaux codes allemands, ce qui a un impact significatif sur le succès des opérations alliées. Il apporte aussi des contributions importantes en mathématiques, dont un travail fondateur en combinatoire, notamment en théorie des matroïdes et en théorie des graphes. Tutte est né à Newmarket dans le Suffolk, d'un père jardinier.
Forbidden graph characterizationIn graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.
Automorphisme de graphevignette|On peut définir deux automorphismes sur le graphe maison : l'identité et la permutation qui échange les deux « murs » de la « maison ». En mathématiques et en particulier en théorie des graphes, un automorphisme de graphe est une bijection de l'ensemble des sommets vers lui-même qui préserve l'ensemble des arêtes. On peut voir l'automorphisme de graphes comme un isomorphisme de graphes du graphe dans lui-même. On peut en général s'arranger pour mettre en évidence visuellement les automorphismes de graphes sous forme de symétries dans le tracé du graphe.
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.
Hamiltonian pathIn the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path.
Graphe de KneserEn théorie des graphes, les graphes de Kneser forment une famille infinie de graphes. Le graphe de Kneser KGn,k est un graphe simple dont les sommets correspondent aux sous-ensembles à k éléments d'un ensemble à n éléments. Deux sommets sont reliés s'ils correspondent à des sous-ensembles disjoints. Son ordre est donc égal , le nombre de combinaison de k parmi n, et il est régulier de degré . En 1955, le mathématicien Martin Kneser se pose la question suivante : Kneser conjecture que ce n'est pas possible et le publie sous forme d'un exercice.
Snark (graphe)En théorie des graphes, une branche des mathématiques, un snark est un graphe cubique connexe, sans isthme et d'indice chromatique égal à 4. En d'autres termes, c'est un graphe dans lequel chaque sommet a trois voisins, et dont les arêtes ne peuvent pas être colorées avec seulement 3 couleurs sans que deux arêtes de même couleur ne se rencontrent en un même sommet (d'après le théorème de Vizing, l'indice chromatique d'un graphe cubique est 3 ou 4). Pour éviter les cas triviaux, on exige souvent de plus que les snarks aient une maille d'au moins 5.
Graphe distance-régulierEn 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 sommet-transitifEn 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.
