Décomposition algorithmique des graphes

Dualité et largeur arborescente 

 Définition et théorème de dualité

La dualité pour les graphes planaires est une notion classique (voir par exemple [Die00]). Les sommets du graphe dual G∗ d’un graphe planaire G 8.4. Dualité et largeur arborescente 123 correspondent aux faces de G et à chaque arête de G qui borde les faces f1 et f2 est associée l’arête duale (f1, f2). Notons que l’arête duale d’un isthme – c’est-à-dire une arête qui déconnecte le graphe – est une boucle. Dans le cas des hyper-graphes, nous pourrions choisir de représenter les boucles par une hyper-arête à un seul sommet mais alors une hyper-arête e et son hyperarête duale e ∗ n’auraient pas nécessairement le même nombre d’extrémités et retrouver e à partir de e ∗ deviendrait impossible. Il est donc important que les hyper-arêtes d’un hyper-graphe planaire soient des multi-ensembles de sommets. La figure 8.15 présente un graphe et un hyper-graphe plan ainsi que leurs duaux respectifs. Définition 8.40 (Hyper-graphe dual) Soient GΣ = (VΣ ∪ AΣ, EΣ) un hyper-graphe plan et FΣ l’ensemble des centres des faces de GΣ. Pour chaque face F de GΣ dont le centre est f et chaque sommet arête a de AΣ incident à F, il est possible de choisir un représentant par classe d’homotopie de chemins de a à f dans F de telle sorte que l’hyper-graphe G∗ Σ = (FΣ ∪ AΣ, E∗ Σ ) dont les arêtes sont ces représentants soit plan. Cet hyper-graphe plan est l’hyper-graphe dual de GΣ. La figure de gauche présente un graphe plan et son dual. Celle de droite présente un hyper-graphe plan ainsi que son dual. Fig. 8.15 – Graphes et hyper-graphes duaux Théorème 8.41 Soit GΣ = (VΣ ∪ AΣ, EΣ) un hyper-graphe plan. 

 Terminologie

Avant toute chose, il est bon de poser clairement les définitions que nous utilisons par la suite. Les notions que nous introduisons ici sont pour la plupart très classiques pour les graphes mais certaines présentent des subtilités quand nous les adaptons aux hyper-graphes. De plus, la notion même d’hyper-graphe que nous utilisons n’est pas la notion usuelle.   Fig. 2.1 – Utilisation des hyper-graphes pour les démonstrations Définitions 2.1 (Hyper-graphe, graphe, graphe d’incidence) Un hyper-graphe est un couple que nous notons généralement G = (V, E). Les ensembles V et E sont finis. Les éléments de V sont les sommets de G et ceux de E sont les hyper-arêtes de G. Chaque élément de E est un multi-ensemble de sommets de G ; c’est-à-dire un ensemble de sommets qui peut contenir plusieurs fois le même sommet. La taille d’une plus grosse hyper-arête de G est notée γ(G) si les sommets sont comptés avec multiplicité et β(G) sinon. Si G est un hyper-graphe, nous notons V (G) et E(G) ses ensembles de sommets et d’hyper-arêtes. Un graphe est un hyper-graphe dont toutes les hyper-arêtes sont de taille deux. Nous notons xy l’arête {x, y}. Soit G = (V, E) un hyper-graphe. Le multigraphe dont les sommets sont les éléments de V ∪ E et dont les arêtes sont les couples (x, e) où e est une hyper-arête de G et où x est une extrémité de e est le graphe d’incidence de G. La définition d’hyper-graphe que nous donnons correspond plutôt à des « multi-hyper-graphes ». Mais le plus souvent, nous pouvons ne considérer que des « vrais » hyper-graphes, c’est-à-dire des hyper-graphes dans lesquels les hyper-arêtes sont simplement des ensembles de sommets. En effet, si nous retirons les occurrences multiples de sommets dans les « multi-hyperarêtes » d’un « multi-hyper-graphe », nous obtenons un « vrai » hyper-graphe. Le plus souvent, nous pouvons identifier un « multi-hyper-graphe » à son hyper-graphe induit. Cependant, au chapitre 8, cette identification ne fonctionne plus car la notion de dualité dans les (hyper-)graphes planaires fait naturellement apparaître des multi-(hyper-)arêtes que nous ne pouvons pas ignorer. Définitions 2.2 (Adjacence, incidence, voisinage, degré) Deux sommets distincts d’un hyper-graphe G sont adjacents s’ils appartiennent à une même hyper-arête. Une hyper-arête est incidente à ses sommets ; elle relie ses sommets. Le voisinage d’un sommet x de V est l’ensemble NG(x) (ou simplement N(x)) des sommets qui lui sont adjacents. Plus généralement, pour X inclus dans V (G), nous notons NG(X) le voisinage de X c’est-à-dire l’ensemble des sommets de V \X adjacents à au moins un sommet de X. Le degré d’un sommet est le cardinal de son voisinage. Définitions 2.3 (Sous-structures et sur-structures) Soit G = (V, E) un hyper-graphe. L’hyper-graphe G0 égal à (V, E0 ) avec E0 inclus dans E est un hypergraphe partiel de G. Dans ce cas G est un sur-hyper-graphe de G0 . Si V 0 est inclus dans V , le sous-hyper-graphe de G induit par l’ensemble de sommets V 0 est l’hyper-graphe G[V 0 ] égal à (V 0 , E0 ) avec E0 , l’ensemble des hyper-arêtes de E dont toutes extrémités sont dans V 0 . De façon analogue, si E0 est inclus dans E, le sous-hyper-graphe de G induit par E0 est l’hyper-graphe G[E0 ] égal à (V 0 , E0 ) avec V 0 l’ensemble des extrémités des hyper-arêtes de E0 . Un hyper-graphe de cette forme est un sous-hypergraphe de G induit par l’ensemble V 0 ou l’ensemble E0 . Un hyper-graphe G0 est un sous-hyper-graphe partiel de G si c’est un hyper-graphe partiel d’un sous-hyper-graphe de G. Les notions de sous-graphe, sous-graphe partiel et de sur-graphe sont les notions analogues pour les graphes. Définitions 2.4 (Chaîne, cycle, corde, longueur) Une chaîne µ d’un hyper-graphe G est une suite (x1, . . . , xl) de sommets de G telle que deux sommets consécutifs de µ soient toujours adjacents. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. Si les sommets xl et x1 sont égaux, µ est un cycle. Un cycle (x1, . . . , xl) est élémentaire si la chaîne (x1, . . . , xl−1) est élémentaire. Une corde d’une chaîne ou d’un cycle µ est une hyper-arête qui relie deux sommets non consécutifs sur µ. La longueur d’une chaîne est le nombre de sommets que contient cette chaîne moins un. Définitions 2.5 (Connexité, composantes connexes) Soit G un hyper-graphe. La relation « il existe une chaîne passant par les sommets x et y » est une relation d’équivalence. Les classes d’équivalence pour cette relation sont les composantes connexes de G. Un hyper-graphe est connexe s’il ne possède qu’une seule composante connexe. 10 Chapitre 2. Préliminaires Définitions 2.6 (Arbre, arbre enraciné, nœud, père, fils) Un arbre est un graphe connexe sans cycle. Nous appellons nœuds les sommets d’un arbre. Un arbre enraciné est un arbre dont un sommet – la racine – est particularisé. Un tel arbre induit une relation d’ordre partiel sur ses nœuds. Le plus petit antécédent et les plus grands successeurs d’un nœud x, s’ils existent, sont respectivement le père et les fils de x. Nous notons généralement les arbres T et les arbres enracinés ∗T. Définitions 2.7 (Clique, cliques maximales) Une clique est un hyper-graphe dans lequel tous les sommets sont deux à deux adjacents. Une clique d’un hyper-graphe est un sous-graphe qui est une clique. Une clique maximale d’un hyper-graphe G est une clique de G maximale pour l’inclusion.

Séparateurs minimaux et frontières

Comme nous l’avons déjà mentionné, l’objet de cette thèse est l’étude de certaines décompositions des hyper-graphes. Pour décomposer les hypergraphes, nous allons utiliser les notions de séparateur minimal et de séparation que nous introduisons ici. 2.2.1 Séparateurs minimaux Définitions 2.8 (Séparateur minimal) Soit G un hyper-graphe. Pour a et b deux sommets de G, un ensemble S est un a, b-séparateur de G si a et b ne sont pas dans une même composante connexe de G\S. Un a, b-séparateur minimal de G est un a, b-séparateur de G qui est minimal pour l’inclusion. Un ensemble S est un séparateur minimal de G s’il existe deux sommets a et b de G tels que S soit un a, b-séparateur minimal. Nous notons ∆G l’ensemble des séparateurs minimaux de G. Si Ω est inclus dans V (G), ∆G(Ω) désigne l’ensemble des séparateurs minimaux de G inclus dans Ω. Remarquons tout de suite que deux séparateurs minimaux peuvent être inclus l’un dans l’autre. Dans la figure 2.2 l’ensemble {e, f, g} est un a, bséparateur minimal, {f, g} est un j, k-séparateur minimal et {g} est un h, iséparateur minimal. Définition 2.9 (Composante pleine) Soit S un ensemble de sommets d’un hyper-graphe G. Une composante connexe C de G\S est pleine par rapport à S si son voisinage N(C) est égal à S. Nous notons CG(S) l’ensemble des composantes connexes de G\S. La composante connexe de G\S contenant un sommet a n’appartenant pas 2.2. Séparateurs minimaux et frontières 11 a b d c e f g h i j k Fig. 2.2 – Séparateurs minimaux à S est notée C a G(S). Nous notons C ∗ G(S) l’ensemble des composantes pleines par rapport à S. Dans la figure 2.2, les composantes connexes de G\S sont {a, d, i, j}, {b, c}, {h} et {k}. Les composantes pleines sont {a, d, i, j} et {b, c}. Nous utilisons beaucoup la caractérisation suivante des séparateurs minimaux à l’aide de composantes pleines. Propriété 2.10 Soient G un hyper-graphe, S un ensemble de sommets de G et C et D deux composantes connexes de CG(S). Les propositions suivantes sont équivalentes : (i) C et D sont pleines par rapport à S ; (ii) il existe a dans C et b dans D tels que S soit un a, b-séparateur minimal ; (iii) pour tout a dans C et b dans D, S est un a, b-séparateur minimal. Montrons que i ⇒ iii. Soient a dans C, b dans D et v dans S. Comme C est une composante connexe pleine de G\S par rapport à S, il existe une chaîne pav de a à v dans C ∪ {v}. De même, il existe une chaîne pvb dans D ∪ {v}. En concaténant pav et pvb, nous obtenons une chaîne de a à b dans C ∪ D ∪ {v}. Par conséquent S\{v} n’est pas un a, b-séparateur. Le sommet v étant quelconque, S est bien un séparateur minimal. L’implication iii ⇒ ii est évidente. Montrons l’implication ii ⇒ i. Soit a dans C et b dans D tels que S soit un a, b-séparateur minimal. Le voisinage de C sépare tout sommet de C de tout sommet de D. Par conséquent, N(C) est un a, b-séparateur. Le a, b-séparateur S étant minimal, les ensembles S et N(C) sont égaux. La composante C est donc pleine par rapport à S. De même, D est pleine par rapport à S. Nous en déduisons directement : 12 Chapitre 2. Préliminaires Corollaire 2.11 Soit G un hyper-graphe. Un ensemble de sommets S est un séparateur minimal de G si et seulement si il admet au moins deux composantes pleines. Dans le découpage récursif des hyper-graphes, les séparateurs que nous utilisons possèdent certaines propriété de parallélisme que nous définissons ici. Définitions 2.12 (Parallélisme de séparateurs minimaux) Soient S et T deux ensembles de sommets d’un hyper-graphe G. Nous dirons que S est parallèle à T si S est inclus dans un ensemble de la forme T ∪C où C est une composante connexe de G\T. Dans le cas contraire, c’est-à-dire si S rencontre au moins deux composantes connexes de G\T, nous dirons que S croise T. Lemme 2.13 Les relations de croisement et de parallélisme de séparateurs minimaux sont symétriques. Notons d’abord que si la relation de croisement est symétrique, alors celle de parallélisme l’est aussi. Soient S et T deux séparateurs minimaux d’un hyper-graphe G et supposons que S croise T. Montrons alors que T croise S. Soient a et b deux sommets de S qui se trouvent dans deux composantes connexes de G\T. D’après la propriété 2.10, il existe C et D deux composantes pleines dans C ∗ G(S). Par définition, a et b sont dans le voisinage de C. Il existe donc une chaîne µ C ab de a à b dans C ∪ {a, b}. Comme T est un a, b-séparateur, il intersecte la chaîne µ C ab et donc la composante connexe C. Les composantes connexes C et D jouant un rôle symétrique, T intersecte aussi D et donc T croise S. La propriété suivante fournit une caractérisation du parallélisme pour les séparateurs minimaux. Propriété 2.14 Soient S et T deux séparateurs minimaux d’un hyper-graphe G. Deux séparateurs minimaux S et T sont parallèles si et seulemenent si il existe une composante connexe CT de G\T telle que S soit inclus dans CT ∪ N(CT ). Soient S et T deux séparateurs minimaux d’un hyper-graphe G. Si S est inclus dans CT ∪ N(CT ) où C est une composante connexe de G\T, alors S croise au plus une composante connexe de G\T : S est parallèle à T. Réciproquement, supposons que S soit parallèle à T. Soient CS et DS deux composantes pleines dans C ∗ G(S). Comme, d’après le lemme 2.13, la relation de parallélisme est symétrique, T est parallèle à S et ne peut pas rencontrer à la fois CS et DS, nous pouvons donc supposer que CS et T sont disjoints. Puisque l’ensemble CS induit un sous-hyper-graphe connexe de G 2.2. Séparateurs minimaux et frontières 13 et que CS et T sont disjoints, CS est inclus dans une composante connexe CT de G\T. Comme S est le voisinage de CS, S est inclus dans CT ∪N(CT ).