Julien Sopena

TD 01 – Théorie des graphes : Propriétés et parcours

Exercice 1: Propriétés des graphes

Question 1.1 )

Énoncez les propriétés des graphes de la figure 1

Question 1.2 )

Énoncez et vérifiez sur ces graphes (Fig. 1) le théorème des poignées de mains.

Question 1.3 )

Un graphe peut-il être à la fois transitif et biparti ? Si oui, donnez un exemple. Si non, pourquoi ?
Graphe 1

Graphe 2

Graphe 3
Figure 1: Divers graphes

Exercice 2: Parcours en profondeur

Question 2.1 )

Rappelez l'algorithme récursif du parcours en profondeur vu en cours.

Question 2.2 )

Donnez le résultat d'un parcours en profondeur sur les graphes de la figure 1. Vous utiliserez l'ordre lexicographique pour le choix des sommets dans les différentes boucles de l'algorithme.

Question 2.3 )

Quelle est la complexité de l'algorithme récursif ? On s'intéressera ici, au nombre d'appels et au nombre de tests sur la couleur des nœuds.

Question 2.4 )

Donnez un algorithme itératif pour le parcours en profondeur.

Question 2.5 )

Quelle est la complexité de l'algorithme itératif ?

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