Bonjour à tous et à toutes,
je viens vous exposer le problème que m'a posé un ami et sur lequel je réfléchi depuis maintenant plusieurs jours. J'ai entendu parler de la topologie et des graphes mais je n'ai pas forcément bien compris comment les utiliser.

Voici donc ce problème :

Démontrer si oui ou non il est possible de tracer les chemins tel que :
- A soit relié à 1, 2 et 3
- B soit relié à 1, 2 et 3
- C soit relié à 1, 2 et 3
sans que les chemins du graphes se croisent.
Voici donc un petit schéma :

____________1____________2____________3



____________A____________B____________C

(P.S. : ne vous souciez pas des lignes blanches entre les lettres et les chiffres, c'est seulement pour avoir un espace assez grand .)

En vous remerciant d'avance

Kanaal

Regarde les graphs et principalement les graphes planaires (graphe qui peut etre dessine sans croiser d'arrete).

Pour trouver ta reponse tu peux regarde le theoreme de Kuratouski.
sinon un graphe planaire valide la formule suivante :
<math>\(|E|<= \frac{g}{(g-2)}(|V| - 2)\)</math>
ou :
|E| nombre d'arrete
|V| nombre de sommet
g la maille (la longueur du plus petit cycle)

Il y a egalement une propriete interessant : Un graphe n'est pas planaire si il contient le graphe que tu viens de donner ou le graphe complet d'ordre 5.