Planaires ou pas...
Au pays des graphes planaires, on ne veut ni ponts, ni tunnels. On vous y a demandé une étude conjecturale...
Dans la province d'Alpha, on veut relier les quatre villes principales les unes aux autres deux à deux par des routes. Pensez-vous que c'est possible ?
Dans la province de Bêta, on veut relier les cinq villes principales les unes aux autres deux à deux par des routes. Pensez-vous que c'est possible ?
Dans la province de Gamma, on veut relier les cinq villes principales les unes aux autres deux à deux par des routes, à l'exception notable de deux d'entre elles. Pensez-vous que c'est possible ?
Dans la province de Delta, les trois villes principales sont reliées entre elles par air. Les trois villes moyennes aussi. Pensez-vous que l'on peut relier par route chacune des trois villes principales à chacune des trois villes moyennes ?
La relation d'Euler
Tous les graphes considérés par la suite seront "d'un seul tenant" et auront des faces d'au moins trois arêtes. Un graphe est dit "planaire" si on peut le dessiner en déplaçant ses sommets et en déformant ses arêtes (sans les rompre) sans que ses arêtes se croisent.
Donnez un exemple d'un graphe planaire et d'un graphe que vous pensez non-planaire.
À partir de quelques exemples de graphes planaires, remplissez un tableau où vous placerez les nombres s de sommets, a d'arêtes, et f de faces (où vous compterez aussi la face extérieure "infinie" du graphe). Il existe une relation simple entre ces trois nombres. Conjecturez ce que l'on nomme "la relation d'Euler".
Cette relation s'applique aussi à certains polyèdres. Fournissez un exemple, et faites comprendre pourquoi la relation d'Euler s'applique aux polyèdres convexes.
Et d'un
Prouvez que, pour presque (à préciser) tout graphe planaire,
. Vous pouvez pour cela, par exemple, compter les liens face-arête.
En déduire que
.
Démontrer alors que l'un des graphes du paragraphe 1 est non-planaire.
Et de deux
Prouvez que, si un graphe planaire n'a que des faces d'au moins quatre arêtes,
.
En déduire que
.
Démontrer alors qu'un autre des graphes du paragraphe 1 est non-planaire.
C'est complet
On dit d'un graphe qu'il est complet quand chacun de ses sommets y est relié à tous les autres. Démontrez qu'il n'y a pas de graphe complet planaire à plus de quatre sommets.
En guise de conclusion
Le mathématicien Kuratowski a prouvé en 1930 qu'un graphe (d'un seul tenant) était planaire si, et seulement si, il ne "contenait" ni l'un ni l'autre des deux graphes démontrés précédemment. La démonstration est trop compliquée pour vous être proposée, mais ce théorème vous permettra de mettre au point de jolis casse-tête...
