Inscription / Connexion Nouveau Sujet
Graphe sans point d'articulation
Bonjour.
Je considère un graphe simple non orienté, supposé connexe et sans point d'articulation. On note n le nombre de sommets, et p le nombre d'arêtes, et on suppose n
3.
Pourriez m'indiquer si les trois propriétés suivantes sont vraies? Connaissez un bonne référence sur ce sujet? Je vous remercie d'avance!
1) p n
2) p=n si, et seulement si, le graphe est un cycle
3) p=n+1 ssi le graphe est un cycle auquel on adjoint une chaine reliant deux de ses sommets.
Ce sont trois conjectures personnelles.
J'arrive à prouver 1) et 2), mais j'ai peur d'avoir fait des erreurs.
Et j'ai un doute sur 3).
J'aimerais beaucoup avoir des références sur le sujet, merci d'avance!
Un point d'articulation est un sommet tel que, si on le supprime du graphe, le graphe n'est plus connexe.
Annuler
connectez vous
algèbre en post-bac