suivant: Programmation
monter: Algorithmes sur les graphes
précédent: Graphe Eulérien
  Table des matières
  Index
Définition 9.4
Une
boucle est une arête dont les deux extrémités sont
identiques.
Exercice 9.1
Pour le type abstrait centré-sommets, écrire un algorithme qui compte
le nombre de boucles dans un graphe
![$G$](img103.png)
donné.
Définition 9.5
Une
arête multiple est une arête
![$a$](img35.png)
d'extrémités
![$s$](img92.png)
et
![$t$](img222.png)
, telle qu'il existe une arête
![$b \neq a$](img274.png)
avec
les mêmes extrémités.
Exercice 9.2
Pour le type abstrait centré-sommets, écrire un algorithme qui
compte le nombre d'arêtes multiples dans un graphe
![$G$](img103.png)
donné.
Exercice 9.3
Pour le type abstrait centré-arêtes, écrire un algorithme qui
compte le nombre d'arêtes multiples dans un graphe
![$G$](img103.png)
donné.
Définition 9.6
Un
cycle Hamiltonien
dans un graphe
![$G$](img103.png)
est un cycle
![$C = s_1, e_1, s_2, e_2, \ldots, s_n, e_n, s_1$](img275.png)
,
tel que
![$\{s_1, s_2, \ldots, s_n\} = V(G)$](img276.png)
et
![$\forall i, j \in [1, n], s_i = s_j
\Rightarrow i = j$](img277.png)
.
Autrement dit, le cycle doit contenir tout
les sommets du graphe, et chaque sommet doit figurer exactement
une fois. Par contre, il n'y a pas d'obligation pour chaque arête
d'y figurer.
Exercice 9.4
Prouver qu'une boucle (voir définition
9.4) ne peut
pas figurer dans un cycle Hamiltonien.
Exercice 9.5
Écrire un algorithme qui cherche une cycle Hamiltonien dans un graphe
![$G$](img103.png)
quelconque.
Définition 9.7
Un
arbre non orienté est un graphe non orienté ne
contenant pas de cycle.
Exercice 9.6
Prouver que dans un arbre non orienté, entre deux sommets quelconques
![$s$](img92.png)
et
![$t$](img222.png)
, il existe au plus une chaîne.
Exercice 9.7
Simplifier l'algorithme
9.6 dans le cas où l'on sait que
le graphe d'entrée est un arbre non orienté.
suivant: Programmation
monter: Algorithmes sur les graphes
précédent: Graphe Eulérien
  Table des matières
  Index