cinq pays et frontières

Édition du: 28/03/2023

INDEX Graphe Topologie Dénombrement Logique	GRAPHES
	Graphes – Introduction	Arbres – Introduction	Chemin le plus court
	Chemin eulérien	Cinq pays	Voyageur de commerce
	Graphe planaire	Trois maisons	Multiple et diviseurs
	Graphe de Delaunay	Petit monde	Nombres de Delannoy
	Ivrogne	Colonies de fourmis

Faites un double-clic pour un retour en haut de page

CINQ PAYS

Comment représenter cinq pays sur une carte, chacun ayant des frontières communes avec les quatre autres?

Sommaire de cette page

>>> Problème des cinq pays

Débutants

Dénombrement

Glossaire

Combinatoire

Problème des cinq pays
Construire une carte avec cinq pays ayant chacun une frontière commune avec tous les autres est impossible. C'est un problème du même type que colorier une carte géographique avec le minimum de couleurs.	Le théorème des quatre couleurs est démontré (certes difficilement et avec ordinateur). Il est toujours possible de colorier une carte avec quatre couleurs seulement. Si un cinquième pays avait des frontières communes avec les quatre autres, il faudrait une cinquième couleur pour le colorier. Ce qui est contraire au théorème.
Une fois quatre pays dessinés avec frontières communes, en placer un cinquième nécessite de traverser l'un des quatre. (Ici, le pays 5, pour avoir une frontière commune avec le pays 3, doit passer à travers le pays 4).
Problème du même type que celui des graphes planaires: les arcs du graphe ne doivent pas se croiser. Totalement réalisable avec les quatre sommets du bas (réseau en bleu), mais impossible avec l'arrivée d'un cinquième (arcs en rouge). Le graphe K₅, comme le K_3,3ne sont pas coplanaires. Le K_3,3consiste à vouloir distribuer l'eau , le gaz et l'électricité dans trois maisons sans que les réseaux se croisent. Le graphe ci-contre est la transcription de la carte ci-dessus. Chaque sommet représente un pays et ses jonctions vers les autres pays. Chacun doit être relié aux quatre autres. C'est impossible.