|
Taille: 7707
Commentaire: Orthographe
|
← Version 27 à la date du 2014-09-26 21:58:52 ⇥
Taille: 7570
Commentaire: OTL + attachment pour éviter les liens cassés + WTF !! C'est quoi ce contre-exemple bancal !
|
| Texte supprimé. | Texte ajouté. |
| Ligne 3: | Ligne 3: |
| * Quatre couleurs sont suffisantes pour colorier une carte, tout en satisfaisant le critere des frontieres, la seule condition imposée sur la carte étant que les pays doivent être connexes (en un seul morceau), sinon en découpant un pays en 4 morceau à l'intérieur d'un autre pays on aboutit à une contradiction manifeste. Précision de Gabounet, sur la notion de voisin: une frontière ne peut pas être un point! Par exemple l'arizona et le colorado ne sont pas voisins sur la carte des Etats-Unis (et on se donne donc le droit de les colorier avec la même couleur): | * Quatre couleurs sont suffisantes pour colorier une carte, tout en satisfaisant le critère des frontières, la seule condition imposée sur la carte étant que les pays doivent être connexes (en un seul morceau). Précision de Gabounet, sur la notion de voisin : une frontière ne peut pas être un point ! Par exemple l'Arizona et le Colorado ne sont pas voisins sur la carte des États-Unis (et on se donne donc le droit de les colorier avec la même couleur) : |
| Ligne 5: | Ligne 5: |
| {{http://www.uniterre.com/r_destinations/usa/images/cartes/carte_etats_unis.jpg}} | {{attachment:carte_etats_unis.jpg}} |
| Ligne 14: | Ligne 14: |
| * On peut par contre prouver un "Théroème des cinq couleurs" (plus faible, donc) par récurrence en s'appuyant sur la formule d'Euler-Poincaré. Cette dernière exprime que dans un graphe connexe (un ensemble de points et d'arêtes tel que parti d'un point il existe toujours un chemin menant à tout autre point du graphe) et planaire (i.e. qui est représentable sur un plan sans que deux arêtes ne se croisent [*]) on a l'égalité:<<BR>> | * On peut par contre prouver un "Théroème des cinq couleurs" (plus faible, donc) par récurrence en s'appuyant sur la formule d'Euler-Poincaré. Cette dernière exprime que dans un graphe connexe (un ensemble de points et d'arêtes tel que parti d'un point il existe toujours un chemin menant à tout autre point du graphe) et planaire (i.e. qui est représentable sur un plan sans que deux arêtes ne se croisent [*]) on a l'égalité :<<BR>> |
| Ligne 17: | Ligne 17: |
| Où <<Latex( $$ f$$ )>>, <<Latex( $$ a$$ )>> et <<Latex( $$ s$$ )>> représentent respectivement le nombre de faces, d'arêtes et de sommets du graphe. Généralement la formule s'écrit avec un <<Latex( $$ 2 $$ )>> dans le second membre, en comtant une face "extérieure en plus", mais cela ne change rien. Cette formule se démontre elle-même par récurrence. | Où <<Latex( $$ f$$ )>>, <<Latex( $$ a$$ )>> et <<Latex( $$ s$$ )>> représentent respectivement le nombre de faces, d'arêtes et de sommets du graphe. Généralement la formule s'écrit avec un <<Latex( $$ 2 $$ )>> dans le second membre, en comptant une face "extérieure en plus", mais cela ne change rien. Cette formule se démontre elle-même par récurrence. |
| Ligne 19: | Ligne 19: |
| [*]: Exercice: Tous les graphes ne sont pas forcément planaires ! Prouver grâce à la formule d'Euler-Poincaré que le graphe <<Latex( $$K_{3,3}$$ )>> est non planaire. Ce graphe est par définition consitué de 6 sommets de telle sorte que les 3 premiers soient chacun reliés au trois suivants. Généralement ce problème est présenté de la manière suivante: trois maisons sont alimentées par trois usines, en gaz, eau et éléctricité. Est-il possible d'alimenter (donc de joindre) les trois maisons sans qu'aucun tuyau ne se croise? La réponse est donc non! | [*] Exercice : Tous les graphes ne sont pas forcément planaires ! Prouver grâce à la formule d'Euler-Poincaré que le graphe <<Latex( $$K_{3,3}$$ )>> est non planaire. Ce graphe est par définition constitué de 6 sommets de telle sorte que les 3 premiers soient chacun reliés au trois suivants. Généralement ce problème est présenté de la manière suivante : trois maisons sont alimentées par trois usines, en gaz, eau et électricité. Est-il possible d'alimenter (donc de joindre) les trois maisons sans qu'aucun tuyau ne se croise ? La réponse est donc non ! |
| Ligne 21: | Ligne 21: |
| * Passons au théorème des cinq couleurs. Le cadre d'application de la formule précédente est le suivant: <<Latex( $$f$$ )>> représente le nombre de pays, <<Latex( $$a$$ )>> le nombre de frontières et <<Latex( $$s$$ )>> le nombre de "croisement" de frontières. Nous allons établir en premier lieu trois remarques: | * Passons au théorème des cinq couleurs. Le cadre d'application de la formule précédente est le suivant : <<Latex( $$f$$ )>> représente le nombre de pays, <<Latex( $$a$$ )>> le nombre de frontières et <<Latex( $$s$$ )>> le nombre de "croisement" de frontières. Nous allons établir en premier lieu trois remarques : |
| Ligne 23: | Ligne 23: |
| * '''[R1]''': Une frontière correspond à exactement deux pays. | * '''[R1]''' : Une frontière correspond à exactement deux pays. |
| Ligne 25: | Ligne 25: |
| * '''[R2]''': Une frontière est délimitée par au plus deux sommets. | * '''[R2]''' : Une frontière est délimitée par au plus deux sommets. |
| Ligne 27: | Ligne 27: |
| * '''[R3]''': Un sommet est le croisement d'au moins trois frontières. | * '''[R3]''' : Un sommet est le croisement d'au moins trois frontières. |
| Ligne 29: | Ligne 29: |
| * Estimons le nombre de couples (sommet,frontières). D'après '''[R2]''' ce nombre est plus petit que <<Latex( $$ 2a$$ )>> mais d'après '''[R3]''' il est également plus grand que <<Latex( $$ 3s$$ )>>. On en déduit:<<BR>> | * Estimons le nombre de couples (sommet,frontières). D'après '''[R2]''' ce nombre est plus petit que <<Latex( $$ 2a$$ )>> mais d'après '''[R3]''' il est également plus grand que <<Latex( $$ 3s$$ )>>. On en déduit :<<BR>> |
| Ligne 33: | Ligne 33: |
| * Et en combinant avec la formule d'Euler-Poincaré, on obtient:<<BR>> | * Et en combinant avec la formule d'Euler-Poincaré, on obtient :<<BR>> |
| Ligne 37: | Ligne 37: |
| * Montrons maintenant qu'il n'existe aucune carte (on suppose les cartes sans enclaves...) dont tous les pays possèdent au moins six voisins. Pour démontrer que quelque chose n'existe pas, on n'a pas vraiment le choix: on doit procéder par l'absurde. Soit donc une telle carte. Tous les pays ont au moins six voisins. Donc au moins six frontières. Une même frontière appartenant par définition à deux pays, on aurait: <<BR>> | * Montrons maintenant qu'il n'existe aucune carte (on suppose les cartes sans enclaves…) dont tous les pays possèdent au moins six voisins. Pour démontrer que quelque chose n'existe pas, on n'a pas vraiment le choix : on doit procéder par l'absurde. Soit donc une telle carte. Tous les pays ont au moins six voisins. Donc au moins six frontières. Une même frontière appartenant par définition à deux pays, on aurait : <<BR>> |
| Ligne 41: | Ligne 41: |
| * Mais alors la formule d'Euler-Poincaré donne: | * Mais alors la formule d'Euler-Poincaré donne : |
| Ligne 51: | Ligne 51: |
| * Initialisation: il est bien évident qu'avec cinq couleurs on peut colorier ''UN'' pays! * Supposons que l'on sache, avec cinq couleurs, colorier toute carte possédant ''N'' pays et soit une carte possédant ''N+1'' pays. D'après ce que nous avons démontré précédemment, nous disposons d'un pays (que nous appelerons Rowdy) possédant au plus cinq frontières. On supprime momentanément une frontière de Rowdy. On obtient alors une carte de ''N'' pays, que l'on sait donc colorier avec nos cinq couleurs par hypothèse de récurrence. Une fois le coloriage réalisé, rétablissons la frontière de Rowdy, en lui enlevant la couleur qu'on lui avait attribué (mais en la laissant sur le voisin avec qui on l'avait fusioné). Nous avons donc presque réussi à colorier notre carte de ''N+1'' pays: il ne reste qu'à attribuer une couleur à Rowdy qui n'a toujours au plus que cinq voisins. Trois cas sont alors possibles: |
* Initialisation : il est bien évident qu'avec cinq couleurs on peut colorier ''UN'' pays ! * Supposons que l'on sache, avec cinq couleurs, colorier toute carte possédant ''N'' pays et soit une carte possédant ''N+1'' pays. D'après ce que nous avons démontré précédemment, nous disposons d'un pays (que nous appellerons Rowdy) possédant au plus cinq frontières. On supprime momentanément une frontière de Rowdy. On obtient alors une carte de ''N'' pays, que l'on sait donc colorier avec nos cinq couleurs par hypothèse de récurrence. Une fois le coloriage réalisé, rétablissons la frontière de Rowdy, en lui enlevant la couleur qu'on lui avait attribué (mais en la laissant sur le voisin avec qui on l'avait fusionné). Nous avons donc presque réussi à colorier notre carte de ''N+1'' pays : il ne reste qu'à attribuer une couleur à Rowdy qui n'a toujours au plus que cinq voisins. Trois cas sont alors possibles : |
| Ligne 54: | Ligne 54: |
| 2. Rowdy a cinq voisins mais deux d'entre eux sont coloriés de la même couleur: on a donc toujours une couleur de disponible et le tour est joué. 3. Reste le cas (et c'est le plus difficile) ou Rowdy a cinq voisins qui ont tous des couleurs différentes. Nous appelerons ses voisins Foustala, Regala, Rafik, Milouse et Ayman, coloriés de la manière suivante: |
2. Rowdy a cinq voisins mais deux d'entre eux sont coloriés de la même couleur : on a donc toujours une couleur de disponible et le tour est joué. 3. Reste le cas (et c'est le plus difficile) ou Rowdy a cinq voisins qui ont tous des couleurs différentes. Nous appellerons ses voisins Foustala, Regala, Rafik, Milouse et Ayman. ##, coloriés de la manière suivante : |
| Ligne 57: | Ligne 58: |
| {{http://perso.crans.org/~moussa/Image1.jpg}} | ##{{http://perso.crans.org/~moussa/Image1.jpg}} |
| Ligne 59: | Ligne 60: |
| Appelons '''chaîne de pays''' une suite de pays se touchant par au moins l'une de leur frontières. Le cercle formé de Foustala, Regala, Rafik, Milouse et Ayman est par exemple une chaîne de pays. On a alors une dernière fois deux cas possibles: | Appelons '''chaîne de pays''' une suite de pays se touchant par au moins l'une de leur frontières. Le cercle formé de Foustala, Regala, Rafik, Milouse et Ayman est par exemple une chaîne de pays. On a alors une dernière fois deux cas possibles : |
| Ligne 61: | Ligne 62: |
| * Il n'existe pas de chaîne de pays coloriée exclusivement en bleu et en noir (et donc forcément en alternance car jusque là notre carte est ''bien'' coloriée, au sens où deux voisins n'ont pas la même couleur) reliant Foustala et Rafik. Alors partis de Foustala il suffit de le colorier en noir et de colorier ses voisins noirs en bleu, d'inverser ces deux couleurs de proche en proche et on s'est ainsi ramené au cas 1. traité précédement. * Il existe une telle chaîne, mais alors il ne peut en exister de similaire reliant Regala à Milouse (pour les puristes qui voudraient une preuve rigoureuse de ce résultat intuitif, c'est une raison de connexité: on peut construire des chemins continus passant par les deux chaînes et invoquer le théorème du passage de douanes). On s'est donc ramené au cas précédent et le coloriage peut-être réalisé. |
* Il n'existe pas de chaîne de pays coloriée exclusivement en bleu et en noir (et donc forcément en alternance car jusque là notre carte est ''bien'' coloriée, au sens où deux voisins n'ont pas la même couleur) reliant Foustala et Rafik. Alors partis de Foustala il suffit de le colorier en noir et de colorier ses voisins noirs en bleu, d'inverser ces deux couleurs de proche en proche et on s'est ainsi ramené au cas 1. traité précédemment. * Il existe une telle chaîne, mais alors il ne peut en exister de similaire reliant Regala à Milouse (pour les puristes qui voudraient une preuve rigoureuse de ce résultat intuitif, c'est une raison de connexité : on peut construire des chemins continus passant par les deux chaînes et invoquer le théorème du passage de douanes). On s'est donc ramené au cas précédent et le coloriage peut-être réalisé. |
| Ligne 64: | Ligne 65: |
| On conclut finalement par récurrence pour obtenir le: | On conclut finalement par récurrence pour obtenir le : |
| Ligne 66: | Ligne 67: |
| '''Théorème (dit "des cinq couleurs")''': Cinq couleurs différentes sont suffisantes pour colorier n'importe quelle carte, sans que deux pays voisins se partagent une même couleur. |
'''Théorème (dit "des cinq couleurs")''' : Cinq couleurs différentes sont suffisantes pour colorier n'importe quelle carte, sans que deux pays voisins se partagent une même couleur. |
| Ligne 79: | Ligne 71: |
Théorème des quatre couleurs
- Quatre couleurs sont suffisantes pour colorier une carte, tout en satisfaisant le critère des frontières, la seule condition imposée sur la carte étant que les pays doivent être connexes (en un seul morceau). Précision de Gabounet, sur la notion de voisin : une frontière ne peut pas être un point ! Par exemple l'Arizona et le Colorado ne sont pas voisins sur la carte des États-Unis (et on se donne donc le droit de les colorier avec la même couleur) :
- Ce résultat est connu en mathématiques sous le nom de "Théorème des quatre couleurs", après être resté au stade de conjecture pendant des décennies il fut prouvé en 1976 par Appel et Haken. La démonstration fait appel à des procédés combinatoires complexes et repose au final sur un calcul d'ordinateur. Une preuve en Coq (langage qui permet la description formelle d'une preuve dans le but de sa vérification automatique par un ordinateur) a été réalisée en 2004 par Georges Gonthier et Benjamin Werner.
Théorème des cinq couleurs
On peut par contre prouver un "Théroème des cinq couleurs" (plus faible, donc) par récurrence en s'appuyant sur la formule d'Euler-Poincaré. Cette dernière exprime que dans un graphe connexe (un ensemble de points et d'arêtes tel que parti d'un point il existe toujours un chemin menant à tout autre point du graphe) et planaire (i.e. qui est représentable sur un plan sans que deux arêtes ne se croisent [*]) on a l'égalité :
Où 
, 
et 
représentent respectivement le nombre de faces, d'arêtes et de sommets du graphe. Généralement la formule s'écrit avec un 
dans le second membre, en comptant une face "extérieure en plus", mais cela ne change rien. Cette formule se démontre elle-même par récurrence.
[*] Exercice : Tous les graphes ne sont pas forcément planaires ! Prouver grâce à la formule d'Euler-Poincaré que le graphe 
est non planaire. Ce graphe est par définition constitué de 6 sommets de telle sorte que les 3 premiers soient chacun reliés au trois suivants. Généralement ce problème est présenté de la manière suivante : trois maisons sont alimentées par trois usines, en gaz, eau et électricité. Est-il possible d'alimenter (donc de joindre) les trois maisons sans qu'aucun tuyau ne se croise ? La réponse est donc non !
Passons au théorème des cinq couleurs. Le cadre d'application de la formule précédente est le suivant :
représente le nombre de pays, 
le nombre de frontières et 
le nombre de "croisement" de frontières. Nous allons établir en premier lieu trois remarques : [R1] : Une frontière correspond à exactement deux pays.
[R2] : Une frontière est délimitée par au plus deux sommets.
[R3] : Un sommet est le croisement d'au moins trois frontières.
Estimons le nombre de couples (sommet,frontières). D'après [R2] ce nombre est plus petit que
mais d'après [R3] il est également plus grand que 
. On en déduit :
Et en combinant avec la formule d'Euler-Poincaré, on obtient :
Montrons maintenant qu'il n'existe aucune carte (on suppose les cartes sans enclaves…) dont tous les pays possèdent au moins six voisins. Pour démontrer que quelque chose n'existe pas, on n'a pas vraiment le choix : on doit procéder par l'absurde. Soit donc une telle carte. Tous les pays ont au moins six voisins. Donc au moins six frontières. Une même frontière appartenant par définition à deux pays, on aurait :
- Mais alors la formule d'Euler-Poincaré donne :
et enfin
- La contradiction est manifeste. On a donc montré que dans toute carte il existe au moins un pays qui ne possède pas plus de cinq voisins.
Il nous reste à récurrer sur le nombre de pays pour obtenir la preuve de notre théorème.
Initialisation : il est bien évident qu'avec cinq couleurs on peut colorier UN pays !
Supposons que l'on sache, avec cinq couleurs, colorier toute carte possédant N pays et soit une carte possédant N+1 pays. D'après ce que nous avons démontré précédemment, nous disposons d'un pays (que nous appellerons Rowdy) possédant au plus cinq frontières. On supprime momentanément une frontière de Rowdy. On obtient alors une carte de N pays, que l'on sait donc colorier avec nos cinq couleurs par hypothèse de récurrence. Une fois le coloriage réalisé, rétablissons la frontière de Rowdy, en lui enlevant la couleur qu'on lui avait attribué (mais en la laissant sur le voisin avec qui on l'avait fusionné). Nous avons donc presque réussi à colorier notre carte de N+1 pays : il ne reste qu'à attribuer une couleur à Rowdy qui n'a toujours au plus que cinq voisins. Trois cas sont alors possibles :
- Rowdy a (strictement) moins de cinq voisins. Il reste donc une couleur de disponible et la carte est coloriée.
- Rowdy a cinq voisins mais deux d'entre eux sont coloriés de la même couleur : on a donc toujours une couleur de disponible et le tour est joué.
- Reste le cas (et c'est le plus difficile) ou Rowdy a cinq voisins qui ont tous des couleurs différentes. Nous appellerons ses voisins Foustala, Regala, Rafik, Milouse et Ayman.
Appelons chaîne de pays une suite de pays se touchant par au moins l'une de leur frontières. Le cercle formé de Foustala, Regala, Rafik, Milouse et Ayman est par exemple une chaîne de pays. On a alors une dernière fois deux cas possibles :
Il n'existe pas de chaîne de pays coloriée exclusivement en bleu et en noir (et donc forcément en alternance car jusque là notre carte est bien coloriée, au sens où deux voisins n'ont pas la même couleur) reliant Foustala et Rafik. Alors partis de Foustala il suffit de le colorier en noir et de colorier ses voisins noirs en bleu, d'inverser ces deux couleurs de proche en proche et on s'est ainsi ramené au cas 1. traité précédemment.
- Il existe une telle chaîne, mais alors il ne peut en exister de similaire reliant Regala à Milouse (pour les puristes qui voudraient une preuve rigoureuse de ce résultat intuitif, c'est une raison de connexité : on peut construire des chemins continus passant par les deux chaînes et invoquer le théorème du passage de douanes). On s'est donc ramené au cas précédent et le coloriage peut-être réalisé.
On conclut finalement par récurrence pour obtenir le :
Théorème (dit "des cinq couleurs") : Cinq couleurs différentes sont suffisantes pour colorier n'importe quelle carte, sans que deux pays voisins se partagent une même couleur.
Cette démonstration est directement inspirée du TIPE de Régis Demizieux et de Brice Febvre.
voir aussi le Theoreme2Musiques