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

donné.
Définition 9.5
Une
arête multiple est une arête

d'extrémités

et

, telle qu'il existe une arête

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

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

donné.
Définition 9.6
Un
cycle Hamiltonien
dans un graphe

est un cycle

,
tel que

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

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

et

, 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