Cet article présente une liste non exhaustive de graphes, classés par types, présentés avec une de leurs représentations graphiques.

Familles infinies de graphes

Graphes complets Le graphe complet à sommets, aussi appelé -clique, est généralement noté ( est l'initiale du mot allemand komplett).

Graphes bipartis complets Le graphe biparti complet est généralement noté . Pour on obtient le graphe en étoile ci-dessous. Le graphe est le 4-cycle (le graphe carré) présenté ci-dessous.

Graphes étoile Le graphe étoile est le graphe biparti complet ( est l'initiale du mot allemand Stern). L'étoile est le graphe griffe. centré|vignette|500x500px

Graphes cycles Le graphe cycle à sommets, ou n-cycle, est généralement noté . On le désigne aussi par graphe polygone ou n-gone.

Graphes d'amitié Le graphe d'amitié relie copies du graphe cycle par un sommet communDavid Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.. centré|vignette|450x450px|Les graphes d'amitié F2 (graphe papillon), F3 et F4 .

Graphes roue Le graphe roue est un graphe à sommets construit en reliant un seul sommet à chaque sommet d'un -cycle ( est l'initiale du mot anglais wheel). centré|vignette|320x320pxVoir aussi les graphes chemin et les graphes grille.

Graphes polyédriques et polytopiques Graphes polyédriques réguliers Le graphe tétraédrique est le graphe complet à quatre sommets.

Graphes polyédriques réguliers tronqués

Autres graphes polyédriques semi-réguliers ainsi que le graphe rhombicosidodécaédrique, le graphe cuboctaédrique tronqué, le graphe icosidodécaédrique tronqué, le graphe hexaédrique adouci, le graphe dodécaédrique adouci.

Graphes polyédriques semi-réguliers de seconde espèce Ce sont les graphes duaux des précédents.

Le graphe triakitétraédrique, le graphe triakioctaédrique, le graphe triaki-icosaédrique,

le graphe tétrakihexaédrique, le graphe pentakidodécaédrique,

le graphe dodécaédrique rhombique, le graphe triacontaédrique rhombique,

le graphe hexacontaédrique trapézoïdal, le graphe icositétraédrique trapézoïdal,

le graphe hexakioctaédrique, le graphe hexaki-icosaédrique,

le graphe icositétraédrique pentagonal, le graphe hexacontaédrique pentagonal.

Graphes polytopiques

Les graphes associés aux simplexes sont les graphes complets. Les graphes associés aux hypercubes sont les graphes hypercubiques, dont le graphe tesseract en dimension 4. Les graphes associés aux hyperoctaèdres sont les graphes hyperoctaédriques, dont le graphe hexadécachorique en dimension 4.

Graphes fullerène Les graphes fullerène sont les diagrammes de Schlegel des fullerènes. Ce sont des graphes polyédriques à faces d'ordre 5 ou 6 (y compris la face externe). Plus précisément, ils ont exactement 12 faces pentagonales et faces hexagonales, où est le nombre de sommets. Le nombre de faces est donc , et le nombre d'arêtes , d'après la formule d'Euler .Un algorithme permettant de générer tous les graphes fullerènes non isomorphes ayant un nombre donné de faces hexagonales a été développé par G. Brinkmann et A. Dress. G. Brinkmann a également fourni une implémentation disponible gratuitement, appelée fullgen .

Graphes présentant des régularités

Graphes fortement réguliers Voir à graphe fortement régulier.

Graphes symétriques Un graphe symétrique est un graphe possédant un automorphisme transformant tout couple de sommets adjacents en n'importe quel autre couple ; le recensement de Foster répertorie tous les petits graphes 3-réguliers symétriques. Tout graphe fortement régulier est symétrique, mais la réciproque est fausse.

Graphes semi-symétriques Voir à graphe semi-symétrique.

Snarks

Un snark est un graphe cubique sans pont qui nécessite quatre couleurs pour toute coloration correcte des arêtes. Le plus petit snark est le graphe de Petersen, déjà mentionné ci-dessus.

Graphes rappelant des formes réelles

Autres graphes remarquables

Autres graphes non répertoriés dans wikipedia Cette liste présente des graphes et des familles de graphes ne possédant pas d'article Wikipédia.

Graphe engrenage vignette| Le graphe engrenage, noté (G comme "gear"), est le graphe obtenu en insérant un sommet entre chaque paire de sommets adjacents d'un graphe roue . Ainsi, possède sommets et arêtes. Les graphes d'engrenage sont des exemples de "squaregrafs" et jouent un rôle clé dans la caractérisation des graphes carrés comme "forbidden grafs". Les graphes d'engrenages sont également appelés graphes roue dentés ou graphes roue bipartites.

Graphe gouvernail Le graphe gouvernail, noté (H comme "helm"), est le graphe obtenu en ajoutant une arête à chaque nœud d'un graphe roue .

Graphe web vignette|100x100px|Le graphe Web est le graphe hexaédrique. Le graphe web est le graphe constitué de copies concentriques du graphe cycle , les sommets correspondants étant reliés par des « rayons ». Ainsi, est le graphe , et est le graphe associé au n-prisme .

Graphe chenille, graphe homard Un graphe chenille est un arbre dans lequel tous les sommets sont à une distance inférieure ou égale à 1 du chemin central; pour une distance inférieure ou égale à 2 on obtient un graphe homard.

Notes et références

Catégorie:Graphe remarquable Catégorie:Famille de graphes Catégorie:Liste en rapport avec les mathématiques Catégorie:Pages avec des traductions non relues