|
Taille: 3689
Commentaire:
|
Taille: 3868
Commentaire:
|
| Texte supprimé. | Texte ajouté. |
| Ligne 1: | Ligne 1: |
| 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. | = théoreme des quatre couleurs = |
| Ligne 3: | Ligne 3: |
| 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écemment (préciser ?) publiée par Georges Gonthier. | * 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. |
| Ligne 5: | Ligne 5: |
| 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é: | * 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écemment (préciser ?) publiée par Georges Gonthier. = théoreme 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é:[[BR]] |
| Ligne 7: | Ligne 11: |
| [[BR]] * 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. |
|
| Ligne 8: | Ligne 14: |
| 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. | * 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 10: | Ligne 16: |
| 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: | * '''[R1]''': Une frontière correspond a exactement deux pays. |
| Ligne 12: | Ligne 18: |
| '''[R1]''': Une frontière correspond a exactement deux pays. | * '''[R2]''': Une frontière est délimitée par au plus deux sommets. |
| Ligne 14: | Ligne 20: |
| '''[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. |
| Ligne 16: | Ligne 22: |
| '''[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 [[latex( $$ 2a$$ )]] mais d'après '''[R3]''' il est également plus grand que [[latex( $$ 3s$$ )]]. On en déduit: |
* 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 22: | Ligne 25: |
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 26: | Ligne 29: |
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 31: | Ligne 33: |
| [[BR]] * Mais alors la formule d'Euler-Poincaré donne: |
|
| Ligne 32: | Ligne 36: |
| Mais alors la formule d'Euler-Poincaré donne: | [[latex( $$f+s-1 \geq 3f $$)]][[BR]] * et enfin[[BR]] [[latex( $$2f+1 \leq s $$)]][[BR]] |
| Ligne 34: | Ligne 40: |
| [[latex( $$f+s-1 \geq 3f $$)]] et enfin [[latex( $$2f+1 \leq s $$)]] 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. |
* 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. |
théoreme des quatre couleurs
- 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.
- 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écemment (préciser ?) publiée par Georges Gonthier.
théoreme 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é:BR
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.
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:
[R1]: Une frontière correspond a 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 latex( $$ 2a$$ ) mais d'après [R3] il est également plus grand que latex( $$ 3s$$ ). On en déduit:BR
Et en combinant avec la formule d'Euler-Poincaré, on obtient: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
- Mais alors la formule d'Euler-Poincaré donne:
et enfinBR
- 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 pour obtenir la preuve de notre théorème. (Suite quand j'ai le temps).
Cette démonstration est directement inspirée du TIPE de Régis Demizieux et de Brice Febvre.
attachment:1.jpg
[http://icosaweb.ac-reunion.fr/Algorithmes/Graphes/Th4Couleurs/th4CouleursSVG.html faites le test]
voir aussi le Theoreme2Musiques