Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
301 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Graphe biparti

Envoyé par Bob25 
Bob25
Graphe biparti
il y a treize années
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
Re: Graphe biparti
il y a treize années
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".
Re: Graphe biparti
il y a treize années
avatar
<latex> 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.
Re: Graphe biparti
il y a treize années
avatar
<latex> 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
Re: Graphe biparti
il y a treize années
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).
Désolé, vous n'avez pas la permission d'envoyer ou de répondre dans ce forum.
Liste des forums - Statistiques du forum

Total
Discussions: 137 936, Messages: 1 337 760, Utilisateurs: 24 640.
Notre dernier utilisateur inscrit edcouturier.


Ce forum
Discussions: 37 176, Messages: 277 915.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page