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 De nombreux invariants sont conservés par certains préordres ou ordres partiels naturels sur les graphes :
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
Propriétés
Graphe connexe Graphe biparti Graphe planaire Graphe sans triangle Graphe parfait Graphe eulérien Graphe hamiltonien
Invariants entiers
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
Coefficient de clustering Centralité d'intermédiarité Taux d'expansion Densité d'un graphe Invariant de Parry-Sullivan
Polynômes
Polynôme caractéristique de la matrice d'adjacence Polynôme chromatique Polynôme de Tutte
Références
Catégorie:Invariant de graphe Catégorie:Théorie des graphes