Julien Sopena

TD 02 – Théorie des graphes : Graphes sans circuit

Exercice 1: Diamètre d'un graphe sans circuit

Question 1.1 )

Dans cet exercice on s'intéresse au diamètre d'un graphe sans circuit. Quel type de graphe doit-on alors considérer ?

Question 1.2 )

Montrer que dans un graphe sans circuit, il existe au moins un sommet sans successeur et au moins un sommet sans prédécesseur.

Question 1.3 )

Montrer alors qu'il existe toujours un chemin entre un sommet sans successeur et un sommet sans prédécesseur.

Question 1.4 )

Quelle est la taille maximum d'un chemin dans un graphe sans circuit ?

Designed by OWSD.org. Valid CSS & XHTML
Ce site et l'ensemble de son contenu est mis à disposition sous un contrat Creative Commons.
Creative Commons License