Familles remarquables

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 plusieurs de ces familles, les problèmes difficiles redeviennent faciles, et exactement. Le chapitre se termine sur deux familles d'une autre nature, celles des tournées : passer une fois par chaque rue, ou une fois par chaque client, deux questions presque identiques que tout sépare.

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 s'il n'a aucun cycle de longueur impaire.

C'est la famille la plus simple, et déjà tout devient facile : $\chi = 2$ dès qu'il y a une arête, le test se fait par un BFS bicolore en $\Theta(n + m)$ , et les problèmes de couplage s'y ramènent à un flot, comme le montrera le dernier chapitre.

Le graphe ci-dessous relie trois machines aux pièces qu'elles savent usiner. Une arête va toujours d'une machine à une pièce, jamais d'une machine à une autre ni d'une pièce à une autre : les deux groupes sont là, et le graphe est biparti par construction.

Graphe non orienté6 sommets, 6 arêtes

Une arête quand la machine sait usiner la pièce. Chaque arête va d'une couleur à l'autre : le graphe est biparti. Dessiné ainsi, c'est un cycle de longueur 6, pair comme l'exige le critère.

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, cartographie de fragments d'ADN, 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.

Pourquoi trier par date de début suffit. Traiter les tâches dans l'ordre de leur début. Quand vient le tour d'une tâche $T$ , ses voisins déjà colorés ont tous commencé avant elle, ou en même temps, et ne sont pas encore finis quand elle commence : ils couvrent tous l'instant où $T$ démarre.
Ils forment donc, avec $T$ , une clique, et sont au plus $\omega - 1$ . La plus petite couleur libre est inférieure à $\omega$  : le glouton n'emploie jamais plus de $\omega$ machines, ce qui est optimal.
C'est ce qu'a constaté le chapitre précédent sur les sept tâches, et c'est désormais démontré, pour toutes les tâches possibles.

Vérification rapideon peut se reprendre

Dans un graphe d'intervalles, la taille de la plus grande clique vaut…

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

Le carré A, B, C, D : un cycle de longueur 4, et aucune arête ne relie A à C ni B à D.

Ajouter 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

La corde A-C, en évidence, coupe le carré en deux triangles, A, B, C et A, C, D.

Vérification rapideon peut se reprendre

Le carré C4 est-il cordal ?

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 s'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'$ , on a $\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 :

\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 aucun cycle induit de longueur impaire au moins 5, ni le complémentaire d'un tel cycle (le complémentaire relie deux sommets exactement quand ils ne sont pas voisins).
Conjecturé par Berge en 1961, démontré en 2002 par Chudnovsky, Robertson, Seymour et Thomas. Ce n'est pas un résultat qu'on utilise en calcul, mais il dit quelque chose de frappant : ce qui empêche l'égalité $\chi = \omega$ tient à ces seuls 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, celui du dictionnaire. L'étiquette d'un sommet est une liste de numéros, vide au départ.

Les sommets reçoivent leur numéro dans l'ordre où ils sont retenus, en décroissant : $n$ pour le premier, $n - 1$ pour le deuxième, et ainsi de suite. Chaque sommet retenu ajoute son numéro à la fin de l'étiquette de ses voisins non encore traités. Un voisin du premier sommet porte donc une étiquette qui commence par $n$ , et passe avant tout sommet qui n'en est pas voisin : c'est bien un parcours en largeur, avec une règle de plus pour départager.

Sur un graphe cordal, l'ordre produit, lu à l'envers, est un ordre parfait d'élimination. Autrement dit, dans l'ordre même du parcours, chaque sommet ne voit parmi ses voisins déjà visités qu'une clique.

C'est donc dans l'ordre du parcours LexBFS, et non dans l'ordre d'élimination lu de gauche à droite, que le glouton 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.

Voici le parcours déroulé à la main sur les sept tâches, avec la même règle que le programme ci-dessous : à étiquettes égales, le nom le plus grand passe en premier.

Tour	Étiquettes des sommets restants	Retenu	Numéro
1	toutes vides	G	7
2	F (7), les autres vides	F	6
3	D (6), E (6), les autres vides	E	5
4	D (6, 5), les autres vides	D	4
5	C (4), A et B vides	C	3
6	A (3), B (3)	B	2
7	A (3, 2)	A	1

Au tour 4, D passe avant C, A et B parce que son étiquette commence par 6 ; au tour 6, A et B sont à égalité, et le nom départage. L'ordre obtenu est G, F, E, D, C, B, A. Le glouton qui le suit donne G 0, F 1, E 0, D 2, C 0, B 1, A 2 : trois machines, autant que la clique A, B, C.

Le sens de lecture compte

L'ordre A, B, C, E, G, F, D est lui aussi un ordre parfait d'élimination du graphe des tâches : les voisins qui suivent A sont B et C, reliés ; ceux qui suivent E sont F et D, reliés ; chacun des autres n'a qu'un voisin après lui, ou aucun.
Suivi de gauche à droite, le glouton donne A 0, B 1, C 2, E 0, G 0, F 1, puis D, qui voit C, E et F, ouvre une quatrième machine. Lu à l'envers, D, F, G, E, C, B, A, il n'en faut que trois.
Suivre l'ordre d'élimination tel quel ne garantit donc rien. C'est son envers qui rend le glouton exact, et c'est précisément l'ordre que LexBFS produit.

Vérification rapideon peut se reprendre

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

main.py

Sortie

>_ Prêt à exécuter…

Coloration gloutonne7 tâches, 8 chevauchements

Ordre :

7 / 7

A : chevauche C (0), B (1) ; interdites : {0, 1} → machine 2

Planning par machine

L'ordre « LexBFS » : 3 machines, et c'est le minimum.

Il en faut bien 3 : A, B et C se chevauchent deux à deux, et tournent toutes à l'instant 2. Cette clique de taille ω = 3, reliée par les arêtes épaissies, exige 3 machines à elle seule.

Ce graphe est cordal : dans l'ordre de LexBFS, qui est l'ordre d'élimination lu à l'envers, le glouton atteint toujours ω.

Les sept tâches, colorées par le glouton dans l'ordre choisi par les boutons d'ordre. Le triangle A, B, C, épaissi, est une clique de taille 3 : il minore. Les trois machines majorent.

Le triangle épaissi est la clique de taille 3 qui prouve $\chi \geq 3$  ; la coloration en trois machines prouve $\chi \leq 3$ . La preuve est complète, et l'affectation se lit sur le planning, sous le graphe : A et D sur une machine, B et F sur une autre, C, E et G sur la troisième.

À manipuler

Choisir l'ordre « élimination », A, B, C, E, G, F, D, et le dérouler : D arrive en dernier, chevauche C, E et F, déjà placées sur trois machines différentes, et en ouvre une quatrième. C'est l'erreur de l'encadré « Le sens de lecture compte », rejouée.
Passer à « élimination à l'envers » : trois machines, comme LexBFS et comme le début croissant. Ces trois ordres sont ceux qui garantissent l'optimum, et la figure rappelle pourquoi à la fin de LexBFS et du début croissant.

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 $f$ faces (la face extérieure comprise) :

n - m + f = 2

Cette formule d'Euler, sur les faces d'un dessin, n'a rien à voir avec le théorème d'Euler sur les tournées qui empruntent chaque arête une fois, qui vient plus bas : le même mathématicien a laissé son nom aux deux.

La conséquence utile. Un graphe planaire simple à $n \geq 3$ sommets vérifie $m \leq 3n - 6$ .
Elle se tire de la formule d'Euler : chaque face est bordée par au moins trois arêtes, et chaque arête borde au plus deux faces, donc $3f \leq 2m$  ; en reportant $f = 2 - n + m$ , il vient $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 $K_5$ ni $K_{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 $\chi \leq 4$ .

Une borne, pas une réponse

Les planaires ne rejoignent pas pour autant les familles faciles. Le théorème des quatre couleurs majore, et une coloration à 4 couleurs se calcule en temps polynomial ; mais décider si 3 couleurs suffisent à un graphe planaire reste NP-complet, aussi difficile qu'en général.
La roue à cinq rayons du chapitre précédent le montre à petite échelle : elle est planaire, sa plus grande clique est un triangle, et elle exige pourtant 4 couleurs. Sur un planaire, ni la clique ni la borne ne donnent

\chi

Graphes eulériens et hamiltoniens

Les familles précédentes rendaient la coloration facile. Les deux dernières répondent à une autre question, celle des tournées : passer partout une fois, sans repasser. Elles donnent la leçon de complexité la plus nette du parcours, parce que deux questions presque identiques y tombent de part et d'autre de la frontière entre facile et difficile.

Définitions

Un cycle eulérien emprunte chaque arête exactement une fois et revient à son point de départ ; un chemin eulérien fait de même sans revenir au départ. Un sommet peut y être traversé plusieurs fois : c'est l'arête qu'on ne reprend jamais. Le chapitre de mathématiques parle de circuit et de parcours eulériens, ce sont les mêmes objets.

Un cycle hamiltonien passe exactement une fois par chaque sommet avant de revenir au départ.

La question eulérienne est née à Königsberg, en 1735 : peut-on traverser les sept ponts de la ville une fois chacun ? Chaque quartier devient un sommet, chaque pont une arête, et deux quartiers reliés par deux ponts le sont par deux arêtes. Le chapitre de mathématiques sur les graphes dessine la ville et déroule le raisonnement d'Euler ; on n'en retient ici que la conclusion. Les degrés valent 5 pour l'île et 3 pour chacun des trois autres quartiers : quatre sommets de degré impair, et la promenade est impossible, sans qu'on ait essayé le moindre itinéraire.

Théorème d'Euler

Soit un graphe dont toutes les arêtes appartiennent à une même composante connexe ; les sommets isolés, que la tournée n'a pas à visiter, n'y changent rien, et deux sommets peuvent être reliés par plusieurs arêtes. Ce graphe admet :

un cycle eulérien si et seulement si tous ses sommets sont de degré pair ;
un chemin eulérien qui ne se referme pas si et seulement s'il a exactement deux sommets de degré impair, et ce chemin part alors de l'un pour finir sur l'autre.

Dans tous les autres cas, il n'y a ni l'un ni l'autre. Un seul sommet impair est d'ailleurs impossible : la somme des degrés vaut deux fois le nombre d'arêtes, elle est paire.

L'idée tient en une phrase : chaque passage par un sommet consomme deux arêtes, une pour entrer et une pour sortir, si bien que seuls le départ et l'arrivée d'un chemin qui ne se referme pas gardent une arête célibataire. Que la parité suffise est moins évident ; c'est l'algorithme qui le montre en construisant la tournée.

Pour un ingénieur, le théorème a deux mérites. La vérification coûte $O(n + m)$  : compter les degrés, puis un parcours du chapitre 3 pour s'assurer que les arêtes forment un seul morceau. Et la construction est aussi rapide : l'algorithme de Hierholzer part d'un sommet, avance en effaçant chaque arête empruntée jusqu'à revenir au départ, puis greffe sur ce premier cycle des détours partis de sommets qui ont encore des arêtes libres, en $O(m)$ au total.

main.py

Sortie

>_ Prêt à exécuter…

La tournée de collecte

Un camion de collecte doit passer dans chaque rue du quartier ci-dessous et revenir au dépôt. Il lui faut donc un cycle eulérien. Mairie et Marché ont trois rues chacun, tous les autres carrefours deux : deux sommets impairs, un chemin eulérien existe, de Mairie à Marché, mais pas de cycle.
Le camion devra donc repasser par certaines rues, et la question devient : lesquelles, pour perdre le moins de chemin ? Repasser par une rue revient à la doubler, ce qui change la parité de ses deux extrémités. Pour rendre pairs Mairie et Marché sans toucher aux autres, il faut doubler un chemin de l'un à l'autre, et le meilleur choix est le plus court chemin du chapitre 5 : Mairie, École, Stade, Marché, 500 m, et non la rue directe de 600 m.
Les rues mesurent 1 900 m en tout ; la tournée la plus courte en fait 2 400. Avec plus de deux carrefours impairs, il faut les apparier au moindre coût, ce qui reste un calcul polynomial : c'est le problème dit du postier chinois, posé au début des années 1960 par le mathématicien Guan Meigu.

Graphe non orienté et pondéré6 sommets, 7 arêteschemin mis en évidence

Le quartier à collecter, longueurs en mètres. Mairie et Marché sont les deux carrefours de degré impair ; les trois rues en évidence, le plus court chemin de l'un à l'autre, sont celles que le camion parcourt deux fois.

Changer « arête » en « sommet » change tout. Pour les cycles hamiltoniens, aucun critère de ce genre n'existe, et décider s'il en existe un est NP-complet, comme la 3-coloration du chapitre précédent. On connaît seulement des conditions suffisantes, comme celle de Dirac : un graphe d'au moins 3 sommets où chacun a au moins $n/2$ voisins possède un cycle hamiltonien. Elle ne dit rien dans l'autre sens : un simple cycle de 10 sommets est hamiltonien, alors que chaque sommet n'y a que 2 voisins.

La version pondérée est le problème du voyageur de commerce : visiter chaque client une fois, revenir au dépôt, au moindre coût total. C'est la tournée d'un livreur, d'un technicien de maintenance, ou d'une perceuse qui doit percer tous les trous d'une carte électronique. On le traite comme la coloration : un glouton (aller toujours au client le plus proche parmi ceux qui restent) donne vite une tournée valide, sans garantie, et une recherche exhaustive intelligente règle les petites instances.

Question	Ce que la tournée couvre	Critère	Coût de la décision
Eulérienne	chaque arête une fois	arêtes d'un seul tenant, et 0 ou 2 sommets de degré impair	$O(n + m)$
Hamiltonienne	chaque sommet une fois	aucun critère simple connu	NP-complet

Deux tournées, deux mondes. Inspecter toutes les canalisations d'un réseau, balayer toutes les rues, relever des compteurs posés le long des rues : une question d'arêtes, eulérienne, facile.
Livrer chaque client, visiter chaque site une fois : une question de sommets, hamiltonienne, difficile.
Avant de se lancer dans le calcul d'une tournée, se demander ce qu'elle doit couvrir : les liens, ou les lieux.

Vérification rapideon peut se reprendre

Un camion doit parcourir chaque rue d'un quartier et revenir au dépôt. Quatre carrefours sont de degré impair. Que conclure ?

Le tableau qu'il faut avoir en tête

Pour la coloration, voici ce que chaque famille apporte :

Famille	Reconnaissance	Coloration
Biparti	$\Theta(n + m)$ par BFS bicolore	$\chi = 2$ , immédiat
Arbre	$O(n + m)$  : connexe et $m = n - 1$	$\chi = 2$ , immédiat
Intervalles	intervalles connus : $\omega$ en $O(n \log n)$ en triant les bornes	$\chi = \omega$ , glouton par début croissant
Cordal	$O(n + m)$ par LexBFS	$\chi = \omega$ , glouton dans l'ordre LexBFS
Parfait	polynomial, mais compliqué	$\chi = \omega$
Planaire	$O(n)$ , algorithme sophistiqué	$\chi \leq 4$ garanti ; savoir si 3 suffisent reste NP-complet
Quelconque		NP-complet

Mettre en pratique

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 $k$ équivaut donc à un instant où $k$ intervalles sont simultanément ouverts.

Il suffit alors de trier les $2n$ bornes et de parcourir l'axe en incrémentant à chaque ouverture, en décrémentant à chaque fermeture, et en traitant les fermetures d'abord quand deux bornes tombent au même instant : $O(n \log n)$ , sans jamais construire le graphe. Sans cette précaution, $[9, 10)$ et $[10, 11)$ , qui ne se chevauchent pas, compteraient pour deux. 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. $C_4$ est biparti, donc $\chi = 2$ , et il contient une arête donc $\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 \geq 3$ sommets vérifie $m \leq 3n - 6$ .

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

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

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

À rendre le glouton exact, à condition de le lire dans le bon sens.

Il faut colorer les sommets dans l'ordre parfait d'élimination lu à l'envers. Au moment où un sommet est coloré, les sommets déjà colorés sont exactement ceux qui le suivent dans l'ordre d'élimination, et il est simplicial parmi eux : ses voisins déjà colorés forment une clique, portent des couleurs deux à deux distinctes, et sont au plus $\omega - 1$ . La plus petite couleur libre est donc toujours inférieure à $\omega$ , et le glouton n'utilise jamais plus de $\omega$ couleurs, ce qui est optimal puisque $\chi \geq \omega$ .

Le sens compte : sur le chemin a-b-c-d, l'ordre a, d, b, c est un ordre parfait d'élimination, et le glouton qui le suit de gauche à droite met trois couleurs là où deux suffisent. LexBFS produit directement le bon sens, en temps linéaire : son ordre de visite est l'ordre d'élimination lu à l'envers.

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 toujours, et une coloration à 4 couleurs se calcule en temps polynomial ; mais décider si 3 suffiraient reste aussi difficile qu'en général.

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

Inspecter chaque tronçon d'un réseau de canalisations, ou visiter chaque station de pompage : pourquoi l'une est-elle facile et l'autre non ?

La première tournée doit couvrir chaque arête une fois : c'est une question eulérienne. Le théorème d'Euler la tranche en comptant les degrés : si les tronçons forment un seul morceau et que tous les nœuds sont de degré pair, une tournée sans repasser existe, et l'algorithme de Hierholzer la construit en $O(m)$ . S'il y a exactement deux nœuds impairs, une inspection sans repasser existe encore, de l'un à l'autre ; au-delà, ou pour revenir au point de départ, on double au plus juste des plus courts chemins entre les nœuds impairs.

La seconde doit passer par chaque sommet une fois : c'est une question hamiltonienne, NP-complète. Aucun comptage ne la tranche ; il faut une heuristique, ou une recherche exhaustive sur un petit réseau.

Les deux énoncés ne diffèrent que d'un mot, arête ou sommet, et c'est ce mot qui fait passer du facile au difficile.

Bipartis

Graphes d'intervalles

Graphes cordaux

Graphes parfaits

LexBFS, l'ordre qui garantit l'optimum

Graphes planaires

Graphes eulériens et hamiltoniens

Le tableau qu'il faut avoir en tête

Mettre en pratique

Dans la bibliothèque d'exercices