Liste de graphes

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 à $n$ sommets, aussi appelé $n$ -clique, est généralement noté $K_{n}$ ( $K$ est l'initiale du mot allemand komplett).

Graphes bipartis complets

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

$K 2 , 3 {\displaystyle K_{2,3}}$
$K_{2,3}$
$K 3 , 3 {\displaystyle K_{3,3}} , the utility graph$
$K_{3,3}$ , graphe des trois maisons
$K 2 , 4 {\displaystyle K_{2,4}}$
$K_{2,4}$
$K 3 , 4 {\displaystyle K_{3,4}}$
$K_{3,4}$

Graphes étoile

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

Graphes cycles

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

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

Graphes d'amitié

Le graphe d'amitié $F_{n}$ relie $n$ copies du graphe cycle $C_{3}$ par un sommet commun^[1].

Graphes roue

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

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

(premier) Snark de Blanuša
(deuxième) Snark de Blanuša
Snark à double étoile
Snark Fleur
(premier) Snark de Loupekine
(deuxième) Snark de Loupekine
Snark deSzekeres
Graphe de Tietze
Snark de Watkins

Graphes rappelant des formes réelles

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

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

Graphe web

Le graphe web $W_{n,r}$ est le graphe constitué de $r$ copies concentriques du graphe cycle $C_{n}$ , les sommets correspondants étant reliés par des « rayons ». Ainsi, $W_{n,1}$ est le graphe $C_{n}$ , et $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^[1]; pour une distance inférieure ou égale à 2 on obtient un graphe homard.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « List of graphs » (voir la liste des auteurs).

1 2 3 David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.
↑ (en) Gallian, J. A., « A Dynamic Survey of Graph Labeling », Electronic Journal of Combinatorics, DS6,‎ 2022 (lire en ligne)

Portail des mathématiques

[ref_auto_1-1] 1 2 3 David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.

[combinatorics.org-2] (en) Gallian, J. A., « A Dynamic Survey of Graph Labeling », Electronic Journal of Combinatorics, DS6,‎ 2022 (lire en ligne)

[1]

[2]