Matroïde graphique

Dans la théorie des matroïdes, un matroïde graphique (aussi appelé matroïde cyclique ou matroïde polygonal^{[réf. nécessaire]}) est un matroïde dont les ensembles indépendants sont des forêts (graphes dont les composantes connexes sont des arbres) dans un graphe fini non orienté fixé. Le matroïde dual d'un matroïde graphique est appelé matroïde co-graphique ou matroïde de lien.

Un matroïde à la fois graphique et co-graphique est parfois appelé matroïde planaire (mais il ne faut pas les confondre avec les matroïdes de rang 3 qui généralisent les points de configurations planaires), ce sont exactement les matroïdes graphiques formés à partir des graphes planaires.

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.

L'algorithme Glouton défini ci-dessous est optimal pour les matroïdes avec toute fonction de poids positive (la réciproque est vraie) :

(Soient M un matroïde, S un ensemble, et w une fonction de poids positive sur S)

def Glouton(M,S,w): 

X = [] 
Trier S par ordre décroissant de w
Pour i de 1 à len(S) faire:
    Si X U S[i] appartient à M alors:
        X = X U S[i]

retourner X

On peut transformer w en max(w) - w pour que le tri par ordre décroissant sur max(w) - w devienne un tri par ordre croissant pour w.

Une application connue de cet algorithme est l'algorithme de Kruskall calculant un arbre (ou une forêt) couvrant(e) de poids minimal(e).

Les algorithmes pour calculer un arbre couvrant de poids minimal ont été intensivement étudiés, on connait un moyen de résoudre le problème avec un nombre linéaire de comparaisons avec un algorithme randomisé, ou en temps linéaire dans lesquels les poids des arêtes sont des petits entiers, autorisant des opérations bit par bit en utilisant leurs représentations binaires. La meilleure borne qui a été montrée pour un algorithme déterministe est légèrement superlinéaire (Kruskall peut être codé en n*log(n)).

Plusieurs chercheurs ont étudié ces algorithmes pour tester si un matroïde donné est graphique. Par exemple l'algorithme de Tutte (1960) résout ce problème lorsque l'entrée est un matroïde binaire. Seymour (1981) résout ce problème pour un matroïde arbitraire à travers un oracle d'indépendance, déterminant si un ensemble est indépendant.

Certaines classes de matroïdes ont été définies à partir de familles de graphes très connues, en écrivant une caractérisation de ces graphes en termes faisant sens de façon plus générale pour les matroïdes. Cela inclut par exemple le matroïde biparti, dans lequel chacun des cycles est de longueur paire, et le matroïde Eulérien, qui peut être partitionné en cycles disjoints.

Un matroïde graphique est biparti si et seulement si c'est le matroïde graphique d'un graphe biparti.

Un matroïde graphique est Eulérien si et seulement si c'est le matroïde graphique d'un graphe Eulérien.

À l'intérieur des matroïdes graphiques (et plus généralement des matroïdes binaires) les deux classes précédentes sont duales, c'est-à-dire qu'un matroïde graphique est biparti si et seulement si son matroïde dual est Eulérien et un matroïde graphique est Eulérien si et seulement si son matroïde dual est biparti.

Les matroïdes graphiques sont des matroïdes rigides à une dimension, les matroïdes décrivant les degrés de liberté des structures d'un rayon rigide pouvant tourner librement autour des sommets où ils se rencontrent. En dimension 1, une telle structure a un degré de liberté égal au nombre de composantes connexes du graphe (le nombre de sommets moins le rang du matroïde) et en plus grande dimension le degré de liberté d'une structure de dimension d avec n sommets est d*n moins le rang du matroïde.

Dans les matroïdes rigides de dimension 2, le graphe de Laman joue le rôle des arbres couvrants dans les matroïdes graphiques, cependant la structure de matroïdes rigides en dimension supérieure ou égale à 2 n'est pas encore bien comprise^{[2],[3],[4],[5],[6],[7],[8],[9],[10],[11],[12],[13],[14],[15]}.

• Portail des mathématiques
• Portail de l'informatique théorique