Graphe biparti
dans Les-mathématiques
Bonjour
Comment voir simplement que le graphe biparti complet K(3,3) n'est pas planaire?
(Problème des 3 villas et des conduites de gaz, d'eau et d'électricité)
Merci
Comment voir simplement que le graphe biparti complet K(3,3) n'est pas planaire?
(Problème des 3 villas et des conduites de gaz, d'eau et d'électricité)
Merci
Réponses
-
Bonjour
Je crois qu'il faut raisonner par l'absurde et dire que si K(3,3) était planaire alors on pourrait lui appliquer la formule d' Euler S-A+F=2. Il faut peut-être aussi regarder le degré des sommets. (Je sais , c'est vague...)
C'est fait dans un livre (très intéressant par ailleurs) qui s'appelle "Raisonnements divins". -
Dans le livre Graphs and Applications : An introductory Approach de Joan M. Aldous et Robin J.Wilson (springer) on propose la solution suivante :
Le graphe est représenté comme dans le premier fichier joint.
Le raisonnement est le suivant :
$K_{3,3}$ possède un cycle de longueur $6$ (le cycle $1-6-2-5-3-4-1$). Dans un plan on peut dessiner ce cycle comme un hexagone. Il manque alors $3$ arêtes : $1-5$, $2-4$ et $3-6$.
On ne peut tracer qu'une seule arête à l'intérieur de l'hexagone, à partir de $2$ elles se croisent (voir le second fichier) . On remarque la même chose si on décide de tracer les arêtes à l'extérieur de l'hexagone (faire le dessin).
Par conséquent il est impossible de tracer les trois arêtes manquantes sans créer de croisement et le graphe n'est donc pas planaire.
Je ne sais pas si on peut formaliser plus mais c'est bien l'idée. -
Une façon que je trouve visuellement satisfaisante mais pas très propre théoriquement . On considère cinq des sommets $a_1,a_2,b_1,b_2,b_3$ et les arêtes reliant ces sommets . On a nécessairement l'une des trois conditions qui est vérifiée :
$b_1$ est à l'intérieur du cycle $a_1b_2a_2b_3$
$b_2$ est à l'intérieur du cycle $a_1b_1a_2b_3$
$b_3$ est à l'intérieur du cycle $a_1b_1a_2b_2$
Si par exemple la deuxième condition est vérifiée ( voir figure jointe ) . Alors quelle que soit la position de $a_3$ , il ne peut être relié à l'un des $b_i$ sans traverser une frontière :
1°) si $a_3$ est dans la région 1 , il ne peut être relié à $b_3$ .
2°) si $a_3$ est dans la région 2 , il ne peut être relié à $b_1$ .
3°) si $a_3$ est dans la région 3 , il ne peut être relié à $b_2$ .
Domi -
Bonsoir
Voici quelque chose de plus précis que ce que j'ai écrit hier :
Supposons K(3,3) planaire. D'après la formule d'Euler S-A+F=2, donc F=5.
Il y a en moyenne 2A/F=3,6 côtés par face, donc il existe une face ayant au plus 3 côtés. On devrait donc trouver soit une boucle en un sommet (impossible), soit 2 arêtes reliant 2 mêmes sommets (impossible), soit un triangle (impossible).
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 63 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 313 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres