Matroïde graphique

Un matroïde est défini comme une famille (ou ensemble) d'ensembles finies 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 sont nombre de composantes connexes et on ne créer 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, peut 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ête 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és 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és 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 sommets 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éfinit comme le matroïde vectoriel d'une matrice d'incidence orienté de G quelconque. Ces matrices ont une ligne pour chaque sommets et une colonne pour chaque arêtes. 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é vaut 0 (quitte à multiplier certaines colonne 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ête 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é 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 lui 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 vu 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 rajouter 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 petit, c'est-à-dire qu'il n'existe pas deux ensembles disjoints d'élément du matroïde tel que la fonction de rang du matroïde vaut la somme du rang des deux sous-ensemble. 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'inclue aucun des cinq mineurs interdit : 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égulier, et les deux derniers sont réguliers mais pas graphique.

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 graphique ${\displaystyle M(K_{5})}$ et ${\displaystyle M(K_{3},_{3})}$.

A 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 dual, leurs matroïdes graphiques sont tous isomorphes.

L'algorithme Glouton défini ci-dessous est optimal pour les matroïdes avec toutes 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 comparaison 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é montrer pour un algorithme déterministe est légèrement superlinéaire (Kruskall peut être coder en n*log(n)).

Plusieurs chercheurs ont étudier 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 a 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 graphe très connues, en écrivant une caractérisation de ces graphes en termes faisant sens de façon plus général pour les matroïdes. Cela inclus 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.

A l'intérieur des matroïdes graphique (et plus généralement des matroïdes binaire) les deux classes précédentes sont duales, c'est-à-dire qu'un matroïde graphique est bipartie 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 graphique sont des matroïdes rigide à une dimension, les matroïdes décrivant les degrés de libertés 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 sommet 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 couvrant dans les matroïdes graphique, cependant la structure de matroïdes rigide en dimension supérieure ou égales à 2 n'est pas encore bien comprise^{[2],[3],[4],[5],[6],[7],[8],[9],[10],[11],[12],[13],[14],[15]}.