Invariant de graphe

Dans cet article, nous aborderons Invariant de graphe dans une perspective complète et détaillée, afin de fournir à nos lecteurs une vision complète et enrichissante sur ce sujet. Dans cette optique, nous explorerons différentes facettes, études et opinions liées à Invariant de graphe, dans le but de proposer une analyse globale et actualisée. De son origine à son évolution actuelle, en passant par son impact sur la société et sa pertinence dans différents domaines, cet article se veut une source de connaissances enrichissante pour tous ceux qui souhaitent entrer dans le monde de 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

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

Propriétés

Invariants entiers

Invariants réels

Polynômes

Références

  1. ↑ (en) László Lovász, Large Networks and Graph Limits, American Mathematical Society, , 475 p. (ISBN 9780821890851, lire en ligne)