Invariant de graphe
En théorie des graphes, un invariant de graphe est une quantité qui n'est pas modifiée par isomorphisme de graphes. Un invariant de graphe ne dépend donc que de la structure abstraite et pas des particularités de la représentation comme l'étiquetage ou le tracé.
Propriétés des propriétés modifier
De nombreux invariants sont conservés par certains préordres ou ordres partiels naturels sur les graphes[1] :
- Une propriété est monotone si elle est héritée par les sous-graphes. Le caractère biparti, sans triangle, ou planaire sont des exemples de propriétés monotones.
- Une propriété est héréditaire si elle est héritée par les sous-graphes induits. Toute propriété monotone est donc héréditaire. Le caractère parfait est un exemple de propriété héréditaire non monotone.
- Une propriété est close par mineur si elle est héritée par les mineurs. Le caractère planaire est un exemple de propriété close par mineur.
Exemples modifier
Propriétés modifier
- Graphe connexe
- Graphe biparti
- Graphe planaire
- Graphe sans triangle
- Graphe parfait
- Graphe eulérien
- Graphe hamiltonien
Invariants entiers modifier
- Ordre et taille (nombre de sommets et d'arêtes respectivement)
- Nombre de composantes connexes
- Diamètre
- Rayon
- Maille
- Sommet-connexité
- Arête-connexité
- Nombre chromatique
- Nombre achromatique
- Indice chromatique
- Taille du stable maximum
- Nombre de clique
- Arboricité
- Dégénérescence
- Dimension
- Nombre de Strahler
- Nombre domatique
Invariants réels modifier
- Coefficient de clustering
- Centralité d'intermédiarité
- Taux d'expansion
- Densité d'un graphe
- Invariant de Parry-Sullivan
Polynômes modifier
Références modifier
- (en) László Lovász, Large Networks and Graph Limits, American Mathematical Society, , 475 p. (ISBN 9780821890851, lire en ligne)
