View
134
Download
7
Category
Preview:
Citation preview
21 mars 2006 Cours de graphes 5 - Intranet 1
Cours de graphesCours de graphes
Coloriage de graphes.Coloriage de graphes.
Problème des 4 couleurs, graphes Problème des 4 couleurs, graphes planaires.planaires.
Théorème de Vizing.Théorème de Vizing.
Applications.Applications.
21 mars 2006 Cours de graphes 5 - Intranet 2
Les grandes lignes du coursLes grandes lignes du cours
•Définitions de baseDéfinitions de base•ConnexitéConnexité•Les plus courts cheminsLes plus courts chemins•Dijkstra et Bellmann-FordDijkstra et Bellmann-Ford•ArbresArbres•Arbres de recouvrement minimaux Arbres de recouvrement minimaux •Problèmes de flotsProblèmes de flots•Coloriage de graphes, Coloriage de graphes, graphes graphes planairesplanaires•CouplageCouplage•Chemins d’Euler et de HamiltonChemins d’Euler et de Hamilton•Problèmes NP-completsProblèmes NP-complets
21 mars 2006 Cours de graphes 5 - Intranet 3
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage des sommets d’un graphe :Coloriage des sommets d’un graphe :
– Deux voisins ne doivent pas avoir la même Deux voisins ne doivent pas avoir la même couleur !couleur !
– Il faut minimiser le nombre de couleurs !Il faut minimiser le nombre de couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 4
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage des sommets d’un graphe :Coloriage des sommets d’un graphe :
– Deux voisins ne doivent pas avoir la même Deux voisins ne doivent pas avoir la même couleur !couleur !
– Il faut minimiser le nombre de couleurs !Il faut minimiser le nombre de couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 5
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage des sommets d’un graphe :Coloriage des sommets d’un graphe :
– Deux voisins ne doivent pas avoir la même Deux voisins ne doivent pas avoir la même couleur !couleur !
– Il faut minimiser le nombre de couleurs !Il faut minimiser le nombre de couleurs !
Solution avecSolution avec5 couleurs !5 couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 6
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage des sommets d’un graphe :Coloriage des sommets d’un graphe :
– Deux voisins ne doivent pas avoir la même Deux voisins ne doivent pas avoir la même couleur !couleur !
– Il faut minimiser le nombre de couleurs !Il faut minimiser le nombre de couleurs !
Mais 2 couleursMais 2 couleurssuffisent !suffisent !
21 mars 2006 Cours de graphes 5 - Intranet 7
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage des sommets d’un graphe :Coloriage des sommets d’un graphe :
– Deux voisins ne doivent pas avoir la même couleur !Deux voisins ne doivent pas avoir la même couleur !
– Il faut minimiser le nombre de couleurs !Il faut minimiser le nombre de couleurs !
– Le minimum de couleurs nécessaires est le nombre chromatique Le minimum de couleurs nécessaires est le nombre chromatique
d’un graphe G, noté « d’un graphe G, noté « ( G ) » ( G ) » (lettre grecque chi de (lettre grecque chi de
« « », qui signifie couleur). », qui signifie couleur).
Mais 2 couleursMais 2 couleurssuffisent !suffisent !
21 mars 2006 Cours de graphes 5 - Intranet 8
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : téléphonie mobile !Application : téléphonie mobile !
– Il faut assurer la continuité de services entre Il faut assurer la continuité de services entre émetteurs !émetteurs !
– Les régions de couverture doivent donc se Les régions de couverture doivent donc se chevaucher, mais ne doivent pas générer chevaucher, mais ne doivent pas générer
d’interférences !d’interférences !
21 mars 2006 Cours de graphes 5 - Intranet 9
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : téléphonie mobile !Application : téléphonie mobile !
– Il faut assurer la continuité de services entre Il faut assurer la continuité de services entre émetteurs !émetteurs !
– Les régions de couverture doivent donc se Les régions de couverture doivent donc se chevaucher, mais ne doivent pas générer chevaucher, mais ne doivent pas générer
d’interférences !d’interférences !
– Chaque émetteur offre plusieurs fréquences Chaque émetteur offre plusieurs fréquences (couleurs) qui sont différentes de celles utilisées (couleurs) qui sont différentes de celles utilisées
par sespar ses voisins !voisins !
21 mars 2006 Cours de graphes 5 - Intranet 10
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : téléphonie mobile !Application : téléphonie mobile !
– Il faut assurer la continuité de services entre Il faut assurer la continuité de services entre émetteurs !émetteurs !
– Les régions de couverture doivent donc se Les régions de couverture doivent donc se chevaucher, mais ne doivent pas générer chevaucher, mais ne doivent pas générer
d’interférences !d’interférences !
– Chaque émetteur offre plusieurs fréquences Chaque émetteur offre plusieurs fréquences (couleurs) qui sont différentes de celles utilisées (couleurs) qui sont différentes de celles utilisées
par sespar ses voisins !voisins !
MM
21 mars 2006 Cours de graphes 5 - Intranet 11
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : téléphonie mobile !Application : téléphonie mobile !
– Il faut assurer la continuité de services entre Il faut assurer la continuité de services entre émetteurs !émetteurs !
– Les régions de couverture doivent donc se Les régions de couverture doivent donc se chevaucher, mais ne doivent pas générer chevaucher, mais ne doivent pas générer
d’interférences !d’interférences !
– Chaque émetteur offre plusieurs fréquences Chaque émetteur offre plusieurs fréquences (couleurs) qui sont différentes de celles utilisées (couleurs) qui sont différentes de celles utilisées
par sespar ses voisins !voisins !
MM
21 mars 2006 Cours de graphes 5 - Intranet 12
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : téléphonie mobile !Application : téléphonie mobile !
– Il faut assurer la continuité de services entre Il faut assurer la continuité de services entre émetteurs !émetteurs !
– Les régions de couverture doivent donc se Les régions de couverture doivent donc se chevaucher, mais ne doivent pas générer chevaucher, mais ne doivent pas générer
d’interférences !d’interférences !
– Chaque émetteur offre plusieurs fréquences Chaque émetteur offre plusieurs fréquences (couleurs) qui sont différentes de celles utilisées (couleurs) qui sont différentes de celles utilisées
par sespar ses voisins !voisins !
MM
21 mars 2006 Cours de graphes 5 - Intranet 13
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : téléphonie mobile !Application : téléphonie mobile !
– Il faut assurer la continuité de services entre Il faut assurer la continuité de services entre émetteurs !émetteurs !
– Les régions de couverture doivent donc se Les régions de couverture doivent donc se chevaucher, mais ne doivent pas générer chevaucher, mais ne doivent pas générer
d’interférences !d’interférences !
– Chaque émetteur offre plusieurs fréquences Chaque émetteur offre plusieurs fréquences (couleurs) qui sont différentes de celles utilisées (couleurs) qui sont différentes de celles utilisées
par sespar ses voisins !voisins !
21 mars 2006 Cours de graphes 5 - Intranet 14
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage des arêtes d’un graphe :Coloriage des arêtes d’un graphe :
– Deux arrêtes adjacentes ne doivent pas avoir Deux arrêtes adjacentes ne doivent pas avoir la même couleur !la même couleur !
– Il faut minimiser le nombre de couleurs !Il faut minimiser le nombre de couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 15
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage des arêtes d’un graphe :Coloriage des arêtes d’un graphe :
– Deux arrêtes adjacentes ne doivent pas avoir Deux arrêtes adjacentes ne doivent pas avoir la même couleur !la même couleur !
– Il faut minimiser le nombre de couleurs !Il faut minimiser le nombre de couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 16
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage des arêtes d’un graphe :Coloriage des arêtes d’un graphe :
– Deux arrêtes adjacentes ne doivent pas avoir Deux arrêtes adjacentes ne doivent pas avoir la même couleur !la même couleur !
– Il faut minimiser le nombre de couleurs !Il faut minimiser le nombre de couleurs !
Solution avecSolution avec6 couleurs !6 couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 17
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage des arêtes d’un graphe :Coloriage des arêtes d’un graphe :
– Deux arrêtes adjacentes ne doivent pas avoir Deux arrêtes adjacentes ne doivent pas avoir la même couleur !la même couleur !
– Il faut minimiser le nombre de couleurs !Il faut minimiser le nombre de couleurs !
Mais 4 couleursMais 4 couleurssuffisent !suffisent !
21 mars 2006 Cours de graphes 5 - Intranet 18
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : emplois du temps !Application : emplois du temps !
ProfsProfs ElèvesElèves
21 mars 2006 Cours de graphes 5 - Intranet 19
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : emplois du temps !Application : emplois du temps !
ProfsProfs ElèvesElèvesOraux !Oraux !
21 mars 2006 Cours de graphes 5 - Intranet 20
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : emplois du temps !Application : emplois du temps !
ProfsProfs ElèvesElèvesOraux !Oraux !
Créneaux horaires sous forme de couleurs !Créneaux horaires sous forme de couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 21
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : emplois du temps !Application : emplois du temps !
ProfsProfs ElèvesElèvesOraux !Oraux !
Créneaux horaires sous forme de couleurs !Créneaux horaires sous forme de couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 22
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : emplois du temps !Application : emplois du temps !
ProfsProfs ElèvesElèvesOraux !Oraux !
Créneaux horaires sous forme de couleurs !Créneaux horaires sous forme de couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 23
Coloriage de graphesColoriage de graphes----------------------------------------------------------------------------------------------------------------------------------
• Application : emplois du temps !Application : emplois du temps !
ProfsProfs ElèvesElèvesOraux !Oraux !
Créneaux horaires sous forme de couleurs !Créneaux horaires sous forme de couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 24
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
L EL EP R O B L E M EP R O B L E M E
D E SD E SQ U A T R E Q U A T R E
C O U L E U R S ! ! !C O U L E U R S ! ! !
21 mars 2006 Cours de graphes 5 - Intranet 25
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• En 1852, Francis Guthrie pose la question de savoir si En 1852, Francis Guthrie pose la question de savoir si toute mappemonde peut être coloriée avec 4 couleurs toute mappemonde peut être coloriée avec 4 couleurs
au plus ?au plus ?
21 mars 2006 Cours de graphes 5 - Intranet 26
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• En 1852, Francis Guthrie pose la question de savoir si En 1852, Francis Guthrie pose la question de savoir si toute mappemonde peut être coloriée avec 4 couleurs toute mappemonde peut être coloriée avec 4 couleurs
au plus ?au plus ?
21 mars 2006 Cours de graphes 5 - Intranet 27
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• En 1852, Francis Guthrie pose la question de savoir si En 1852, Francis Guthrie pose la question de savoir si toute mappemonde peut être coloriée avec 4 couleurs toute mappemonde peut être coloriée avec 4 couleurs
au plus ?au plus ? En termes de graphes !En termes de graphes !
21 mars 2006 Cours de graphes 5 - Intranet 28
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• En 1852, Francis Guthrie pose la question de savoir si En 1852, Francis Guthrie pose la question de savoir si toute mappemonde peut être coloriée avec 4 couleurs toute mappemonde peut être coloriée avec 4 couleurs
au plus ?au plus ? En termes de graphes !En termes de graphes !
C’est un problème de coloriage des sommets d’un graphe !C’est un problème de coloriage des sommets d’un graphe !
21 mars 2006 Cours de graphes 5 - Intranet 29
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• Nous devons considérer une partie des graphes Nous devons considérer une partie des graphes planaires !planaires !
21 mars 2006 Cours de graphes 5 - Intranet 30
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• Nous devons considérer une partie des graphes Nous devons considérer une partie des graphes planaires !planaires !
• Un graphe est planaire s’il peutUn graphe est planaire s’il peut
être dessiné dans le plan sansêtre dessiné dans le plan sans que des arêtes ne se croisent !que des arêtes ne se croisent !
21 mars 2006 Cours de graphes 5 - Intranet 31
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• Nous devons considérer une partie des graphes Nous devons considérer une partie des graphes planaires !planaires !
• Un graphe est planaire s’il peutUn graphe est planaire s’il peut
être dessiné dans le plan sansêtre dessiné dans le plan sans que des arêtes ne se croisent !que des arêtes ne se croisent !
21 mars 2006 Cours de graphes 5 - Intranet 32
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• Nous devons considérer une partie des graphes Nous devons considérer une partie des graphes planaires !planaires !
• Un graphe est planaire s’il peutUn graphe est planaire s’il peut
être dessiné dans le plan sansêtre dessiné dans le plan sans que des arêtes ne se croisent !que des arêtes ne se croisent !
• La famille à analyser est difficile à caractériser ! On La famille à analyser est difficile à caractériser ! On démontre vite que 5 couleurs suffisent, puis il faut démontre vite que 5 couleurs suffisent, puis il faut attendre un siècle !attendre un siècle !
21 mars 2006 Cours de graphes 5 - Intranet 33
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• Nous devons considérer une partie des graphes planaires !Nous devons considérer une partie des graphes planaires !
• Un graphe est planaire s’il peutUn graphe est planaire s’il peut
être dessiné dans le plan sansêtre dessiné dans le plan sans que des arêtes ne se croisent !que des arêtes ne se croisent !
• La famille à analyser est difficile à caractériser ! On La famille à analyser est difficile à caractériser ! On démontre vite que 5 couleurs suffisent, puis il faut attendre démontre vite que 5 couleurs suffisent, puis il faut attendre un siècle !un siècle !
• En 1976, Appel & Haken prouvent que 4 couleurs suffisent, En 1976, Appel & Haken prouvent que 4 couleurs suffisent, en étudiant 1476 graphes critiques par ordinateur !en étudiant 1476 graphes critiques par ordinateur ! Depuis, Depuis, on a pu simplifier le programme et se ramener àon a pu simplifier le programme et se ramener à 633 cas à 633 cas à étudier.étudier.
21 mars 2006 Cours de graphes 5 - Intranet 34
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• Nous devons considérer une partie des graphes planaires !Nous devons considérer une partie des graphes planaires !
• Un graphe est planaire s’il peutUn graphe est planaire s’il peut
être dessiné dans le plan sansêtre dessiné dans le plan sans que des arêtes ne se croisent !que des arêtes ne se croisent !
• La famille à analyser est difficile à caractériser ! On démontre La famille à analyser est difficile à caractériser ! On démontre vite que 5 couleurs suffisent, puis il faut attendre un siècle !vite que 5 couleurs suffisent, puis il faut attendre un siècle !
• En 1976, Appel & Haken prouvent que 4 couleurs suffisent, en En 1976, Appel & Haken prouvent que 4 couleurs suffisent, en étudiant 1476 graphes critiques par ordinateur !étudiant 1476 graphes critiques par ordinateur ! Depuis, on a Depuis, on a pu simplifier le programme et se ramener àpu simplifier le programme et se ramener à 633 cas à étudier.633 cas à étudier.
• Question chez les matheux : La preuve est-elle acceptable ???Question chez les matheux : La preuve est-elle acceptable ???
21 mars 2006 Cours de graphes 5 - Intranet 35
Le problème des 4 couleursLe problème des 4 couleurs----------------------------------------------------------------------------------------------------------------------------------
• Nous devons considérer une partie des graphes planaires !Nous devons considérer une partie des graphes planaires !
• Un graphe est planaire s’il peutUn graphe est planaire s’il peut
être dessiné dans le plan sansêtre dessiné dans le plan sans que des arêtes ne se croisent !que des arêtes ne se croisent !
• La famille à analyser est difficile à caractériser ! On démontre vite que La famille à analyser est difficile à caractériser ! On démontre vite que 5 couleurs suffisent, puis il faut attendre un siècle !5 couleurs suffisent, puis il faut attendre un siècle !
• En 1976, Appel & Haken prouvent que 4 couleurs suffisent, en étudiant En 1976, Appel & Haken prouvent que 4 couleurs suffisent, en étudiant 1476 graphes critiques par ordinateur !1476 graphes critiques par ordinateur ! Depuis, on a pu simplifier le Depuis, on a pu simplifier le programme et se ramener àprogramme et se ramener à 633 cas à étudier.633 cas à étudier.
• Question chez les matheux : La preuve est-elle acceptable ???Question chez les matheux : La preuve est-elle acceptable ???
• On peut construire un 4-coloriage en temps O ( | V |^2 ) !On peut construire un 4-coloriage en temps O ( | V |^2 ) !
21 mars 2006 Cours de graphes 5 - Intranet 36
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
L E SL E S
G R A P H E SG R A P H E S
P L A N A I R E S ! ! !P L A N A I R E S ! ! !
21 mars 2006 Cours de graphes 5 - Intranet 37
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
21 mars 2006 Cours de graphes 5 - Intranet 38
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
OUI !OUI !
21 mars 2006 Cours de graphes 5 - Intranet 39
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
OUI !OUI !
21 mars 2006 Cours de graphes 5 - Intranet 40
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
OUI !OUI !
21 mars 2006 Cours de graphes 5 - Intranet 41
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
OUI !OUI !
21 mars 2006 Cours de graphes 5 - Intranet 42
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
OUI !OUI !
NON, il y auraNON, il y auratoujours untoujours unproblème pourproblème pourune arête !une arête !
21 mars 2006 Cours de graphes 5 - Intranet 43
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
OUI !OUI !
NON, il y auraNON, il y auratoujours untoujours unproblème pourproblème pourune arête !une arête !
21 mars 2006 Cours de graphes 5 - Intranet 44
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
OUI !OUI !
NON, il y auraNON, il y auratoujours untoujours unproblème pourproblème pourune arête !une arête !
21 mars 2006 Cours de graphes 5 - Intranet 45
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
OUI !OUI !
NON, il y auraNON, il y auratoujours untoujours unproblème pourproblème pourune arête !une arête !
21 mars 2006 Cours de graphes 5 - Intranet 46
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
• Est-ce que ce graphe est planaire ?Est-ce que ce graphe est planaire ?
OUI !OUI !
NON, il y auraNON, il y auratoujours untoujours unproblème pourproblème pourune arête !une arête !
C’est le graphe bi-partiC’est le graphe bi-particomplet 3 – 3 : K !complet 3 – 3 : K !
3,33,3
21 mars 2006 Cours de graphes 5 - Intranet 47
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Le graphe complet à 5 sommets, K , n’est pas planaire Le graphe complet à 5 sommets, K , n’est pas planaire !! 55
En construction !En construction !
21 mars 2006 Cours de graphes 5 - Intranet 48
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Le graphe complet à 5 sommets, K , n’est pas planaire Le graphe complet à 5 sommets, K , n’est pas planaire !! 55
En construction !En construction !
21 mars 2006 Cours de graphes 5 - Intranet 49
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Le graphe complet à 5 sommets, K , n’est pas planaire Le graphe complet à 5 sommets, K , n’est pas planaire !! 55
En construction !En construction !
21 mars 2006 Cours de graphes 5 - Intranet 50
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Le graphe complet à 5 sommets, K , n’est pas planaire Le graphe complet à 5 sommets, K , n’est pas planaire !! 55
En construction !En construction !
21 mars 2006 Cours de graphes 5 - Intranet 51
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Le graphe complet à 5 sommets, K , n’est pas planaire Le graphe complet à 5 sommets, K , n’est pas planaire !! 55
Le voilà !Le voilà !
21 mars 2006 Cours de graphes 5 - Intranet 52
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Le graphe complet à 5 sommets, K , n’est pas planaire Le graphe complet à 5 sommets, K , n’est pas planaire !! 55
Le voilà !Le voilà !
21 mars 2006 Cours de graphes 5 - Intranet 53
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Deux graphes sont homéomorphes si l’un peut être Deux graphes sont homéomorphes si l’un peut être obtenu à partir l’autre par insertion de sommets de obtenu à partir l’autre par insertion de sommets de degré 2 !degré 2 !
21 mars 2006 Cours de graphes 5 - Intranet 54
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Deux graphes sont homéomorphes si l’un peut être Deux graphes sont homéomorphes si l’un peut être obtenu à partir l’autre par insertion de sommets de obtenu à partir l’autre par insertion de sommets de degré 2 !degré 2 !
21 mars 2006 Cours de graphes 5 - Intranet 55
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Deux graphes sont homéomorphes si l’un peut être Deux graphes sont homéomorphes si l’un peut être obtenu à partir l’autre par insertion de sommets de obtenu à partir l’autre par insertion de sommets de degré 2 !degré 2 !
21 mars 2006 Cours de graphes 5 - Intranet 56
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Théorème (Kuratowski, 1930) :Théorème (Kuratowski, 1930) :
– Un graphe est planaire si et seulement s’il ne Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe homéomorphe à K contient pas de sous-graphe homéomorphe à K ou à K !ou à K ! 553,33,3
21 mars 2006 Cours de graphes 5 - Intranet 57
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Théorème (Kuratowski, 1930) :Théorème (Kuratowski, 1930) :
– Un graphe est planaire si et seulement s’il ne Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe homéomorphe à K contient pas de sous-graphe homéomorphe à K ou à K !ou à K ! 553,33,3
PlanairePlanaireou non ?ou non ?
21 mars 2006 Cours de graphes 5 - Intranet 58
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Théorème (Kuratowski, 1930) :Théorème (Kuratowski, 1930) :
– Un graphe est planaire si et seulement s’il ne Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe homéomorphe à K contient pas de sous-graphe homéomorphe à K ou à K !ou à K ! 553,33,3
PlanairePlanaireou non ?ou non ?
NON !NON !
KK3,33,3
21 mars 2006 Cours de graphes 5 - Intranet 59
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Un graphe G peut se contracter en un graphe G’ de la Un graphe G peut se contracter en un graphe G’ de la façon suivante :façon suivante :
GG
21 mars 2006 Cours de graphes 5 - Intranet 60
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Un graphe G peut se contracter en un graphe G’ de la Un graphe G peut se contracter en un graphe G’ de la façon suivante :façon suivante :
GG G’G’
21 mars 2006 Cours de graphes 5 - Intranet 61
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Un graphe G peut se contracter en un graphe G’ de la Un graphe G peut se contracter en un graphe G’ de la façon suivante :façon suivante :
GG G’G’
GG
21 mars 2006 Cours de graphes 5 - Intranet 62
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Un graphe G peut se contracter en un graphe G’ de la Un graphe G peut se contracter en un graphe G’ de la façon suivante :façon suivante :
GG G’G’
GG G’G’
21 mars 2006 Cours de graphes 5 - Intranet 63
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Théorème :Théorème :
– Un graphe est planaire si et seulement s’il ne Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe qui se contracte vers K contient pas de sous-graphe qui se contracte vers K ou vers K ! ou vers K ! 553,33,3
21 mars 2006 Cours de graphes 5 - Intranet 64
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Théorème :Théorème :
– Un graphe est planaire si et seulement s’il ne Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe qui se contracte vers K contient pas de sous-graphe qui se contracte vers K ou vers K ! ou vers K ! 553,33,3
PlanairePlanaireou non ?ou non ?
21 mars 2006 Cours de graphes 5 - Intranet 65
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Théorème :Théorème :
– Un graphe est planaire si et seulement s’il ne Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe qui se contracte vers K contient pas de sous-graphe qui se contracte vers K ou vers K ! ou vers K ! 553,33,3
PlanairePlanaireou non ?ou non ?
Sous-graphe !Sous-graphe !
21 mars 2006 Cours de graphes 5 - Intranet 66
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Théorème :Théorème :
– Un graphe est planaire si et seulement s’il ne Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe qui se contracte vers K contient pas de sous-graphe qui se contracte vers K ou vers K ! ou vers K ! 553,33,3
PlanairePlanaireou non ?ou non ?
Sous-graphe !Sous-graphe !
21 mars 2006 Cours de graphes 5 - Intranet 67
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Théorème :Théorème :
– Un graphe est planaire si et seulement s’il ne Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe qui se contracte vers K contient pas de sous-graphe qui se contracte vers K ou vers K ! ou vers K ! 553,33,3
PlanairePlanaireou non ?ou non ?
Sous-graphe !Sous-graphe !
Contraction !Contraction !
21 mars 2006 Cours de graphes 5 - Intranet 68
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Théorème :Théorème :
– Un graphe est planaire si et seulement s’il ne Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe qui se contracte vers K contient pas de sous-graphe qui se contracte vers K ou vers K ! ou vers K ! 553,33,3
PlanairePlanaireou non ?ou non ?
Sous-graphe !Sous-graphe !
NON !NON !
KK3,33,3
21 mars 2006 Cours de graphes 5 - Intranet 69
Les graphes planairesLes graphes planaires----------------------------------------------------------------------------------------------------------------------------------
• Attention :Attention :
– Nous n’avons pas encore dit comment il faut Nous n’avons pas encore dit comment il faut faire concrètement pour trouver une faire concrètement pour trouver une représentation planaire d’un graphe qui l’est !représentation planaire d’un graphe qui l’est !
• Applications :Applications :
– Organisation de circuits électroniques !Organisation de circuits électroniques !
21 mars 2006 Cours de graphes 5 - Intranet 70
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
C O L O R I A G EC O L O R I A G E
D E SD E S
S O M M E T S ! ! !S O M M E T S ! ! !
21 mars 2006 Cours de graphes 5 - Intranet 71
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
21 mars 2006 Cours de graphes 5 - Intranet 72
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Une clique est un sous-ensembleUne clique est un sous-ensemblede sommets qui sont voisins 2 à 2.de sommets qui sont voisins 2 à 2.
21 mars 2006 Cours de graphes 5 - Intranet 73
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Une clique est un sous-ensembleUne clique est un sous-ensemblede sommets qui sont voisins 2 à 2.de sommets qui sont voisins 2 à 2.
Les sommets d’une clique doiventLes sommets d’une clique doiventtous avoir des couleurs différentes !tous avoir des couleurs différentes !
21 mars 2006 Cours de graphes 5 - Intranet 74
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Une clique est un sous-ensembleUne clique est un sous-ensemblede sommets qui sont voisins 2 à 2.de sommets qui sont voisins 2 à 2.
Les sommets d’une clique doiventLes sommets d’une clique doiventtous avoir des couleurs différentes !tous avoir des couleurs différentes !
Le nombre chromatique du grapheLe nombre chromatique du grapheest au moins aussi grand que laest au moins aussi grand que lataille de la plus grande clique !taille de la plus grande clique !
21 mars 2006 Cours de graphes 5 - Intranet 75
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Il est clair que D ( G ) + 1Il est clair que D ( G ) + 1couleurs suffisent !couleurs suffisent !
Nous pouvons trouver uneNous pouvons trouver une couleur pour tout sommet, couleur pour tout sommet,
même si tous ses voisins ontmême si tous ses voisins ont déjà des couleurs et quedéjà des couleurs et quecelles-ci sont toutes différentes !celles-ci sont toutes différentes !
21 mars 2006 Cours de graphes 5 - Intranet 76
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
21 mars 2006 Cours de graphes 5 - Intranet 77
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
== ==
21 mars 2006 Cours de graphes 5 - Intranet 78
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
== ==
21 mars 2006 Cours de graphes 5 - Intranet 79
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
== <<<<
21 mars 2006 Cours de graphes 5 - Intranet 80
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
== <<<<
21 mars 2006 Cours de graphes 5 - Intranet 81
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
<< ==
21 mars 2006 Cours de graphes 5 - Intranet 82
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
<< ==
En construction !En construction !
21 mars 2006 Cours de graphes 5 - Intranet 83
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
<< ==
En construction !En construction !
21 mars 2006 Cours de graphes 5 - Intranet 84
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
<< ==
En construction !En construction !
21 mars 2006 Cours de graphes 5 - Intranet 85
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
<< ==
Le voilà !Le voilà !
21 mars 2006 Cours de graphes 5 - Intranet 86
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
<< ==
Le voilà !Le voilà !
21 mars 2006 Cours de graphes 5 - Intranet 87
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
<< ==
Le voilà !Le voilà !
21 mars 2006 Cours de graphes 5 - Intranet 88
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
<< ==
Le voilà !Le voilà !
21 mars 2006 Cours de graphes 5 - Intranet 89
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
taille_clique_max ( G ) <= taille_clique_max ( G ) <= ( G ) <= D ( G ) + 1 ( G ) <= D ( G ) + 1
Montrons que cet encadrement ne peut pas être amélioré !Montrons que cet encadrement ne peut pas être amélioré !
<< ==
Le voilà !Le voilà !
21 mars 2006 Cours de graphes 5 - Intranet 90
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• La question de savoir siLa question de savoir si
un graphe « G » peut être colorié à l’aide de « k » couleurs au un graphe « G » peut être colorié à l’aide de « k » couleurs au plusplus
est NPest NP--complète ! ! ! complète ! ! !
21 mars 2006 Cours de graphes 5 - Intranet 91
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• La question de savoir siLa question de savoir si
un graphe « G » peut être colorié à l’aide de « k » couleurs au un graphe « G » peut être colorié à l’aide de « k » couleurs au plusplus
est NPest NP--complète ! ! ! complète ! ! !
• Le problème deLe problème de
minimiser le nombre de couleurs pour colorier un graphe « G »minimiser le nombre de couleurs pour colorier un graphe « G »
est NPest NP--difficile ! ! ! difficile ! ! !
21 mars 2006 Cours de graphes 5 - Intranet 92
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Une politique locale ne convient pas !Une politique locale ne convient pas !
– Soit le cas ci-dessous, avec un choix à faire pour « u » !Soit le cas ci-dessous, avec un choix à faire pour « u » !
– Une minimisation locale veut que « u » soit « Une minimisation locale veut que « u » soit « rougerouge » ! ! ! » ! ! !
uu
21 mars 2006 Cours de graphes 5 - Intranet 93
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Une politique locale ne convient pas !Une politique locale ne convient pas !
– Soit le cas ci-dessous, avec un choix à faire pour « u » !Soit le cas ci-dessous, avec un choix à faire pour « u » !
– Une minimisation locale veut que « u » soit « Une minimisation locale veut que « u » soit « rougerouge » ! ! ! » ! ! !
uu
21 mars 2006 Cours de graphes 5 - Intranet 94
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Une politique locale ne convient pas !Une politique locale ne convient pas !
– Soit le cas ci-dessous, avec un choix à faire pour « u » !Soit le cas ci-dessous, avec un choix à faire pour « u » !
– Une minimisation locale veut que « u » soit « Une minimisation locale veut que « u » soit « rougerouge » ! ! ! » ! ! !
uu
21 mars 2006 Cours de graphes 5 - Intranet 95
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Une politique locale ne convient pas !Une politique locale ne convient pas !
– Soit le cas ci-dessous, avec un choix à faire pour « u » !Soit le cas ci-dessous, avec un choix à faire pour « u » !
– Une minimisation locale veut que « u » soit « Une minimisation locale veut que « u » soit « rougerouge » ! ! ! » ! ! !
uu
21 mars 2006 Cours de graphes 5 - Intranet 96
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Une politique locale ne convient pas !Une politique locale ne convient pas !
– Soit le cas ci-dessous, avec un choix à faire pour « u » !Soit le cas ci-dessous, avec un choix à faire pour « u » !
– Une minimisation locale veut que « u » soit « Une minimisation locale veut que « u » soit « rougerouge » ! ! ! » ! ! !
uu5 couleurs !5 couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 97
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Une politique locale ne convient pas !Une politique locale ne convient pas !
– Soit le cas ci-dessous, avec un choix à faire pour « u » !Soit le cas ci-dessous, avec un choix à faire pour « u » !
– Il fallait une nouvelle couleur pour « u » : « Il fallait une nouvelle couleur pour « u » : « bleubleu » ! ! ! » ! ! !
uu
21 mars 2006 Cours de graphes 5 - Intranet 98
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Une politique locale ne convient pas !Une politique locale ne convient pas !
– Soit le cas ci-dessous, avec un choix à faire pour « u » !Soit le cas ci-dessous, avec un choix à faire pour « u » !
– Il fallait une nouvelle couleur pour « u » : « Il fallait une nouvelle couleur pour « u » : « bleubleu » ! ! ! » ! ! !
uu
21 mars 2006 Cours de graphes 5 - Intranet 99
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Une politique locale ne convient pas !Une politique locale ne convient pas !
– Soit le cas ci-dessous, avec un choix à faire pour « u » !Soit le cas ci-dessous, avec un choix à faire pour « u » !
– Il fallait une nouvelle couleur pour « u » : « Il fallait une nouvelle couleur pour « u » : « bleubleu » ! ! ! » ! ! !
uu3 couleurs !3 couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 100
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Une politique locale ne convient pas !Une politique locale ne convient pas !
– Soit le cas ci-dessous, avec un choix à faire pour « u » !Soit le cas ci-dessous, avec un choix à faire pour « u » !
– Il fallait une nouvelle couleur pour « u » : « Il fallait une nouvelle couleur pour « u » : « bleubleu » ! ! ! » ! ! !
uu3 couleurs !3 couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 101
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Principe d’une énumération complète !Principe d’une énumération complète !
– Nous avons une solution avec « m » couleurs, D( G ) + 1 au Nous avons une solution avec « m » couleurs, D( G ) + 1 au début !début !
– Certains sommets ont déjà des couleurs !Certains sommets ont déjà des couleurs !
– « C » est l’ensemble des couleurs déjà utilisées !« C » est l’ensemble des couleurs déjà utilisées !
21 mars 2006 Cours de graphes 5 - Intranet 102
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Principe d’une énumération complète !Principe d’une énumération complète !
– Nous avons une solution avec « m » couleurs, D( G ) + 1 au Nous avons une solution avec « m » couleurs, D( G ) + 1 au début !début !
– Certains sommets ont déjà des couleurs !Certains sommets ont déjà des couleurs !
– « C » est l’ensemble des couleurs déjà utilisées !« C » est l’ensemble des couleurs déjà utilisées !
• Nous back-trackons pour un sommet « u » enNous back-trackons pour un sommet « u » en
– explorant pour « u » le choix de toutes les couleurs de « C » explorant pour « u » le choix de toutes les couleurs de « C » qui ne sont pas prises par un de ses voisins,qui ne sont pas prises par un de ses voisins,
21 mars 2006 Cours de graphes 5 - Intranet 103
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Principe d’une énumération complète !Principe d’une énumération complète !
– Nous avons une solution avec « m » couleurs, D( G ) + 1 au Nous avons une solution avec « m » couleurs, D( G ) + 1 au début !début !
– Certains sommets ont déjà des couleurs !Certains sommets ont déjà des couleurs !
– « C » est l’ensemble des couleurs déjà utilisées !« C » est l’ensemble des couleurs déjà utilisées !
• Nous back-trackons pour un sommet « u » enNous back-trackons pour un sommet « u » en
– explorant pour « u » le choix de toutes les couleurs de « C » explorant pour « u » le choix de toutes les couleurs de « C » qui ne sont pas prises par un de ses voisins,qui ne sont pas prises par un de ses voisins,
– en attribuant une nouvelle couleur à « u », à moins que ceci ne en attribuant une nouvelle couleur à « u », à moins que ceci ne nous amène à utiliser plus que « m » couleurs !nous amène à utiliser plus que « m » couleurs !
21 mars 2006 Cours de graphes 5 - Intranet 104
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Heuristique de coloriage !Heuristique de coloriage !
– Nous renonçons à la solution optimale et nous nous Nous renonçons à la solution optimale et nous nous contentons d’une contentons d’une solution pas trop mauvaisesolution pas trop mauvaise trouvée de trouvée de manière gloutonne !manière gloutonne !
21 mars 2006 Cours de graphes 5 - Intranet 105
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Heuristique de coloriage !Heuristique de coloriage !
– Nous renonçons à la solution optimale et nous nous Nous renonçons à la solution optimale et nous nous contentons d’une contentons d’une solution pas trop mauvaisesolution pas trop mauvaise trouvée de trouvée de manière gloutonne !manière gloutonne !
• Nous considérons les sommets dans un ordre pré-défini :Nous considérons les sommets dans un ordre pré-défini :
– aléatoire,aléatoire,– plus grand degré d’abord,plus grand degré d’abord,– plus au centre d’abord,plus au centre d’abord,– . . .. . .
21 mars 2006 Cours de graphes 5 - Intranet 106
Coloriage des sommetsColoriage des sommets----------------------------------------------------------------------------------------------------------------------------------
• Heuristique de coloriage !Heuristique de coloriage !
– Nous renonçons à la solution optimale et nous nous contentons d’une Nous renonçons à la solution optimale et nous nous contentons d’une solution pas trop mauvaisesolution pas trop mauvaise trouvée de manière gloutonne ! trouvée de manière gloutonne !
• Nous considérons les sommets dans un ordre pré-défini :Nous considérons les sommets dans un ordre pré-défini :
– aléatoire,aléatoire,– plus grand degré d’abord,plus grand degré d’abord,– plus au centre d’abord,plus au centre d’abord,– . . .. . .
• Le sommet va rejoindre un ensemble de sommets de la même couleur Le sommet va rejoindre un ensemble de sommets de la même couleur que lui, si c’est possible (sinon, nous créons une nouvelle couleur) :que lui, si c’est possible (sinon, nous créons une nouvelle couleur) :
– aléatoire,aléatoire,– l’ensemble le plus grand ( largest independent set ),l’ensemble le plus grand ( largest independent set ),– l’ensemble le plus petit ( utilisation équilibrée des couleurs),l’ensemble le plus petit ( utilisation équilibrée des couleurs),– . . .. . .
21 mars 2006 Cours de graphes 5 - Intranet 107
Graphes bi-partisGraphes bi-partis----------------------------------------------------------------------------------------------------------------------------------
G R A P H E SG R A P H E S
B I – P A R T I S ! ! !B I – P A R T I S ! ! !
21 mars 2006 Cours de graphes 5 - Intranet 108
Graphes bi-partisGraphes bi-partis----------------------------------------------------------------------------------------------------------------------------------
• Un graphe est bi-parti si ses sommets peuvent être Un graphe est bi-parti si ses sommets peuvent être
coloriés à l’aide de deux couleurs seulement !coloriés à l’aide de deux couleurs seulement !
21 mars 2006 Cours de graphes 5 - Intranet 109
Graphes bi-partisGraphes bi-partis----------------------------------------------------------------------------------------------------------------------------------
• Un graphe est bi-parti si ses sommets peuvent être Un graphe est bi-parti si ses sommets peuvent être
coloriés à l’aide de deux couleurs seulement !coloriés à l’aide de deux couleurs seulement !
Aucun sommet n’est relié à unAucun sommet n’est relié à unautre sommet de même couleur !autre sommet de même couleur !
21 mars 2006 Cours de graphes 5 - Intranet 110
Graphes bi-partisGraphes bi-partis----------------------------------------------------------------------------------------------------------------------------------
• Un graphe est bi-parti si ses sommets peuvent être Un graphe est bi-parti si ses sommets peuvent être
coloriés à l’aide de deux couleurs seulement !coloriés à l’aide de deux couleurs seulement !
• Les arbres sont des graphes bi-partis !Les arbres sont des graphes bi-partis !
Aucun sommet n’est relié à unAucun sommet n’est relié à unautre sommet de même couleur !autre sommet de même couleur !
21 mars 2006 Cours de graphes 5 - Intranet 111
Graphes bi-partisGraphes bi-partis----------------------------------------------------------------------------------------------------------------------------------
• Un graphe est bi-parti si ses sommets peuvent être Un graphe est bi-parti si ses sommets peuvent être
coloriés à l’aide de deux couleurs seulement !coloriés à l’aide de deux couleurs seulement !
• Les arbres sont des graphes bi-partis !Les arbres sont des graphes bi-partis !
Aucun sommet n’est relié à unAucun sommet n’est relié à unautre sommet de même couleur !autre sommet de même couleur !
21 mars 2006 Cours de graphes 5 - Intranet 112
Graphes bi-partisGraphes bi-partis----------------------------------------------------------------------------------------------------------------------------------
• Un graphe est bi-parti si ses sommets peuvent être coloriés à l’aide Un graphe est bi-parti si ses sommets peuvent être coloriés à l’aide
de deux couleurs seulement !de deux couleurs seulement !
• Les arbres sont des graphes bi-partis !Les arbres sont des graphes bi-partis !
• Théorème ( TD ) : Un graphe est bi-parti si et seulement si tous ses Théorème ( TD ) : Un graphe est bi-parti si et seulement si tous ses
cycles sont de longueurs paires !cycles sont de longueurs paires !
Aucun sommet n’est relié à unAucun sommet n’est relié à unautre sommet de même couleur !autre sommet de même couleur !
21 mars 2006 Cours de graphes 5 - Intranet 113
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
C O L O R I A G EC O L O R I A G E
D E SD E S
A R E T E S ! ! !A R E T E S ! ! !
21 mars 2006 Cours de graphes 5 - Intranet 114
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Minimisation des couleurs !Minimisation des couleurs !
– Il faut au moins D ( G ) couleurs !Il faut au moins D ( G ) couleurs !– En effet, il existe un sommet dans « G » avec « D( G ) » En effet, il existe un sommet dans « G » avec « D( G ) »
voisins !voisins !
21 mars 2006 Cours de graphes 5 - Intranet 115
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Minimisation des couleurs !Minimisation des couleurs !
– Il faut au moins D ( G ) couleurs !Il faut au moins D ( G ) couleurs !– En effet, il existe un sommet dans « G » avec « D( G ) » En effet, il existe un sommet dans « G » avec « D( G ) »
voisins !voisins !
• Maximisation des couleurs !Maximisation des couleurs !
– D ( G ) + 1 couleurs suffisent ! ! !D ( G ) + 1 couleurs suffisent ! ! !– Théorème de Vizing (1964) !Théorème de Vizing (1964) ! – L’algorithme de coloriage est en L’algorithme de coloriage est en ( | E | ) !( | E | ) !
21 mars 2006 Cours de graphes 5 - Intranet 116
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Minimisation des couleurs !Minimisation des couleurs !
– Il faut au moins D ( G ) couleurs !Il faut au moins D ( G ) couleurs !– En effet, il existe un sommet dans « G » avec « D( G ) » En effet, il existe un sommet dans « G » avec « D( G ) »
voisins !voisins !
• Maximisation des couleurs !Maximisation des couleurs !
– D ( G ) + 1 couleurs suffisent ! ! !D ( G ) + 1 couleurs suffisent ! ! !– Théorème de Vizing (1964) !Théorème de Vizing (1964) ! – L’algorithme de coloriage est en L’algorithme de coloriage est en ( | E | ) !( | E | ) !
21 mars 2006 Cours de graphes 5 - Intranet 117
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Minimisation des couleurs !Minimisation des couleurs !
– Il faut au moins D ( G ) couleurs !Il faut au moins D ( G ) couleurs !– En effet, il existe un sommet dans « G » avec « D( G ) » En effet, il existe un sommet dans « G » avec « D( G ) »
voisins !voisins !
• Maximisation des couleurs !Maximisation des couleurs !
– D ( G ) + 1 couleurs suffisent ! ! !D ( G ) + 1 couleurs suffisent ! ! !– Théorème de Vizing (1964) !Théorème de Vizing (1964) ! – L’algorithme de coloriage est en L’algorithme de coloriage est en ( | E | ) !( | E | ) !
21 mars 2006 Cours de graphes 5 - Intranet 118
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
T H E O R E M ET H E O R E M E
D ED E
V I Z I N G ! ! !V I Z I N G ! ! !
21 mars 2006 Cours de graphes 5 - Intranet 119
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage de G = ( V , { e , . . . , e } ) avec D( G ) + 1 Coloriage de G = ( V , { e , . . . , e } ) avec D( G ) + 1 couleurs !couleurs ! mm11
21 mars 2006 Cours de graphes 5 - Intranet 120
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage de G = ( V , { e , . . . , e } ) avec D( G ) + 1 Coloriage de G = ( V , { e , . . . , e } ) avec D( G ) + 1 couleurs !couleurs !
• L’hypothèse :L’hypothèse :
– G = ( V , { e , . . . , e } ) est colorié !G = ( V , { e , . . . , e } ) est colorié !
mm11
11ii--11 ii--11
21 mars 2006 Cours de graphes 5 - Intranet 121
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage de G = ( V , { e , . . . , e } ) avec D( G ) + 1 Coloriage de G = ( V , { e , . . . , e } ) avec D( G ) + 1 couleurs !couleurs !
• L’hypothèse :L’hypothèse :
– G = ( V , { e , . . . , e } ) est colorié !G = ( V , { e , . . . , e } ) est colorié !
• Nous étendons ce coloriage vers G en coloriant e !Nous étendons ce coloriage vers G en coloriant e !
mm11
11ii--11 ii--11
iiii
21 mars 2006 Cours de graphes 5 - Intranet 122
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Coloriage de G = ( V , { e , . . . , e } ) avec D( G ) + 1 Coloriage de G = ( V , { e , . . . , e } ) avec D( G ) + 1 couleurs !couleurs !
• L’hypothèse :L’hypothèse :
– G = ( V , { e , . . . , e } ) est colorié !G = ( V , { e , . . . , e } ) est colorié !
• Nous étendons ce coloriage vers G en coloriant e !Nous étendons ce coloriage vers G en coloriant e !
• Notation :Notation :
– Abs( u ) est l’ensemble des couleurs absentes du sommet « u » !Abs( u ) est l’ensemble des couleurs absentes du sommet « u » !
– Abs( u ) n’est jamais vide ! ! !Abs( u ) n’est jamais vide ! ! !
mm11
11ii--11 ii--11
iiii
21 mars 2006 Cours de graphes 5 - Intranet 123
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Soit e = ( v , w ) !Soit e = ( v , w ) !ii 11
vv
ww
11
21 mars 2006 Cours de graphes 5 - Intranet 124
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Soit e = ( v , w ) !Soit e = ( v , w ) !
• Premier cas, favorable :Premier cas, favorable :
– Il existe une couleur « c » avec c Il existe une couleur « c » avec c Abs( v ) Abs( w Abs( v ) Abs( w ) !) !
– Utilisons donc cette couleur ! ! !Utilisons donc cette couleur ! ! !
ii 11
11
vv
ww
11
vv
21 mars 2006 Cours de graphes 5 - Intranet 125
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Soit e = ( v , w ) !Soit e = ( v , w ) !
• Premier cas, favorable :Premier cas, favorable :
– Il existe une couleur « c » avec c Il existe une couleur « c » avec c Abs( v ) Abs( w Abs( v ) Abs( w ) !) !
– Utilisons donc cette couleur ! ! !Utilisons donc cette couleur ! ! !
• Deuxième cas, défavorable :Deuxième cas, défavorable :
– Abs( v ) Abs( w ) est vide !Abs( v ) Abs( w ) est vide !
ii 11
11
vv
ww
11
vv
11
vv
vv
ww
11
??
21 mars 2006 Cours de graphes 5 - Intranet 126
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Soit e = ( v , w ) !Soit e = ( v , w ) !
• Premier cas, favorable :Premier cas, favorable :
– Il existe une couleur « c » avec c Il existe une couleur « c » avec c Abs( v ) Abs( w Abs( v ) Abs( w ) !) !
– Utilisons donc cette couleur ! ! !Utilisons donc cette couleur ! ! !
• Deuxième cas, défavorable :Deuxième cas, défavorable :
– Abs( v ) Abs( w ) est vide !Abs( v ) Abs( w ) est vide !– Soit c Soit c Abs( v ) ! Abs( v ) !
ii 11
11
vv
ww
11
vv
11
vv
11 11
vv
ww
11Sans cSans c11
??
21 mars 2006 Cours de graphes 5 - Intranet 127
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Soit e = ( v , w ) !Soit e = ( v , w ) !
• Premier cas, favorable :Premier cas, favorable :
– Il existe une couleur « c » avec c Il existe une couleur « c » avec c Abs( v ) Abs( v ) Abs( w ) !Abs( w ) !
– Utilisons donc cette couleur ! ! !Utilisons donc cette couleur ! ! !
• Deuxième cas, défavorable :Deuxième cas, défavorable :
– Abs( v ) Abs( w ) est vide !Abs( v ) Abs( w ) est vide !– Soit c Soit c Abs( v ) ! Abs( v ) ! – Donc, c Donc, c Abs ( w ) ! Abs ( w ) !
ii 11
11
vv
ww
11
vv
11
vv
11 11
vv
ww
11Sans cSans c11
11 //
??
21 mars 2006 Cours de graphes 5 - Intranet 128
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Soit e = ( v , w ) !Soit e = ( v , w ) !
• Premier cas, favorable :Premier cas, favorable :
– Il existe une couleur « c » avec c Il existe une couleur « c » avec c Abs( v ) Abs( w ) ! Abs( v ) Abs( w ) !– Utilisons donc cette couleur ! ! !Utilisons donc cette couleur ! ! !
• Deuxième cas, défavorable :Deuxième cas, défavorable :
– Abs( v ) Abs( w ) est vide !Abs( v ) Abs( w ) est vide !– Soit c Soit c Abs( v ) ! Abs( v ) ! – Donc, c Donc, c Abs ( w ) ! Abs ( w ) ! – Il existe v tel que ( v , w )Il existe v tel que ( v , w ) ait la couleur c !ait la couleur c !
ii 11
11
vv
ww
11
vv
11
vv
11 11
vv
ww
11Sans cSans c11
11 //
22 22 11
vv22
cc 11??
21 mars 2006 Cours de graphes 5 - Intranet 129
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire ? ? ?Que faire ? ? ? vv
ww
11Sans cSans c11 vv
22
cc 11??
21 mars 2006 Cours de graphes 5 - Intranet 130
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire ? ? ?Que faire ? ? ?
• Nous essayons deNous essayons de
– trouver une couleur « c » avec c trouver une couleur « c » avec c Abs( v ) Abs( v ) Abs( w ) !Abs( w ) !
vv
ww
11Sans cSans c11 vv
22
cc 11
22
vv
??
21 mars 2006 Cours de graphes 5 - Intranet 131
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire ? ? ?Que faire ? ? ?
• Nous essayons deNous essayons de
– trouver une couleur « c » avec c trouver une couleur « c » avec c Abs( v ) Abs( v ) Abs( w ) !Abs( w ) !
– Nous utilisons cette couleur à la place de c ! ! !Nous utilisons cette couleur à la place de c ! ! !
vv
ww
11Sans cSans c11 vv
22
cc 11
22
vv11
cc
XXXX??
21 mars 2006 Cours de graphes 5 - Intranet 132
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire ? ? ?Que faire ? ? ?
• Nous essayons deNous essayons de
– trouver une couleur « c » avec c trouver une couleur « c » avec c Abs( v ) Abs( v ) Abs( w ) !Abs( w ) !
– Nous utilisons cette couleur à la place de c ! ! !Nous utilisons cette couleur à la place de c ! ! ! – c peut être utilisée pour ( v , w ) ! ! !c peut être utilisée pour ( v , w ) ! ! !
vv
ww
11Sans cSans c11 vv
22
cc 11
22
vv11
cc
XXXX
11 11
cc 11
21 mars 2006 Cours de graphes 5 - Intranet 133
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire ? ? ?Que faire ? ? ?
• Nous essayons deNous essayons de
– trouver une couleur « c » avec c trouver une couleur « c » avec c Abs( v ) Abs( v ) Abs( w ) !Abs( w ) !
– Nous utilisons cette couleur à la place de c ! ! !Nous utilisons cette couleur à la place de c ! ! ! – c peut être utilisée pour ( v , w ) ! ! !c peut être utilisée pour ( v , w ) ! ! !
vv
ww
11Sans cSans c11 vv
22
cc 11
22
vv11
cc
XXXX
11 11
cc 11
vv
ww
11Sans cSans c11 vv
22
cc 11?? devientdevient
vv
ww
11Sans cSans c11 vv
22
cc 11
cc
XXXXcc 11
cc
21 mars 2006 Cours de graphes 5 - Intranet 134
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire ? ? ?Que faire ? ? ?
• Nous essayons deNous essayons de
– trouver une couleur « c » avec c trouver une couleur « c » avec c Abs( v ) Abs( v ) Abs( w ) !Abs( w ) !
– Nous utilisons cette couleur à la place de c ! ! !Nous utilisons cette couleur à la place de c ! ! ! – c peut être utilisée pour ( v , w ) ! ! !c peut être utilisée pour ( v , w ) ! ! !
vv
ww
11Sans cSans c11 vv
22
cc 11
22
vv11
cc
XXXX
11 11
cc 11
vv
ww
11Sans cSans c11 vv
22
cc 11?? devientdevient
vv
ww
11Sans cSans c11 vv
22
cc 11
cc
XXXXcc 11
cc
21 mars 2006 Cours de graphes 5 - Intranet 135
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire siQue faire si
– Abs( v ) Abs( w ) est vide ?Abs( v ) Abs( w ) est vide ?22
vvvv
ww
11Sans cSans c11 vv
22
cc 11??
21 mars 2006 Cours de graphes 5 - Intranet 136
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire siQue faire si
– Abs( v ) Abs( w ) est vide ?Abs( v ) Abs( w ) est vide ?– Soit c Soit c Abs( v ) ! Abs( v ) !
22
vv
22 22
vv
ww
11Sans cSans c11 vv
22
cc 11??
Sans cSans c22
21 mars 2006 Cours de graphes 5 - Intranet 137
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire siQue faire si
– Abs( v ) Abs( w ) est vide ?Abs( v ) Abs( w ) est vide ?– Soit c Soit c Abs( v ) ! Abs( v ) ! – Donc, c Donc, c Abs ( w ) ! Abs ( w ) ! – Il existe v tel que ( v , w )Il existe v tel que ( v , w ) ait la couleur c !ait la couleur c !
22
vv
22 22
vv
ww
11Sans cSans c11
22 //
33 33 22
vv22
cc 11??
Sans cSans c22
vv33cc 22
21 mars 2006 Cours de graphes 5 - Intranet 138
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire siQue faire si
– Abs( v ) Abs( w ) est vide ?Abs( v ) Abs( w ) est vide ?– Soit c Soit c Abs( v ) ! Abs( v ) ! – Donc, c Donc, c Abs ( w ) ! Abs ( w ) ! – Il existe v tel que ( v , w )Il existe v tel que ( v , w ) ait la couleur c !ait la couleur c !
22
vv
22 22
vv
ww
11Sans cSans c11
22 //
33 33 22
vv22
cc 11??
Sans cSans c22
vv33cc 22
Nous cherchons . . .Nous cherchons . . .
21 mars 2006 Cours de graphes 5 - Intranet 139
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Que faire siQue faire si
– Abs( v ) Abs( w ) est vide ?Abs( v ) Abs( w ) est vide ?– Soit c Soit c Abs( v ) ! Abs( v ) ! – Donc, c Donc, c Abs ( w ) ! Abs ( w ) ! – Il existe v tel que ( v , w )Il existe v tel que ( v , w ) ait la couleur c !ait la couleur c !
22
vv
22 22
vv
ww
11Sans cSans c11
22 //
33 33 22
vv22
cc 11??
Sans cSans c22
vv33cc 22
Nous cherchons . . .Nous cherchons . . .
21 mars 2006 Cours de graphes 5 - Intranet 140
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• La pire des situations . . .La pire des situations . . .
vv
ww
11Sans cSans c11
??
21 mars 2006 Cours de graphes 5 - Intranet 141
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• La pire des situations . . .La pire des situations . . .
vv
ww
11Sans cSans c11 vv
22
cc 11??
Sans cSans c22
21 mars 2006 Cours de graphes 5 - Intranet 142
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• La pire des situations . . .La pire des situations . . .
vv
ww
11Sans cSans c11 vv
22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
21 mars 2006 Cours de graphes 5 - Intranet 143
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• La pire des situations . . .La pire des situations . . .
vv
ww
11Sans cSans c11 vv
22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
21 mars 2006 Cours de graphes 5 - Intranet 144
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• La pire des situations . . .La pire des situations . . .
vv
ww
11Sans cSans c11 vv
22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
21 mars 2006 Cours de graphes 5 - Intranet 145
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• La pire des situations . . .La pire des situations . . .
vv
ww
11Sans cSans c11 vv
22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
21 mars 2006 Cours de graphes 5 - Intranet 146
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• La pire des situations . . .La pire des situations . . .
vv
ww
11Sans cSans c11 vv
22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
21 mars 2006 Cours de graphes 5 - Intranet 147
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
21 mars 2006 Cours de graphes 5 - Intranet 148
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
( C1 ) : 1 <= j <= h( C1 ) : 1 <= j <= h--1 :1 :
c c Abs( v ) et Abs( v ) et ( v , w ) de couleur c( v , w ) de couleur c
jj jj
jjj+1j+1
21 mars 2006 Cours de graphes 5 - Intranet 149
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
( C1 ) : 1 <= j <= h( C1 ) : 1 <= j <= h--1 :1 :
c c Abs( v ) et Abs( v ) et ( v , w ) de couleur c( v , w ) de couleur c
jj jj
jjj+1j+1
21 mars 2006 Cours de graphes 5 - Intranet 150
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
( C1 ) : 1 <= j <= h( C1 ) : 1 <= j <= h--1 :1 :
c c Abs( v ) et Abs( v ) et ( v , w ) de couleur c( v , w ) de couleur c
jj jj
jjj+1j+1
21 mars 2006 Cours de graphes 5 - Intranet 151
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
( C1 ) : 1 <= j <= h( C1 ) : 1 <= j <= h--1 :1 :
c c Abs( v ) et Abs( v ) et ( v , w ) de couleur c( v , w ) de couleur c
jj jj
jjj+1j+1
( C2 ) : 1 <= j <= h( C2 ) : 1 <= j <= h--1 :1 :
Abs( v ) Abs( w ) est videAbs( v ) Abs( w ) est vide jj
vv
21 mars 2006 Cours de graphes 5 - Intranet 152
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
( C1 ) : 1 <= j <= h( C1 ) : 1 <= j <= h--1 :1 :
c c Abs( v ) et Abs( v ) et ( v , w ) de couleur c( v , w ) de couleur c
jj jj
jjj+1j+1
( C2 ) : 1 <= j <= h( C2 ) : 1 <= j <= h--1 :1 :
Abs( v ) Abs( w ) est videAbs( v ) Abs( w ) est vide jj
vv
( C3 ) : 2 <= j <= h( C3 ) : 2 <= j <= h--1 :1 :
{ c , . . . , c } Abs( v ) est vide{ c , . . . , c } Abs( v ) est vide jj11 jj--11
vv
21 mars 2006 Cours de graphes 5 - Intranet 153
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
( C1 ) : 1 <= j <= h( C1 ) : 1 <= j <= h--1 :1 :
c c Abs( v ) et Abs( v ) et ( v , w ) de couleur c( v , w ) de couleur c
jj jj
jjj+1j+1
( C2 ) : 1 <= j <= h( C2 ) : 1 <= j <= h--1 :1 :
Abs( v ) Abs( w ) est videAbs( v ) Abs( w ) est vide jj
vv
( C3 ) : 2 <= j <= h( C3 ) : 2 <= j <= h--1 :1 :
{ c , . . . , c } Abs( v ) est vide{ c , . . . , c } Abs( v ) est vide jj11 jj--11
vv
21 mars 2006 Cours de graphes 5 - Intranet 154
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
( C1 ) : 1 <= j <= h( C1 ) : 1 <= j <= h--1 :1 :
c c Abs( v ) et Abs( v ) et ( v , w ) de couleur c( v , w ) de couleur c
jj jj
jjj+1j+1
( C2 ) : 1 <= j <= h( C2 ) : 1 <= j <= h--1 :1 :
Abs( v ) Abs( w ) est videAbs( v ) Abs( w ) est vide jj
vv
( C3 ) : 2 <= j <= h( C3 ) : 2 <= j <= h--1 :1 :
{ c , . . . , c } Abs( v ) est vide{ c , . . . , c } Abs( v ) est vide jj11 jj--11
vv
21 mars 2006 Cours de graphes 5 - Intranet 155
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
( C1 ) : 1 <= j <= h( C1 ) : 1 <= j <= h--1 :1 :
c c Abs( v ) et Abs( v ) et ( v , w ) de couleur c( v , w ) de couleur c
jj jj
jjj+1j+1
( C2 ) : 1 <= j <= h( C2 ) : 1 <= j <= h--1 :1 :
Abs( v ) Abs( w ) est videAbs( v ) Abs( w ) est vide jj
vv
( C3 ) : 2 <= j <= h( C3 ) : 2 <= j <= h--1 :1 :
{ c , . . . , c } Abs( v ) est vide{ c , . . . , c } Abs( v ) est vide jj11 jj--11
vv
21 mars 2006 Cours de graphes 5 - Intranet 156
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Pour v , . . . , v et c , . . . , c couleurs Pour v , . . . , v et c , . . . , c couleurs différentes :différentes :
vv
ww
11
Sans cSans c11vv22
cc 11??
Sans cSans c22
vv33cc 22
cc 11
Sans cSans c33
vv44
cc 33
cc 11
cc 22
11 11hh hh--11
( C1 ) : 1 <= j <= h( C1 ) : 1 <= j <= h--1 :1 :
c c Abs( v ) et Abs( v ) et ( v , w ) de couleur c( v , w ) de couleur c
jj jj
jjj+1j+1
( C2 ) : 1 <= j <= h( C2 ) : 1 <= j <= h--1 :1 :
Abs( v ) Abs( w ) est videAbs( v ) Abs( w ) est vide jj
vv
( C3 ) : 2 <= j <= h( C3 ) : 2 <= j <= h--1 :1 :
{ c , . . . , c } Abs( v ) est vide{ c , . . . , c } Abs( v ) est vide jj11 jj--11
vv
21 mars 2006 Cours de graphes 5 - Intranet 157
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 ) Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 )
et il existera v tel que . . .et il existera v tel que . . . hh
h+1h+1
21 mars 2006 Cours de graphes 5 - Intranet 158
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 ) Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 )
et il existera v tel que . . .et il existera v tel que . . .
• Or, l’arité des v est bornée et, tôt ou tard, ( C2 ) ou Or, l’arité des v est bornée et, tôt ou tard, ( C2 ) ou
( C3 ) ne seront plus vérifiées !( C3 ) ne seront plus vérifiées !
hh
h+1h+1
ii
21 mars 2006 Cours de graphes 5 - Intranet 159
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 ) Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 )
et il existera v tel que . . .et il existera v tel que . . .
• Or, l’arité des v est bornée et, tôt ou tard, ( C2 ) ou Or, l’arité des v est bornée et, tôt ou tard, ( C2 ) ou
( C3 ) ne seront plus vérifiées !( C3 ) ne seront plus vérifiées !
• Cas A, la négation de ( C2 ), facile :Cas A, la négation de ( C2 ), facile :
– Il existe c telle que c Il existe c telle que c Abs( v ) Abs( w ) Abs( v ) Abs( w )
hh
h+1h+1
ii
00 00 hh
vv
21 mars 2006 Cours de graphes 5 - Intranet 160
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 ) Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 )
et il existera v tel que . . .et il existera v tel que . . .
• Or, l’arité des v est bornée et, tôt ou tard, ( C2 ) ou Or, l’arité des v est bornée et, tôt ou tard, ( C2 ) ou
( C3 ) ne seront plus vérifiées !( C3 ) ne seront plus vérifiées !
• Cas A, la négation de ( C2 ), facile :Cas A, la négation de ( C2 ), facile :
– Il existe c telle que c Il existe c telle que c Abs( v ) Abs( w ) Abs( v ) Abs( w )
hh
h+1h+1
ii
00 00 hh
vv
vv
ww
11 vv22
cc 11??
vvhhcc hh--11
. . .. . .devientdevient
vv
ww
11 vv22
cc 11??
vvhhcc hh--11
. . .. . .
cc 00
21 mars 2006 Cours de graphes 5 - Intranet 161
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 ) Si v vérifie ( C2 ) et ( C3 ), nous aurons aussi ( C1 )
et il existera v tel que . . .et il existera v tel que . . .
• Or, l’arité des v est bornée et, tôt ou tard, ( C2 ) ou Or, l’arité des v est bornée et, tôt ou tard, ( C2 ) ou
( C3 ) ne seront plus vérifiées !( C3 ) ne seront plus vérifiées !
• Cas A, la négation de ( C2 ), facile :Cas A, la négation de ( C2 ), facile :
– Il existe c telle que c Il existe c telle que c Abs( v ) Abs( w ) Abs( v ) Abs( w )
hh
h+1h+1
ii
00 00 hh
vv
vv
ww
11 vv22
cc 11??
vvhhcc hh--11
. . .. . .devientdevient
vv
ww
11 vv22
cc 11??
vvhhcc hh--11
. . .. . .
cc 00c pour ( v , w ) et c pour ( v , w ) , 1 <= i < h.c pour ( v , w ) et c pour ( v , w ) , 1 <= i < h.
00 hh ii ii
21 mars 2006 Cours de graphes 5 - Intranet 162
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hhss
21 mars 2006 Cours de graphes 5 - Intranet 163
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
21 mars 2006 Cours de graphes 5 - Intranet 164
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
21 mars 2006 Cours de graphes 5 - Intranet 165
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
Soit P = { v , u , . . . , u } le chemin le plus longSoit P = { v , u , . . . , u } le chemin le plus long
constitué d’arêtes de couleurs c et c !constitué d’arêtes de couleurs c et c ! ss 11 tt
00 ss
21 mars 2006 Cours de graphes 5 - Intranet 166
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
Soit P = { v , u , . . . , u } le chemin le plus longSoit P = { v , u , . . . , u } le chemin le plus long
constitué d’arêtes de couleurs c et c !constitué d’arêtes de couleurs c et c ! ss 11 tt
00 ss
vvss
cc ss--11
21 mars 2006 Cours de graphes 5 - Intranet 167
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
Soit P = { v , u , . . . , u } le chemin le plus longSoit P = { v , u , . . . , u } le chemin le plus long
constitué d’arêtes de couleurs c et c !constitué d’arêtes de couleurs c et c ! ss 11 tt
00 ss
vvss cc
00
uu11 cc
ss
. . .. . . uutt
cc ss--11
21 mars 2006 Cours de graphes 5 - Intranet 168
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
P n’est pas vide, simple et de longueur finie ! ! ! P n’est pas vide, simple et de longueur finie ! ! !
vvss cc
00
uu11 cc
ss
. . .. . . uutt
cc ss--11
21 mars 2006 Cours de graphes 5 - Intranet 169
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
P n’est pas vide, simple et de longueur finie ! ! ! P n’est pas vide, simple et de longueur finie ! ! !
vvss cc
00
uu11 cc
ss
. . .. . . uutt
Ce n’est pas un cycle : v = u ! ! ! Ce n’est pas un cycle : v = u ! ! ! ttss //
Sans cSans css
cc ss--11
21 mars 2006 Cours de graphes 5 - Intranet 170
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
P n’est pas vide, simple et de longueur finie ! ! ! P n’est pas vide, simple et de longueur finie ! ! !
vvss cc
00
uu11 cc
ss
. . .. . . uutt
Ce n’est pas un cycle : v = u ! ! ! Ce n’est pas un cycle : v = u ! ! ! ttss //
Sans cSans css
w = u , . . . , w = u , car c w = u , . . . , w = u , car c Abs( w ) ! ! ! Abs( w ) ! ! ! 11// tt--11// 00
cc ss--11
21 mars 2006 Cours de graphes 5 - Intranet 171
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
P n’est pas vide, simple et de longueur finie ! ! ! P n’est pas vide, simple et de longueur finie ! ! !
vvss cc
00
uu11 cc
ss
. . .. . . uutt
Ce n’est pas un cycle : v = u ! ! ! Ce n’est pas un cycle : v = u ! ! ! ttss //
Sans cSans css
w = u , . . . , w = u , car c w = u , . . . , w = u , car c Abs( w ) ! ! ! Abs( w ) ! ! ! 11// tt--11// 00
cc ss--11
21 mars 2006 Cours de graphes 5 - Intranet 172
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
vvss cc
00
uu11 cc
ss
. . .. . . uutt
Sans cSans css
cc ss--11
( Cas ( Cas ) )
21 mars 2006 Cours de graphes 5 - Intranet 173
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
vvss cc
00
uu11 cc
ss
. . .. . . uutt
Sans cSans css
cc ss--11
( Cas ( Cas ) )
Notons que u peutNotons que u peutêtre égal à v .être égal à v .
tthh
21 mars 2006 Cours de graphes 5 - Intranet 174
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
vvss cc
00
uu11 cc
ss
. . .. . . uutt
Sans cSans css
cc ss--11
Echangeons les couleurs c et c le long de P !Echangeons les couleurs c et c le long de P !00 ss( Cas ( Cas ) )
Notons que u peutNotons que u peutêtre égal à v .être égal à v .
tthh
21 mars 2006 Cours de graphes 5 - Intranet 175
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
vvss cc
ss
uu11 cc
00
. . .. . . uutt
Sans cSans css
cc ss--11
Echangeons les couleurs c et c le long de P !Echangeons les couleurs c et c le long de P !00 ss( Cas ( Cas ) )
Notons que u peutNotons que u peutêtre égal à v .être égal à v .
tthh
21 mars 2006 Cours de graphes 5 - Intranet 176
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
vvss cc
ss
uu11 cc
00
. . .. . . uutt
Sans cSans css
cc ss--11
Echangeons les couleurs c et c le long de P !Echangeons les couleurs c et c le long de P !00 ss
Utilisons c pour ( v , w ) et décalons les autres !Utilisons c pour ( v , w ) et décalons les autres !00 ss
cc00
( Cas ( Cas ) )
Notons que u peutNotons que u peutêtre égal à v .être égal à v .
tthh
21 mars 2006 Cours de graphes 5 - Intranet 177
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
ww
11 vvs+1s+1
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
Sans cSans c00
vvss cc
00
uu11 cc
ss
. . .. . . uutt
Sans cSans css
cc ss--11
( Cas ( Cas ) )
21 mars 2006 Cours de graphes 5 - Intranet 178
v = uv = us+1 ts+1 t--11
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
u = wu = w
11
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
vvss cc
00
uu11
Sans cSans css
cc ss--11
( Cas ( Cas ) )
tt
. . .. . .
21 mars 2006 Cours de graphes 5 - Intranet 179
v = uv = us+1 ts+1 t--11
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
u = wu = w
11
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
vvss cc
00
uu11
Sans cSans css
cc ss--11
( Cas ( Cas ) )
tt
. . .. . .
Soit P’ = { v , u’ , . . . , u’ } le chemin le plusSoit P’ = { v , u’ , . . . , u’ } le chemin le plus
long constitué d’arêtes de couleurs c et c !long constitué d’arêtes de couleurs c et c ! hh 11 t’t’
00 ss
21 mars 2006 Cours de graphes 5 - Intranet 180
v = uv = us+1 ts+1 t--11
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
u = wu = w
11
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
vvss cc
00
uu11
Sans cSans css
cc ss--11
( Cas ( Cas ) )
tt
. . .. . .
Soit P’ = { v , u’ , . . . , u’ } le chemin le plusSoit P’ = { v , u’ , . . . , u’ } le chemin le plus
long constitué d’arêtes de couleurs c et c !long constitué d’arêtes de couleurs c et c ! hh 11 t’t’
00 ss
cc00
u’u’11 cc
ss
. . .. . . u’u’t’t’
21 mars 2006 Cours de graphes 5 - Intranet 181
v = uv = us+1 ts+1 t--11
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
u = wu = w
11
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .
Pas d’arêtePas d’arêterouge !rouge !
SoitSoitc c Abs( w ) Abs( w )00
vvss cc
00
uu11
Sans cSans css
cc ss--11
( Cas ( Cas ) )
tt
. . .. . .
Soit P’ = { v , u’ , . . . , u’ } le chemin le plusSoit P’ = { v , u’ , . . . , u’ } le chemin le plus
long constitué d’arêtes de couleurs c et c !long constitué d’arêtes de couleurs c et c ! hh 11 t’t’
00 ss
cc00
u’u’11 cc
ss
. . .. . . u’u’t’t’
Maintenant, w = u’ et nous avons le cas Maintenant, w = u’ et nous avons le cas ! !t’t’//
21 mars 2006 Cours de graphes 5 - Intranet 182
v = uv = us+1 ts+1 t--11
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
u = wu = w
11
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .SoitSoitc c Abs( w ) Abs( w )00
vvss cc
00
uu11
Sans cSans css
cc ss--11
( Cas ( Cas ) )
tt
. . .. . .
Soit P’ = { v , u’ , . . . , u’ } le chemin le plusSoit P’ = { v , u’ , . . . , u’ } le chemin le plus
long constitué d’arêtes de couleurs c et c !long constitué d’arêtes de couleurs c et c ! hh 11 t’t’
00 ss
ccss
u’u’11 cc
00
. . .. . . u’u’t’t’
Maintenant, w = u’ et nous avons le cas Maintenant, w = u’ et nous avons le cas ! !t’t’//
Pas d’arêtePas d’arêterouge !rouge !
21 mars 2006 Cours de graphes 5 - Intranet 183
v = uv = us+1 ts+1 t--11
Coloriage des arêtesColoriage des arêtes----------------------------------------------------------------------------------------------------------------------------------
• Cas B, la négation de ( C3 ), plus difficile :Cas B, la négation de ( C3 ), plus difficile :
– Il existe c , 1 <= s < hIl existe c , 1 <= s < h--1 , telle que c 1 , telle que c Abs( v ) Abs( v )ss hh
vv
u = wu = w
11
cc ss??
vvhhcc h-1h-1
. . .. . .
ss
. . .. . .SoitSoitc c Abs( w ) Abs( w )00
vvss cc
00
uu11
Sans cSans css
cc ss--11
( Cas ( Cas ) )
tt
. . .. . .
Soit P’ = { v , u’ , . . . , u’ } le chemin le plusSoit P’ = { v , u’ , . . . , u’ } le chemin le plus
long constitué d’arêtes de couleurs c et c !long constitué d’arêtes de couleurs c et c ! hh 11 t’t’
00 ss
ccss
u’u’11 cc
00
. . .. . . u’u’t’t’
Maintenant, w = u’ et nous avons le cas Maintenant, w = u’ et nous avons le cas ! !t’t’//
cc00
Pas d’arêtePas d’arêterouge !rouge !
21 mars 2006 Cours de graphes 5 - Intranet 184
SynthèseSynthèse----------------------------------------------------------------------------------------------------------------------------------
• Coloriage de graphes.Coloriage de graphes.
• Problème des 4 couleurs, graphes Problème des 4 couleurs, graphes planaires.planaires.
• Théorème de Vizing.Théorème de Vizing.
• Applications.Applications.
21 mars 2006 Cours de graphes 5 - Intranet 185
m E r C i e Tm E r C i e Tb O n N e J o U r N é b O n N e J o U r N é
E ! ! !E ! ! !
N ‘ o U b L i E z P a S N ‘ o U b L i E z P a S d Ed E
p R é P a R e R v O sp R é P a R e R v O sT D ! ! !T D ! ! !
Recommended