TD2 — Graphes : corrections TD1 (ex. 11–14), bipartition (ex. 15–17), chapitres 2–3

🔊 Écouter la source audio

Couverture : de 00:01:42 (le début, 00:00:00–00:01:42 est du silence/acceuil) à 02:01:33 sur un audio de 02:01:33 (2 h 02). La séance commence par la fin de la correction du TD1 (exercices 11 à 14 : eulérien/hamiltonien), poursuit avec les exercices 15 à 17 qui mobilisent la bipartition (cavalier, souris et fromage, espions), puis aborde le chapitre 2 (démonstration « graphe biparti à partitions inégales ⇒ non hamiltonien ») et le chapitre 3 (graphes planaires, théorèmes d’Euler, Fáry, Kuratowski). L’exercice 2 du chapitre 2 est reporté à la séance suivante.

ASR : ⚠️ les transcriptions ASR des termes du cours sont très approximatives : « périmé / l’airien / européen » → eulérien ; « améthonien / mythonien / à mi-tonnière / anétonien » → hamiltonien ; « 4,3,3 » → K_{3,3} ; « mètre du poignet » → lemme de la poignée de main (handshake lemma) ; « théorème d’or » → théorème d’Ore ; « TIX » → TikZ (outil LaTeX utilisé pour replotier les graphes). Les cycles/chemins explicites et les listes d’adjacence cités au tableau doivent être vérifiés sur la figure de l’énoncé (graphes_syllabus_exercices.pdf).

PARTIE 1 — Fin de correction du TD1 : exercices 11–14 — [00:01:42]

1. Exercice 11 — Rendre un graphe eulérien en ajoutant un sommet — [00:01:42]–[00:22:07]

Énoncé : est-il toujours possible de rendre un graphe $G$ eulérien en lui ajoutant un sommet et quelques arêtes ? (arêtes multiples autorisées, le graphe n’est pas supposé simple).

Réponse : oui, avec deux cas selon la connexité.

Rappel : un graphe est eulérien s’il possède un cycle eulérien (une arête → deux sommets de degré impair ⇒ chemin eulérien mais pas de cycle). « Graphe eulérien = cycle eulérien, pas seulement chemin eulérien » → il faut tous les sommets de degré pair.

Cas 1 — $G$ connexe : le lemme de la poignée de main assure que le nombre de sommets de degré impair est pair. On relie le nouveau sommet à tous les sommets de degré impair : chacun passe à un degré pair, et le nouveau sommet reçoit autant d’arêtes que de sommets impairs, donc un degré pair. Tous les sommets sont de degré pair → le nouveau graphe est eulérien.
Cas 2 — $G$ non connexe (plusieurs composantes) :
- pour chaque composante possédant des sommets de degré impair : on relie ses sommets de degré impair au nouveau sommet (même principe que le cas 1) ;
- pour chaque composante dont tous les sommets sont déjà de degré pair : on relie un sommet de la composante au nouveau sommet par une arête double (deux arêtes parallèles → le sommet passe à degré pair $+ 2$ , le nouveau sommet gagne $2$ ) — autorisé car les arêtes multiples ne sont pas interdites.
- Sinon (sans arête double) il resterait des sommets de degré impair.
Si $G$ devait être simple (interdiction des arêtes multiples) → le cas 2 devient impossible (pour les composantes à degrés tous pairs, il n’y a pas de solution).
La consigne ne précise pas « simple » → on peut utiliser des arêtes multiples.

Objection discutée (reliure des mini-graphes deux à deux puis sommet central relié aux arêtes vertes) : cela dépend des exemples et ne fonctionne pas toujours ; un contre-exemple sera montré la fois suivante. La méthode « relier les degrés impairs au nouveau sommet » est la seule réponse générale.

Ajout de 2 sommets : on réapplique le même principe (un sommet puis l’autre).

2. Exercice 12 — Deux personnes ayant le même nombre d’amis — [00:22:12]–[00:30:36]

Énoncé : montrer que dans un groupe de $n$ personnes, il y a toujours deux personnes ayant le même nombre d’amis (dans un graphe d’amitié).

Généralisation de l’exercice « Monsieur et Madame Dupont » (où M. et Mme avaient chacun serré la main du même nombre de personnes, égal à 3).
Preuve (par l’absurde / énumération des degrés) :
1. Supposons que tous les degrés sont distincts. Avec $n$ personnes, les degrés possibles sont $n$ valeurs distinctes : $0, 1, \dots, n - 1$ (le maximum est $n - 1$ car on s’exclut soi-même).
2. La liste complète serait ${0, 1, \dots, n - 1}$ : il y aurait quelqu’un avec $0$ ami et quelqu’un avec $n - 1$ amis.
3. Or celui qui a $n - 1$ amis est ami avec tout le monde → la personne à $0$ ami ne peut pas exister. Contradiction.
4. Conclusion : deux personnes ont le même nombre d’amis.

3. Exercice 13 — Plan de table à table ronde — [00:30:36]–[00:43:33]

Énoncé : un groupe de 8 personnes (sommets $1, \dots, 8$ ) se retrouve pour dîner ; le graphe des incompatibilités est donné (une arête = deux personnes qui s’entendent très modérément). Proposer un plan de table à table ronde en évitant de placer côte à côte deux personnes incompatibles.

Méthode : plutôt que le graphe d’incompatibilité, considérer le graphe de compatibilité = complémentaire du graphe d’incompatibilité (on relie les sommets non reliés auparavant : ex. 1–3).
Un cycle hamiltonien du graphe de compatibilité est une disposition valide autour de la table ronde (à table ronde, un chemin ne suffit pas : il faut refermer le cycle).
Théorèmes du cours (Dirac, Ore) : non applicables ici. La condition (somme des degrés de toute paire de sommets non adjacents $\geq n$ , ou degré $\geq n /2$ ) n’est pas vérifiée pour certaines paires (ex. la paire non adjacente ${2, 5}$ ). Ces théorèmes donnent une condition suffisante mais pas nécessaire : ils ne détectent pas tous les graphes hamiltoniens (même remarque que pour le théorème de Dirac, qui échoue ici).
Solution : donner explicitement un cycle hamiltonien, p.ex.

1 \to 3 \to 2 \to 4 \to 6 \to 7 \to 5 \to 8 \to 1. (⚠️ \overset{a}{ˋ} v \overset{e}{ˊ} rifier sur la figure)

Remarque sur la justification : « trouver un cycle hamiltonien » ≠ « prouver qu’il en existe un ». Si l’on demande une preuve, on utilise les théorèmes du cours (quand ils s’appliquent) ; sinon on expose le cycle.

4. Exercice 14 — Parmi les graphes suivants : eulériens ? hamiltoniens ? — [00:43:57]–[00:57:38]

Énoncé : parmi les graphes A, B, C, D, déterminer lesquels sont eulériens et lesquels sont hamiltoniens.

Eulérien : examiner les degrés — tous pairs ⇒ cycle eulérien.
Hamiltonien : pour A, B, C, le contour du graphe donne un cycle hamiltonien (on en voit un immédiatement) ; D n’admettra jamais de cycle hamiltonien.
Piège sur A : un sommet de degré $2$ alors que $n = 5$ → les conditions de Dirac ( $n /2 = 2, 5$ ) et d’Ore ne s’appliquent pas ; pourtant le graphe est hamiltonien (le contour) → illustration de la suffisance non nécessaire des théorèmes.

Consigne du TD2 : correctifs (TD1 et exercice 3 du TD2, qui demandent des illustrations) publiés en ligne après la séance.

PARTIE 2 — Exercices 15–17 : bipartition et hamiltonicité — [00:57:39]

Les exercices 15 et 16 requièrent des notions du chapitre 2 (bipartition) ; le prof n’est pas exhaustif sur la démo ici, les preuves étant faites au chapitre 2.

5. Exercice 15 — Le cavalier sur un échiquier 3×4 — [01:00:35]–[01:15:51]

Énoncé : le cavalier d’échecs placé sur une case quelconque d’un échiquier 3×4 (12 cases) peut-il visiter toutes les cases sans passer deux fois sur la même ?

Modélisation — graphe de déplacement du cavalier : 12 sommets (les cases), une arête entre deux cases reliées par un déplacement de cavalier (2 + 1 en L). Liste des adjacences partielle (au tableau) : ${1 : 7, 10}$ , ${7 : 1, 9, 2}$ , ${9 : 7, 2}$ , ${2 : 9, 1, 8}$ , ${8 : 2, 10}$ , ${10 : 8, 1, 3, 5, 12}$ , ${3 : 10, 5, 12}$ , ${5 : 3, 11}$ , ${11 : 2, 5, 4}$ , ${4 : 11, 12}$ , etc. ⚠️ transcription brouillée → vérifier sur la figure.
On cherche un chemin hamiltonien (passer partout sans repasser), pas un cycle : l’énoncé ne demande pas de revenir au point de départ.
Ni Dirac ni Ore ne s’appliquent ici.
Réponse (a) : oui, un chemin hamiltonien existe (le prof en trace un depuis la case 1), p.ex. 1 → 7 → 9 → 2 → 8 → 3 → 5 → 11 → 4 → 12 → 10 → 6 (⚠️ séquence à confirmer sur le graphe, ASR partielle).
Distinction clé : avec « une case quelconque », il faudrait pouvoir partir de n’importe où ⇒ il faudrait un cycle hamiltonien ; or aucun cycle hamiltonien n’existe (on ne peut pas refermer la boucle).

5 bis. Sous-question : échiquier 8×8 privé de deux coins opposés — [01:10]–[01:15:51]

Le graphe de déplacement du cavalier est biparti : d’une case noire on saute sur une case blanche (et réciproquement) — c’est exactement la définition d’un graphe biparti.
Enlever deux coins opposés = enlever deux cases de la même couleur (la diagonale garde la couleur) → les deux sont noires.
Résultat : au chapitre 2 on montrera que si le graphe biparti (partition $X$ , $Y$ ) vérifie $∣ Y ∣ - ∣ X ∣ \geq 2$ , il n’admet pas même de chaîne hamiltonienne (donc pas de cycle). Ici $∣ Y ∣ - ∣ X ∣ = 2$ → impossible.

6. Exercice 16 — La souris et le fromage en cubes 3×3×3 — [01:17:30]–[01:24:58]

Énoncé : une souris face à un morceau de fromage découpé en 27 petits cubes (3 étages de 9). Elle peut creuser en partant de n’importe quel cube sauf le cube central, et se déplacer vers tout cube voisin (adjacence). (a) Peut-elle creuser un tunnel qui commence et se termine au même cube en passant par tous les cubes ? (b) Peut-elle creuser un tunnel commençant en un coin, passant par tous les cubes extérieurs, et se terminant au centre ?

(a) = cycle hamiltonien. Le graphe des cubes est biparti (coloration en « damier » 3D) : 14 sommets dans une classe, 13 dans l’autre → partitions inégalés → pas de cycle hamiltonien (théorème du chapitre 2). Réponse : non.
(b) = chemin hamiltonien d’un coin vers le centre. Les coins sont tous dans la classe noire, le cube central dans la classe blanche. Un chemin hamiltonien alterne les classes sommets par sommets : s’il part de la classe noire (coin) et finit dans la classe blanche (centre), il contient autant de sommets de chaque classe ; or les classes ont 14 et 13 sommets → impossible. Réponse : non.

7. Exercice 17 — Les espions — [01:24:58]–[01:33:45]

Énoncé : trois pays envoient chacun deux espions à une conférence (6 espions). Chaque espion doit espionner tous les espions des autres pays. Modéliser par un graphe, puis : un espion confie un message à un espion qu’il espionne ; l’information peut-elle revenir à ses oreilles après avoir été entendue une et une seule fois par chacun des autres espions ? Donner les propriétés du graphe.

Modélisation : 6 sommets regroupés en trois parties $A, B, C$ (deux sommets par pays) ; une arête entre chaque paire de sommets de pays différents (espionnage mutuel), aucune arête au sein d’un même pays.
Un espion (ex. premier sommet de $A$ ) espionne tous les espions de $B$ et tous ceux de $C$ .
(b) = cycle hamiltonien (message audible une et une seule fois par chacun et retour à l’émetteur). Ici on peut utiliser les théorèmes : Dirac est le plus évident — $n = 6$ , $n /2 = 3$ , tous les sommets sont de degré $4 \geq 3$ ⇒ cycle hamiltonien ⇒ oui, c’est possible. (Ore marche aussi.)
Propriétés du graphe : simple (pas d’arêtes multiples, pas de boucles), connexe (une seule composante), régulier de degré 4 (tous les sommets de degré 4).

PARTIE 3 — Chapitres 2 et 3 : rappels et exercices — [01:33:45]

8. Rappels du chapitre 2 (vocabulaire) — [01:33:45]–[01:37:13]

Complément d’un graphe : même ensemble de sommets, toutes les arêtes absentes de $G$ .
Graphe régulier : tous les sommets ont exactement le même degré → le graphe complet est un cas particulier des graphes réguliers.
Graphe biparti : il existe une partition des sommets en deux ensembles $X$ et $Y$ telle que chaque arête relie un sommet de $X$ à un sommet de $Y$ (les sommets de $X$ ne sont adjacents qu’aux sommets de $Y$ , et réciproquement). Exemples : hypercube (cube), graphe de l’échiquier.
Graphe planaire : représentable dans le plan avec des arêtes qui ne se croisent pas (sauf aux sommets).
Graphe biparti complet $K_{m, n}$ : graphe biparti où chaque sommet de $X$ est relié à chaque sommet de $Y$ ( $∣ X ∣ = m$ , $∣ Y ∣ = n$ ).
Graphe biregulier : tous les sommets de $X$ ont le même degré et tous les sommets de $Y$ ont le même degré.
Théorème : un graphe est biparti ssi il ne contient aucun cycle de longueur impaire.
Théorèmes utilisés (hamiltonicité) : Dirac et Ore (ex. exercice 3).

9. Exercice 1 du chapitre 2 — Biparti à partitions inégales ⇒ non hamiltonien — [01:37:13]–[01:48:27]

Énoncé : montrer que si $G$ est biparti (partition $X$ , $Y$ ) et | $X ∣ \neq = ∣ Y ∣$ , alors $G$ n’est pas hamiltonien.

Preuve (par l’absurde) :

Supposons que $G$ possède un cycle hamiltonien.
Comme $G$ est biparti, chaque arête du cycle relie un sommet de $X$ à un sommet de $Y$ → le cycle alterne $X, Y, X, Y, \dots$ → il contient autant de sommets de $X$ que de $Y$ .
Or un cycle hamiltonien passe par tous les sommets ( $∣ X ∣ + ∣ Y ∣$ sommets) → cela impose $∣ X ∣ = ∣ Y ∣$ , ce qui contredit l’hypothèse $∣ X ∣ \neq = ∣ Y ∣$ .
Conclusion : $G$ n’admet pas de cycle hamiltonien. ∎

Variante utilisée dans l’exercice 15 (échiquier) : si $∣ Y ∣ - ∣ X ∣ \geq 2$ , il n’y a même pas de chaîne hamiltonienne (la chaîne alterne aussi les classes, donc à une case près les deux classes doivent avoir le même nombre).

10. Exercice 2 du chapitre 2 — reporté — [01:48:27]–[01:50:08]

Reporté à la séance suivante (exercice potentiellement long, « ça peut devenir très long en termes d’exploitation »). On en fait l’exercice 3 d’abord.

11. Exercice 3 — Chapitre 3 : graphes planaires — [01:50:08]–[02:01:33]

Énoncé : parmi les graphes suivants (A, B, C, D), déterminer lesquels sont planaires.

Outils du chapitre 3 :

Théorème de Fáry : tout graphe planaire peut être représenté en n’utilisant que des arêtes droites (segments) sans croisement.
Formule d’Euler : pour tout graphe planaire, $V - A + F = 2$ ( $V$ sommets, $A$ arêtes, $F$ faces).
Théorème de Kuratowski : un graphe est planaire ssi il ne contient aucun sous-graphe qui est une subdivision de $K_{5}$ ou de $K_{3, 3}$ (seul théorème avec condition nécessaire et suffisante ⇒ on l’utilisera beaucoup).
Stratégie : pour montrer planaire → le dessiner (ou le redessiner) dans le plan ; pour montrer non planaire → montrer un sous-graphe égal à une subdivision de $K_{5}$ ou $K_{3, 3}$ .

Résultats :

A : planaire (on le redessine sans croisement).
B : planaire — représenté comme un cube ; en dessinant les arêtes en courbes/droites non croisées (le dessin initial avait des arêtes « croittes » apparentes), c’est planaire.
C : non planaire (contient une subdivision de $K_{3, 3}$ ) — difficile à montrer au tableau (graphe flou, reproduit en TikZ) : il n’y a pas une seule subdivision mais plusieurs ; correctif mis en ligne.
D : non planaire — en retirant deux sommets (ex. deux sommets $v, w$ ) et leurs arêtes, on obtient $K_{3, 3}$ → non planaire par Kuratowski (évident).

Définition — subdivision : insérer un nouveau sommet au milieu d’une arête existante (une arête devient deux : le sommet est « placé sur l’arête »). Une subdivision de $K_{3, 3}$ est $K_{3, 3}$ ou l’un de ses graphes obtenus en subdivisant des arêtes.

12. Conclusion et annonces — [02:01:27]

La fois prochaine : retour sur l’exercice 2 du chapitre 2 (démonstration) et sur l’exercice 11 de façon plus explicite.
Correctifs en ligne : TD1 (chapitre 1) et TD2 exercice 3 (pour les illustrations / subdivisions).

Points clés

Eulérien = cycle eulérien : tous les sommets de degré pair ; deux degrés impairs → seulement un chemin eulérien.
Rendre un graphe eulérien (cas connexe) : relier un nouveau sommet aux sommets de degré impair (pair en nombre par le lemme de la poignée de main) ; (cas non connexe) relier de même chaque composante, et par une arête double les composantes déjà à degrés pairs. Simple → impossible dans le cas 2.
Dirac : $n \geq 3$ et tous degrés $\geq n /2$ ⇒ hamiltonien. Ore : $d (u) + d (v) \geq n$ pour toute paire non adjacente ⇒ hamiltonien. Ce sont des conditions suffisantes, non nécessaires.
Graphe biparti : partition $X, Y$ ; chaque arête relie $X$ à $Y$ ; ssi pas de cycle impair ; ex. cavalier, cube 3D.
Graphe biparti $∣ X ∣ \neq = ∣ Y ∣$ ⇒ pas de cycle hamiltonien (un cycle hamiltonien alterne les classes et passe par tout ⇒ $∣ X ∣ = ∣ Y ∣$ ). Si $∣ Y ∣ - ∣ X ∣ \geq 2$ ⇒ pas même de chaîne hamiltonienne.
Planaire : dessin sans croisement (Fáry : arêtes droites suffisent), $V - A + F = 2$ , Kuratowski : planaire ssi pas de subdivision de $K_{5}$ ni $K_{3, 3}$ .

Doutes / à vérifier

⚠️ Cycles/chemins hamiltoniens explicites (ex. 13 : $1 \to 3 \to 2 \to 4 \to 6 \to 7 \to 5 \to 8 \to 1$ ; ex. 15 : chemin du cavalier ; adjacences du graphe de déplacement 3×4) — transcription ASR partielle ; vérifier sur graphes_syllabus_exercices.pdf.
Date de la séance non déterminée depuis l’audio (field date à confirmer).
Nom du chargé de TD non entendu.
Ex. 14 : détails des degrés/figures pas tous auditibles (seuls les résultats A–D et le « contour ⇒ hamiltonien » sont clairs).
« 6.3 » relevé en début d’exercice 3 (= « exercice 3 » probablement) — ✅ interpreté comme exercice 3 du chapitre 3.

Apuntes de Andres

Explorador

TD2 - Graphes