Aller au contenu principal
graphesFamilles remarquables

Familles remarquables

Ce que ce chapitre apporte

  • Reconnaître un graphe biparti, un graphe d'intervalles, un graphe cordal, un graphe planaire.
  • Enchaîner les implications entre ces familles.
  • Définir un graphe parfait et dire ce que la perfection garantit.
  • Employer LexBFS pour obtenir un ordre parfait d'élimination.
  • Colorer un graphe d'intervalles de façon optimale en temps linéaire.
  • Utiliser la formule d'Euler et la conséquence sur les graphes planaires.
Où on va
Le chapitre précédent s'est achevé sur un constat inconfortable : la coloration est NP-complète, et le glouton dépend d'un ordre qu'on ne sait pas choisir. La sortie n'est pas un algorithme plus malin, c'est un changement de regard. Les graphes qu'on rencontre vraiment ne sont presque jamais quelconques : ils viennent d'intervalles de temps, de contraintes géométriques, de relations bipartites. Sur ces familles, les problèmes difficiles redeviennent faciles, et exactement.

Bipartis

Rappel

Un graphe est biparti si ses sommets se répartissent en deux groupes tels que toute arête aille d'un groupe à l'autre.

Équivalence : un graphe est biparti si et seulement si il n'a aucun cycle de longueur impaire.

C'est la famille la plus simple, et déjà tout devient facile : χ=2\chi = 2 dès qu'il y a une arête, le test se fait par un BFS bicolore en Θ(n+m)\Theta(n + m), et les problèmes de couplage y ont des solutions polynomiales.

Graphe non orienté6 sommets, 6 arêtes
Machine1Piece1Piece2Machine2Piece3Machine3

Graphes d'intervalles

Définition

Un graphe est un graphe d'intervalles si l'on peut associer à chaque sommet un intervalle de la droite réelle, de sorte que deux sommets soient adjacents exactement quand leurs intervalles se coupent.

C'est la famille du chapitre précédent : tâches sur un axe de temps, réservations de salle, expression de gènes, allocation de registres dans un compilateur. Sa propriété fondamentale est visible directement :

Clique et recouvrement, c'est la même chose
Dans un graphe d'intervalles, une clique correspond à un ensemble d'intervalles se coupant deux à deux. Or, sur une droite, des intervalles deux à deux sécants ont toujours un point commun : c'est le théorème de Helly en dimension 1.
Donc $\omega(G)$ vaut exactement le recouvrement maximal, c'est-à-dire le nombre maximal d'intervalles empilés au-dessus d'un même instant. Cela se calcule en triant les bornes, en $O(n \log n)$, sans jamais construire le graphe.
Compter sans dessiner
Intervalles : A[0,4), B[1,3), C[2,6), D[5,9), E[7,10), F[8,12), G[11,14).
À l'instant 2, trois intervalles sont ouverts : A, B, C. Nulle part il n'y en a quatre.
Donc $\omega = 3$, donc au moins 3 machines. Et l'on va voir qu'il en suffit exactement 3.

Graphes cordaux

Définition

Un graphe est cordal (ou triangulé) si tout cycle de longueur au moins 4 possède une corde, c'est-à-dire une arête reliant deux sommets non consécutifs du cycle.

Autrement dit : ses seuls cycles sans corde sont des triangles.

Le cycle à quatre sommets ci-dessous n'est pas cordal : aucune diagonale ne le traverse.

Graphe non orienté4 sommets, 4 arêtes
ABCD

Ajoutez la corde A -- C et il le devient : le carré se décompose en deux triangles.

Graphe non orienté4 sommets, 5 arêteschemin mis en évidence
ABCD
Sommet simplicial et ordre parfait d'élimination

Un sommet est simplicial si ses voisins forment une clique.

Un ordre parfait d'élimination est un ordre des sommets tel que chacun soit simplicial dans le sous-graphe formé de lui-même et de ceux qui le suivent.

Un graphe est cordal si et seulement si il admet un tel ordre.

C'est cette caractérisation qui rend la famille utile : elle transforme une propriété globale, difficile à vérifier, en un ordre qu'un algorithme sait produire.

Graphes parfaits

Définition

Un graphe est parfait si, pour tout sous-graphe induit G′G', on a χ(G′)=ω(G′)\chi(G') = \omega(G').

Le mot tout est essentiel. Il ne suffit pas que l'égalité vaille pour le graphe entier : elle doit valoir pour chacun de ses sous-graphes induits. C'est ce qui rend la notion stable et exploitable.

La chaîne d'implications qui débloque le problème du chapitre précédent :

graphe d’intervalles⇒cordal⇒parfait⇒χ=ω\text{graphe d'intervalles} \Rightarrow \text{cordal} \Rightarrow \text{parfait} \Rightarrow \chi = \omega
Ce qui vient d'être gagné
Le problème général de coloration est NP-complet. En reconnaissant qu'un graphe est un graphe d'intervalles, donc cordal, donc parfait, on obtient une solution exacte en temps linéaire.
On n'a pas trouvé un meilleur algorithme général : on a identifié la structure du problème particulier. C'est le mouvement le plus rentable de toute l'algorithmique, et il vaut bien au-delà des graphes.
Le théorème fort des graphes parfaits
Un graphe est parfait si et seulement s'il ne contient, ni lui ni son complémentaire, de cycle sans corde de longueur impaire au moins 5.
Conjecturé par Berge en 1961, démontré en 2002. Ce n'est pas un résultat qu'on utilise en calcul, mais il dit quelque chose de frappant : toute la difficulté de la coloration tient à ces trous impairs, et le cycle $C_5$ du chapitre précédent en est le plus petit exemple.

LexBFS, l'ordre qui garantit l'optimum

Parcours en largeur lexicographique

LexBFS est un BFS où, à chaque étape, on choisit le sommet dont l'étiquette est la plus grande dans l'ordre lexicographique. Chaque sommet retenu ajoute son numéro à l'étiquette de ses voisins non encore traités.

Sur un graphe cordal, l'ordre produit, lu à l'envers, est un ordre parfait d'élimination.

Le glouton appliqué dans cet ordre donne une coloration optimale, en temps linéaire. Le problème NP-complet du chapitre précédent est résolu exactement, pour cette famille.

main.py
Sortie
>_ Prêt à exécuter…
Graphe non orienté7 sommets, 8 arêteschemin mis en évidence
ABCDEFG

Le triangle mis en évidence est la clique de taille 3 qui prouve χ≥3\chi \geq 3 ; la coloration en trois teintes prouve χ≤3\chi \leq 3. La preuve est complète, et l'affectation aux machines se lit directement sur les couleurs.

Vérification rapidesans note, on peut se reprendre

1.Le carré C4 est-il cordal ?

2.Dans un graphe d'intervalles, la plus grande clique correspond…

3.Que garantit la chaîne « intervalles ⟹ cordal ⟹ parfait » ?

Graphes planaires

Définition

Un graphe est planaire s'il peut être dessiné dans le plan sans qu'aucune arête n'en croise une autre.

C'est une propriété du graphe, pas du dessin : un graphe planaire mal dessiné a des croisements, ce qui ne l'empêche pas d'être planaire.

Formule d'Euler

Pour un graphe planaire connexe dessiné sans croisement, avec ff faces (la face extérieure comprise) :

n−m+f=2n - m + f = 2
La conséquence utile
Un graphe planaire simple à $n \geq 3$ sommets vérifie $m \leq 3n - 6$.
C'est un test de réfutation immédiat : $K_5$ a 5 sommets et 10 arêtes, or $3 \times 5 - 6 = 9 < 10$. Donc $K_5$ n'est pas planaire, et c'est prouvé en une ligne.
Attention au sens : l'inégalité est nécessaire, pas suffisante. $K_{3,3}$ a 6 sommets et 9 arêtes, il passe le test, et il n'est pourtant pas planaire.

Le théorème de Kuratowski donne la caractérisation exacte : un graphe est planaire si et seulement s'il ne contient ni K5K_5 ni K3,3K_{3,3}, à subdivision près. Et le théorème des quatre couleurs, démontré en 1976 avec l'aide d'un ordinateur, affirme que tout graphe planaire vérifie χ≤4\chi \leq 4.

Le tableau qu'il faut avoir en tête

FamilleReconnaissanceColoration
BipartiΘ(n+m)\Theta(n + m) par BFS bicoloreχ=2\chi = 2, immédiat
Arbrem=n−1m = n - 1 et connexeχ=2\chi = 2, immédiat
IntervallesO(nlog⁡n)O(n \log n) en triant les bornesχ=ω\chi = \omega, glouton par début croissant
CordalO(n+m)O(n + m) par LexBFSχ=ω\chi = \omega, glouton dans l'ordre LexBFS
Parfaitpolynomial, mais compliquéχ=ω\chi = \omega
PlanaireO(n)O(n), algorithme sophistiquéχ≤4\chi \leq 4
QuelconqueNP-complet

Exercices type

Pourquoi la clique d'un graphe d'intervalles est-elle facile à trouver ?

Parce qu'elle correspond à un point de la droite.

Des intervalles deux à deux sécants ont nécessairement un point commun, c'est le théorème de Helly en dimension 1. Une clique de taille kk équivaut donc à un instant où kk intervalles sont simultanément ouverts.

Il suffit alors de trier les 2n2n bornes et de parcourir l'axe en incrémentant à chaque ouverture, en décrémentant à chaque fermeture : O(nlog⁡n)O(n \log n), sans jamais construire le graphe. Sur un graphe quelconque, trouver la clique maximale est NP-difficile.

Le carré $C_4$ est-il cordal ? Et parfait ?

Cordal : non. C'est un cycle de longueur 4 sans corde, ce qui est exactement la définition du contraire.

Parfait : oui. C4C_4 est biparti, donc χ=2\chi = 2, et il contient une arête donc ω=2\omega = 2. La même vérification vaut pour tous ses sous-graphes induits.

Cet exemple montre que cordal est strictement plus fort que parfait : la chaîne d'implications ne se remonte pas.

Que garantit exactement la perfection, et que ne garantit-elle pas ?

Elle garantit χ=ω\chi = \omega pour le graphe et tous ses sous-graphes induits.

Elle ne donne pas d'algorithme simple : savoir qu'un graphe est parfait ne dit pas comment le colorer. Il existe un algorithme polynomial, mais il est très sophistiqué.

C'est pourquoi on préfère travailler sur les sous-familles concrètes, intervalles ou cordaux, où un algorithme simple et linéaire existe : LexBFS suivi du glouton.

Pourquoi $K_5$ n'est-il pas planaire ?

Par la conséquence de la formule d'Euler : tout graphe planaire simple à n≥3n \geq 3 sommets vérifie m≤3n−6m \leq 3n - 6.

Pour K5K_5 : n=5n = 5 et m=5×42=10m = \frac{5 \times 4}{2} = 10, alors que 3×5−6=93 \times 5 - 6 = 9. L'inégalité est violée, donc K5K_5 n'est pas planaire.

Ce raisonnement ne fonctionne pas dans l'autre sens : K3,3K_{3,3} vérifie l'inégalité (9≤129 \leq 12) sans être planaire. Pour lui il faut une borne affinée, valable sur les graphes sans triangle : m≤2n−4m \leq 2n - 4, soit 9>89 > 8.

Un ordre parfait d'élimination : à quoi cela sert-il concrètement ?

À rendre le glouton exact.

Quand on colore un sommet simplicial, ses voisins déjà colorés forment une clique : ils portent donc des couleurs deux à deux distinctes, et leur nombre est au plus ω−1\omega - 1. La plus petite couleur libre est donc toujours inférieure à ω\omega.

En procédant dans cet ordre, le glouton n'utilise jamais plus de ω\omega couleurs, ce qui est optimal puisque χ≥ω\chi \geq \omega. LexBFS produit cet ordre en temps linéaire sur un graphe cordal.

Comment aborder un problème de coloration en pratique ?

En cherchant d'abord la famille du graphe, avant tout algorithme.

Les données viennent-elles d'intervalles de temps ? Le graphe est d'intervalles, donc parfait, et le glouton par date de début croissante est optimal.

Est-il biparti ? Alors 2 couleurs, et un BFS le montre.

Est-il planaire, parce qu'il vient d'une carte ? Alors 4 couleurs suffisent.

Ce n'est que si aucune structure ne se dégage qu'on se rabat sur le glouton avec Welsh-Powell, en acceptant l'approximation.

La méthode

  1. Cherche l'origine des données : le temps, la géométrie, une relation bipartite.
  2. Teste le bipartisme en premier : c'est un BFS, et cela règle tout.
  3. Trie les bornes si les sommets sont des intervalles : ω\omega tombe immédiatement.
  4. Applique LexBFS puis le glouton sur un graphe cordal.
  5. Vérifie l'optimalité en comparant le nombre de couleurs à ω\omega.
  6. Utilise m≤3n−6m \leq 3n - 6 pour réfuter la planarité, jamais pour la prouver.
  7. Ne conclus « NP-complet, donc perdu » qu'après avoir cherché la structure.

En résumé

  • Un graphe biparti se colore avec 2 couleurs, et se reconnaît par un BFS.
  • Dans un graphe d'intervalles, ω\omega est le recouvrement maximal, calculable en triant.
  • Un graphe est cordal si tout cycle de longueur ≥4\geq 4 a une corde.
  • Cordal équivaut à l'existence d'un ordre parfait d'élimination.
  • Un graphe est parfait si χ=ω\chi = \omega pour tous ses sous-graphes induits.
  • intervalles ⇒\Rightarrow cordal ⇒\Rightarrow parfait ⇒χ=ω\Rightarrow \chi = \omega.
  • LexBFS produit l'ordre qui rend le glouton exact, en temps linéaire.
  • Un graphe planaire vérifie m≤3n−6m \leq 3n - 6 et se colore avec 4 couleurs.
  • Reconnaître la structure vaut mieux que chercher un meilleur algorithme général.

Et ensuite ? Il reste une grande famille de problèmes que les graphes résolvent et que ce module n'a pas encore abordée : faire circuler quelque chose, et apparier deux ensembles. C'est le dernier chapitre.