Liste de graphes

Graphes complets

Le graphe complet à ${\displaystyle n}$ sommets, aussi appelé ${\displaystyle n}$-clique, est généralement noté ${\displaystyle K_{n}}$ (${\displaystyle K}$ est l'initiale du mot allemand komplett).

• 
  ${\displaystyle K_{1}}$
• 
  ${\displaystyle K_{2}}$
• 
  ${\displaystyle K_{3}}$
• 
  ${\displaystyle K_{4}}$
• 
  ${\displaystyle K_{5}}$
• 
  ${\displaystyle K_{6}}$
• 
  ${\displaystyle K_{7}}$
• 
  ${\displaystyle K_{8}}$

Graphes bipartis complets

Le graphe biparti complet est généralement noté ${\displaystyle K_{n,m}}$ . Pour ${\displaystyle n=1}$ on obtient le graphe en étoile ci-dessous. Le graphe ${\displaystyle K_{2,2}}$ est le 4-cycle ${\displaystyle C_{4}}$ (le graphe carré) présenté ci-dessous.

• 
  ${\displaystyle K_{2,3}}$
• 
  ${\displaystyle K_{3,3}}$, graphe des trois maisons
• 
  ${\displaystyle K_{2,4}}$
• 
  ${\displaystyle K_{3,4}}$

Graphes étoile

Le graphe étoile ${\displaystyle S_{n}}$ est le graphe biparti complet ${\displaystyle K_{1,n}}$ (${\displaystyle S}$ est l'initiale du mot allemand Stern). L'étoile ${\displaystyle S_{3}}$ est le graphe griffe.

Graphes cycles

Le graphe cycle à ${\displaystyle n}$ sommets, ou n-cycle, est généralement noté ${\displaystyle C_{n}}$. On le désigne aussi par graphe polygone ou n-gone.

• 
  ${\displaystyle C_{3}}$ graphe triangle
• 
  ${\displaystyle C_{4}}$ graphe carré
• 
  ${\displaystyle C_{5}}$ graphe pentagone
• 
  ${\displaystyle C_{6}}$ graphe hexagone

Graphes d'amitié

Le graphe d'amitié ${\displaystyle F_{n}}$ relie ${\displaystyle n}$ copies du graphe cycle ${\displaystyle C_{3}}$ par un sommet commun.

Graphes roue

Le graphe roue ${\displaystyle W_{n}}$ est un graphe à ${\displaystyle n}$ sommets construit en reliant un seul sommet à chaque sommet d'un ${\displaystyle n}$-cycle ( ${\displaystyle W}$ est l'initiale du mot anglais wheel).

Voir aussi les graphes chemin et les graphes grille.

Graphes polyédriques réguliers

Le graphe tétraédrique est le graphe complet à quatre sommets.

• 
  Graphe hexaédrique
• 
  Graphe octaédrique
• 
  Graphe dodécaédrique
• 
  Graphe icosaédrique

Graphes polyédriques réguliers tronqués

• 
  Graphe tétraédrique tronqué
• 
  Graphe hexaédrique tronqué
• 
  Graphe octaédrique tronqué
• 
  Graphe dodécaédrique tronqué
• 
  Graphe icosaédrique tronqué

Autres graphes polyédriques semi-réguliers

• 
  Graphe cuboctaédrique
• 
  Graphe icosidodécaédrique
• 
  Graphe rhombicuboctaédrique

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 ${\displaystyle H=S/2-10}$ faces hexagonales, où ${\displaystyle S=20+2H}$ est le nombre de sommets. Le nombre de faces est donc ${\displaystyle F=12+H}$, et le nombre d'arêtes ${\displaystyle A=30+3H}$, d'après la formule d'Euler ${\displaystyle S-A+F=2}$.

• 
  Graphe fullerène à 20 sommets (graphe dodécaédrique),
• 
  à 24 sommets (Graphe trapézoédrique tronqué hexagonal),
• 
  à 26 sommets,
• 
  à 60 sommets (graphe icosaédrique tronqué),
• 
  à 70 sommets.

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 fortement réguliers

Voir à graphe fortement régulier.

• 
  Graphe de Clebsch
• 
  Graphe de Petersen
• 
  Graphe de Hall-Janko
• 
  Graphe de Hoffman-Singleton
• 
  Graphe de Higman-Sims
• 
  Graphe de Paley d'ordre 13
• 
  Graphe de Shrikhande
• 
  Graphe de Schläfli
• 
  Graphe de Brouwer-Haemers
• 
  Graphe local de McLaughlin
• 
  Graphe de Perkel
• 
  Graphe de Gewirtz

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.

• 
  Graphe de Heawood
• 
  Graphe de Möbius-Kantor
• 
  Graphe de Pappus
• 
  Graphe de Desargues
• 
  Graphe de Nauru
• 
  Graphe de Coxeter
• 
  Graphe de Tutte-Coxeter
• 
  Graphe de Dyck
• 
  Graphe de Klein
• 
  Graphe de Foster
• 
  Graphe de Biggs-Smith
• 
  Graphe de Rado

Graphes semi-symétriques

Voir à graphe semi-symétrique.

• 
  Graphe de Folkman
• 
  Graphe de Gray
• 
  Graphe de Ljubljana
• 
  12-cage de Tutte

Graphe engrenage

Le graphe engrenage, noté ${\displaystyle G_{n}}$ (G comme "gear"), est le graphe obtenu en insérant un sommet entre chaque paire de sommets adjacents d'un graphe roue ${\displaystyle W_{n}}$. Ainsi, ${\displaystyle G_{n}}$ possède ${\displaystyle 2n+1}$ sommets et ${\displaystyle 3n}$ 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é ${\displaystyle H_{n}}$ (H comme "helm"), est le graphe obtenu en ajoutant une arête à chaque nœud d'un graphe roue ${\displaystyle W_{n}}$.

Graphe web

Le graphe web ${\displaystyle W_{n,r}}$ est le graphe constitué de ${\displaystyle r}$ copies concentriques du graphe cycle ${\displaystyle C_{n}}$, les sommets correspondants étant reliés par des « rayons ». Ainsi, ${\displaystyle W_{n,1}}$ est le graphe ${\displaystyle C_{n}}$, et ${\displaystyle W_{n,2}}$ 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.