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.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :