[GRAPHE] Démonstration d'un problème demandé!

[moutonjr]

Bonjour.
Je suis en Terminale S, et j'ai entendu un problème qui m'a tout l'air d'être résolvable à l'aide de graphes. Pourrait-on m'expliquer?

Il existe 3 maisons, de nom très originaux 1, 2 et ...3.
Elles doivent-êtres connectées à un réseau d'électricité, de gaz et d'eau. Bien entendu, ces canalisations sont coplanaires, sinon...
Ptit dessin sur paint pour continuer...



Peut-on les raccorder toutes aux 3 réseaux sans qu'aucune canalisation ne se touche (y'a de l'eau dans le gaz et de l'électricité dans l'air si vous voyez ce que je veux dire...)? (on peut modifier tous les points de position)

La réponse est instinctivement non, mais comment le prouver? peut-être par la théorie des graphes, on pourrait substituer l'image à un graphe S{1,2,3, EDF, GDF, Eau} avec pour arêtes orientées {EDF, 1}{GDF,1}{Eau,1}{EDF, 2}{GDF,2}{Eau,2}{EDF, 3}{GDF,3}{Eau,3} et il faudrait démontrer qu'au moins deux de ces arêtes de soupent si S est uniplanaire, mais comment??
Pourrait-on trouver une solution??
Merci d'avance!

[Argentoratum]

Il faut effectivement representer cela par un graphe. Ce graphe n'etant pas planaire, il n'y a pas de solution.

[moutonjr]

Oui mais pourquoi n'y a-t-il pas de solution? c'est là que je bloque...

[Imod]

n'est pas planaire , ça doit être du cours . Sinon je te proposerai une démonstration .
Une petite remarque , si on n'est pas limité en fil et en tuyauterie en s'autorisant à faire le tour de la terre les branchements sont possibles sans croisement :ptdr:

Imod

[moutonjr]

Euuh je suis en terminale S^^

[ThSQ]

n'est pas planaire , ça doit être du cours . Sinon je te proposerai une démonstration .
Une petite remarque , si on n'est pas limité en fil et en tuyauterie en s'autorisant à faire le tour de la terre les branchements sont possibles sans croisement :ptdr:

Imod

Sur un ruban de Moebius c'est possible aussi :ptdr:

[Imod]

Euuh je suis en terminale S^^

Dans ce cas évite de poster dans le supérieur :zen:
Je te donnerais une solution avec dessins dans la soirée ( plutôt la nuit ) si personne d'autre ne s'y colle .

Imod

[moutonjr]

Dans ce cas évite de poster dans le supérieur :zen:
Imod

hé hé hé, je pense que c'est moins à mon programme :ptdr:

[Imod]

Une petite explication , claire , j'espère !



On suppose que les branchements sont possibles sans croisement . On note 1 , 2 , 3 les maisons et E , G , W l'eau , le gaz et l'électricité . 1G2E forme une boucle ( en théorie des graphe on dit un cycle ) et en changeant au besoin les rôles de EGW , on peut supposer que W est dans la boucle ( voir figure ) . Maintenant où se situe la maison 3 ?

a) Dans le triangle de gauche : elle n'aura pas l'eau .
b) Dans le triangle de droite : elle n'aura pas le gaz .
c) A l'extérieur du losange : elle n'aura pas l'electricité .

Contradiction .

Imod