Bonjour à tous,
J'ai un problème sur un petit exo sur la théorie des graphes...
Voici la question:
Si un graphe compte s sommets, a arêtes et n composantes connexes, en
combien de régions divise-t-il le plan?
Je ne sais pas par où commencer pour faire une explication cohérente...
Merci à tous
Peut-être que je comprends mal la question, mais la réponse me semble dépendre de la représentation du graphe dans le plan. Par exemple, pour s=4, a=4 et n=1, si les sommets A, B, C, D forment un quadrilatère et si les arêtes sont les quatre côtés de ce quadrilatère, le plan est partagé en deux régions si le quadrilétère est non croisé, mais en trois régions s’il est croisé. Du coup, pas d’espoir d’avoir une formule générale en fonction de s, a et n…
pour que la question ait un sens, il faut supposer le graphe planaire. Pour une composante connexe, si f est le nombre de régions (y compris la région non bornée "extérieure") on a la relation s-a+f=2 (exercice). Si tu as plusieurs composantes connexes, tu as la même relation pour chacune, mais bien entendu la face extérieure est la même, et donc on a s-a+f = 2 - (n-1)
En effet, je pensais aussi qu’il manquait l’hypothèse de planarité (et cherchais à mettre en évidence ce manque avec mon exemple) ; attendons confirmation de la part de l’auteur du fil…
En effet, il sdoit s'agir d'un graphe planaire, l'exo est dans cette section la...
Merci a tous
au fait j'ai supposé que toutes les composantes connexes partageaient la même face non bornée, mais ce n'est pas vrai : penser à deux triangles emboîtés. Mais le résultat demeure vrai (la face extérieure du triangle intérieur devient la face intérieure du triangle extérieur, bref on "perd" une face en recollant les deux formules d'Euler)
J'ai l'impression que cette formule ne fonctionne vraiment pas toujours... Une composante connexe est-ce bien (une définition vulgarisé) le nombre d'amas de points qui sont entre eux connexes? c'est à dire si un graphe comprend trois sous-graphes, il y a trois composantes connexes?Envoyé par toothpick-charlie
Merci
quel est ton contre-exemple?
Deux carrés distincts par exemple...
J'ai réfléchis au raisonnement et est-ce qu'il est possible que ce soit plutôt un addition devant la parenthèse? avec cette modification tout fonctionne...
Merci encore
tu as raison, je me suis trompé. On a bien s-a+f=2 pour chaque composante connexe, mais quand on regroupe toutes les composantes connexes, on compte n fois la même face (en dessinant les composantes connexes séparément dans la face non bornée, mais c'est facile de voir que ça ne change rien), et donc la formule est bien s-a+f - (n-1) = 2 ou si tu préfères s-a+f = 1+n (ça marche avec les deux carrés).
il te reste à démontrer la formule l'Euler s-a+f=2 pour un graphe planaire connexe. Il y a de nombreuses façons de faire (Imre Lakatos a écrit un livre entier là-dessus). La plus simple consiste à trianguler le graphe (i.e. ajouter de arêtes de façon à ce que toutes las faces soient des triangles), et à raisonner par récurrence sur le nombre de triangles.
