Matroïde graphique

Un matroïde est défini comme une famille (ou ensemble) d'ensembles finis appelés ensembles indépendants du matroïde (ou plus simplement, indépendants).

Un matroïde M doit vérifier deux propriétés :

• L'hérédité : pour tout A dans M, pour tout B inclus dans A, B est dans M.
• L'échange : pour tout I, J dans M, si |I| < |J|, alors il existe j dans J\I tel que I U {j} soit dans M.

Ainsi dans le cas d'un graphe non orienté G, on note M(G) l'ensemble des forêts incluses dans G, si A est dans M(G), lui retirer des arêtes le fera rester dans M(G) (car retirer une arête d'un arbre va créer soit deux arbres si ce n'est pas une feuille, soit un arbre sans cette feuille et un sommet isolé). M(G) vérifie donc l'axiome d'hérédité.

Si I et J sont dans M(G) et que J a plus d'arêtes que I, alors il existe une arête de J reliant deux composantes connexes de I (raisonnement par l'absurde et lien nombre d'arêtes d'une forêt à son nombre de composantes connexes) ainsi en rajoutant cette arête à I on diminue son nombre de composantes connexes et on ne crée pas de cycle donc I reste une forêt. Ainsi M(G) vérifie l'axiome d'échange.

Donc M(G) est un matroïde appelé matroïde graphique de G. Plus généralement un matroïde est appelé graphique s'il est isomorphe au matroïde graphique d'un graphe, peu importe si leurs éléments sont des arêtes d'un graphe.

Les bases d'un matroïde graphique sont les forêts maximales de G (forêt de nombre d'arêtes total maximal) et les circuit de M(G) sont les cycles simples de G (cycles sans sous-cycles). Le rang dans M(G) d'un sous-ensemble d'arêtes de G est r(X) = n - c où n est le nombre de sommets dans le sous-graphe constitué des arêtes de X et c est son nombre de composantes connexes. Le co-rang d'un matroïde graphique est le rang des circuits de G (appelé nombre cyclomatique).

L'adhérence d'un ensemble d'arêtes S dans M(S), notée cl(S) est un fermé constitué des arêtes non indépendantes de S (c'est-à-dire, que leurs sommets d'arrivée sont connectés par un chemin dans S). Ce fermé peut être identifié avec la partition des sommets de G dans les composantes connexes du sous-graphe formé par S.

Chaque ensemble d'arêtes possède la même adhérence que S qui donne la même partition des sommets et cl(S) peut être retrouvé à partir de la partition des sommets car cl(S) prend les arêtes dont les sommets d'arrivée appartiennent à la même composante connexe.

Dans l'espace euclidien d'un matroïde, il y a une relation d'ordre ≤ entre les fermés, pour x et y des fermés, x ≤ y signifie que la partition du fermé x est un raffinement de celle de y.

Dans ce point de vue du matroïde graphique, le matroïde graphique d'un graphe complet à n sommet noté ${\displaystyle K_{n}}$ est très grand, car chaque sous-ensemble de sommets appartient au matroïde, car il peut être vu comme une composante connexe d'un sous-arbre (par exemple celui contenant les arêtes reliant chaque sommet du sous-ensemble). Ainsi les fermés de l'espace euclidien du matroïde graphique ${\displaystyle K_{n}}$ sont isomorphes a l'espace euclidien de partitions d'un ensemble à n éléments.

Comme les fermés de l'espace euclidien d'un matroïde sont exactement les espaces euclidiens géométriques cela implique donc que les espaces euclidiens de partitions le sont aussi.

Le matroïde graphique d'un graphe G est représentable, c'est-à-dire qu'il existe une matrice telle que le matroïde graphique de G soit égal au matroïde vectoriel de cette matrice.

Les indépendants d'un matroïde vectoriel sont les indices des colonnes formant une famille libre (ou linéairement indépendante).

Il peut être défini comme le matroïde vectoriel d'une matrice d'incidence orientée de G quelconque. Ces matrices ont une ligne pour chaque sommet et une colonne pour chaque arête. Chaque colonne (x,y) vaut 0 pour les lignes différentes de x et y vaut 1 soit en ligne x, soit en ligne y et -1 sur l'autre ligne (Il y a donc 2^(nombre d'arêtes) choix possibles).

Si un ensemble d'arêtes contient un cycle, alors la somme des colonnes correspondantes dans la matrice d'incidence orientée vaut 0 (quitte à multiplier certaines colonnes par -1 (pour changer le sens des arêtes)) ainsi la famille est liée (non libre) et ce n'est pas un indépendant.

Réciproquement, si l'ensemble d'arêtes induit une forêt, en résonnant par récurrence sur le nombre de sommets, puis en enlevant une feuille on peut montrer que les colonnes de la matrice d'incidence orientée forment une famille libre.

Ainsi le matroïde graphique de G est isomorphe au matroïde vectoriel défini précédemment (à une arête on associe son indice).

La méthode de représentation du matroïde graphique marche peut importe le corps sur lequel la matrice d'incidence est définie. Ainsi les matroïdes graphiques forment un sous ensemble des matroïdes réguliers, matroïdes qui ont une représentation sur tous les corps possibles.

Les fermés de l'espace euclidien d'un matroïde graphique peuvent être vus comme l'espace euclidien d'un arrangement d'hyperplans, le sous-ensemble des tresses dont les hyperplans sont les diagonales ${\displaystyle H_{i},_{j}=\{(x_{1},...,x_{n})\in \mathbb {R} ^{n},x_{i}=x_{j}\}}$. Si les sommets de G sont ${\displaystyle s_{1}}$, ... , ${\displaystyle s_{n}}$, alors l'hyperplan ${\displaystyle H_{i},_{j}}$ est rajouté si (${\displaystyle s_{i}}$,${\displaystyle s_{j}}$) est une arête de G.

Un matroïde est dit connecté s'il n'est pas la somme directe de deux matroïde plus petits, c'est-à-dire qu'il n'existe pas deux ensembles disjoints d'éléments du matroïde tels que la fonction de rang du matroïde vaut la somme du rang des deux sous-ensembles. Un matroïde graphique d'un graphe G est connecté si et seulement si G est connexe et 2-sommet-connexe.

Un matroïde est graphique si et seulement si son mineur n'inclut aucun des cinq mineurs interdits : le matroïde uniforme ${\displaystyle U_{4}^{2}}$, le plan de Fano ou son dual, ou le dual de ${\displaystyle M(K_{5})}$ et ${\displaystyle M(K_{3},_{3})}$ défini à partir du graphe complet ${\displaystyle K_{5}}$ et le graphe biparti complet ${\displaystyle K_{3},_{3}}$. Les trois premiers sont interdits pour les matroïdes réguliers et les deux derniers sont réguliers mais pas graphiques.

Si un matroïde est graphique alors son dual (un matroïde co-graphique) ne peut pas contenir un des cinq matroïdes interdits précédents. De plus, son dual doit aussi être régulier, et ne peut pas contenir un des deux matroïdes graphiques ${\displaystyle M(K_{5})}$ et ${\displaystyle M(K_{3},_{3})}$.

À cause de cette caractérisation et du théorème de Wagner caractérisant les graphes planaires comme les graphes avec aucun ${\displaystyle K_{5}}$ ou ${\displaystyle K_{3},_{3}}$ graphe mineur, cela implique qu'un matroïde graphique est co-graphique si et seulement si G est planaire, c'est le critère de planéité de Whitney. Si G est planaire alors le dual de M(G) est le matroïde graphique du dual de G. Bien que G puisse avoir plusieurs graphes duaux, leurs matroïdes graphiques sont tous isomorphes.