Bonjour à tous ,
J'ai un DM pour la rentrée et je bloque sur les 2 dernières questions :
d ) Dans un graphe quelconque d'ordre 4, qu'elle est la longueur maximale d'une chaîne reliant 2 sommets quelconques vérifiant :
- Les arêtes sont distinctes.
- Les sommets sont distincts.
& une petite question : Comment déterminer si un graphe donnés par sa matrice est connexe ou non sans les dessiner ?
Pouvez-vous m'aider SVP.
Merci.
Graphes et Matrices
-
Piimousse
-
SoS-Math(11)
- Messages : 2881
- Enregistré le : lun. 9 mars 2009 18:20
Re: Graphes et Matrices
Bonsoir
Pour la question supplémentaire, il me semble que connexe veut dire qu'il n'y a pas deux sous graphes sans liens, donc dans la matrice il ne doit pas y avoir de "blocs" où il n'y a que des 0. Fais des essais avec différentes matrices et différents graphes non-connexes.
Pour la première question : prends un graphe à 4 sommets A, B, C, D et regarde si tu peux aller de A à D avec une arête ; puis si tu peux y aller avec deux arêtes, puis si tu peux y aller avec trois arêtes ; puis avec quatre sans réutiliser deux fois le même sommet ni deux fois la même arête et conclus.
Bonne suite d'exercice
Pour la question supplémentaire, il me semble que connexe veut dire qu'il n'y a pas deux sous graphes sans liens, donc dans la matrice il ne doit pas y avoir de "blocs" où il n'y a que des 0. Fais des essais avec différentes matrices et différents graphes non-connexes.
Pour la première question : prends un graphe à 4 sommets A, B, C, D et regarde si tu peux aller de A à D avec une arête ; puis si tu peux y aller avec deux arêtes, puis si tu peux y aller avec trois arêtes ; puis avec quatre sans réutiliser deux fois le même sommet ni deux fois la même arête et conclus.
Bonne suite d'exercice