SOS-MATH

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.

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