Théorème des graphes

Tout d'abord bonjour à tous,

Voila j'ai un problème très compliqué à résoudre que je vous propose de regarder attentivement.

Problème :

Il y a 3 maisons A, B et C, chacunes d'entre elles doivent être allimentées en eau, gaz et électricité.

voici le schéma (les points peuvent être placés dans n'importe quel ordre et endroit)



O : eau
G : gaz
E : électricité

Pour les allimenter il faut faire des canalisations d'eau, de gaz et d'électricité pour chacunes d'entre elles et chaques canalisations ne doivent pas se croiser. Elles peuvent contourner les points dans tout les sens. (elles doivent en revanche toujours rester sur la feuille)

Généralement on arrive à la fin mais il manque toujours une canalisation...

Mais j'ai appris que par le théorème des graphes il était possible de réaliser cette énigme. j'espère que vous pourez m'aider car je ne suis qu'en 1ère année d'IUT et j'ai tenté de comprendre le théorème des graphes sans y parvenir vraiment....
Je vous remercie d'avance d'avoir jeté un oeil et vous souhaite bonne chance.

(si vous trouvez que mon énoncer n'est pas assez clair n'ésitez pas à me demander)

Nanoriel.

C'est un probleme interessant et je vais essayer d'y reflechir. Par contre, je ne suis pas specialiste des graphes, pourrais-tu rappeler ce que dit le theoreme des graphes.

Euh et bien si j'avais compris le théorème j'aurai pu te l'énnoncer mais à mon avis si tu veut pas te suicider en lisant ma version va sur un site qui te propose des cours rapide pour t'informer.
Voila dsl de ne pas pouvoir t'aider mieux que çà ...

Ok, je vais essayer de voir ça et je te tiens au courant.

J'ai cherche un peu sur le net et je n'ai rien trouve qui portait le nom de "theoreme des graphes". Peut-etre est-il plus connu sous un autre nom, comme par exemple celui du mathematicien qui la' demontre.
Je vais continuer a me renseigner.

Ok mais j'ai une copine qui a regardé aussi et elle m'a dit que se serai impossible alors ne te tue pas trop à la tâche car je ne sais plus quoi penser ^^ essaye "théorie des graphes" au cas où car c'est une des ses appélation. Voilà je vais te chercher le nom du mec pour te le dire.

J'ai cherche un peu "theorie des graphes", mais je n'ai vu aucun resultat qui pourrait resoudre ce pb.
En tout cas, le probleme est interessant et me semble bien difficile a resoudre quoi que tres simple a enoncer (comme c'est parfois le cas en maths).

Alors je viens d'apprendre par une amie plutôt douée en maths qu'en faite cette énigme n'avais pas de solution, et qu'en faite le truc c'était d'être capable de faire la démonstration qui prouvaie que c'était impossible....
Désolé de t'avoir fait chercher pour rien mais bon si tu veut il te reste à prouver que c'est impossible.
Voila bonne chance^^

Ok, merci pour ces precisions.

Ah je le connaissais ce problème

Intéressant ce problème !
Pour info, il existe une solution si on se place dans un tore (un donut !), mais aucune solution sur une surface plane

J'ai trouvé sur le net une petite démonstration de ce résultat à l'adresse : http://mathforum.org/dr.math/faq/faq.3utilities.html

En voici un petit résumé simpliste :
On veut montrer que l'on ne peut pas trouver un graphe solution sans croisement.
On trace alors des connexions entre les trois chaque maisons et deux bornes, de facon à ce qu'il n'y ait pas de croisement
Les segments ainsi tracés délimitent une courbe de Jordan (courbe fermée simple). Le théorème de Jordan assure alors qu'il existe un intérieur et un extérieur à la 'surface' délimitée par cette courbe.
Comme il nous reste trois courbe à tracer, on devra nécessairement en tracer deux à l'intérieur ou deux à l'extérieur de la courbe de Jordan. Ainsi, on 'voit' que deux courbes vont se croiser.

Ca n'est pas très formel, mais ca dépasse largement mes connaissances !

Merci pour le lien pihro.