Algorithmique et programmation
Travaux dirigés, 22 décembre 2000
Graphes ; Arborescences.
- Arborescences
Une arborescence de racine r est un graphe orienté (fini)
dont r est un sommet
et tel que pour tout autre sommet x il existe un unique chemin de
r à x.
On représente souvent une arborescence en numérotant ses sommets et
en indiquant pour chacun quel est son père.
-
Quelle est la différence entre un arbre et une arborescence ?
- Si les sommets sont numérotés de 1 à n,
on dit qu'une arborescence est préfixe lorsque l'ensemble des
descendants de tout sommet i est un intervalle dont le minimum
est i. Trouver un algorithme de renumérotation qui rend une
arborescence préfixe.
- Arborescence recouvrante
Étant donné un graphe orienté G, une arborescence recouvrante est un
graphe partiel de G qui est une arborescence et qui passe par
tous les sommets.
On dit qu'un graphe est enraciné en r s'il existe une arborescence
recouvrante de racine r.
-
Trouver un algorithme qui dit si un graphe est enraciné.
- Chemin de poids minimal
On suppose que chaque arc est valué par un réel.
Le poids d'un chemin est la somme des poids de ses arcs.
-
Proposer un algorithme pour calculer un chemin de poids minimal
entre deux sommets, dans le cas où les poids des arcs ne sont
jamais négatifs.
- Proposer un algorithme pour trouver s'il existe un cycle de poids
négatif.
- Proposer un algorithme pour calculer un chemin de poids minimal
dans le cas général.
- Arborescences recouvrantes de poids minimal
On suppose que chaque arc est valué par un réel strictement positif.
Le poids d'une arborescence est la somme des poids de ses arcs.
-
Proposer un algorithme pour trouver une arborescence
recouvrante de poids minimal pour un graphe non-orienté.
- Regarder le cas des graphes orientés.
- Arborescence des dominants
On suppose que le graphe (orienté) G est acyclique et enraciné.
On dit qu'un sommet en domine un autre s'il est dans tout chemin
de la racine à cet autre sommet.
-
Montrer que la relation de domination décrit une arborescence.
- Trouver un algorithme qui calcule cette arborescence.
- Réduction transitive
Rappel : la clôture transitive d'un graphe (orienté)
est un graphe ayant les mêmes
sommets et dont deux sommets sont reliés par une arête s'il
y a un chemin les reliant dans le graphe de départ.
Une réduction transitive est un graphe avec un nombre minimal
d'arêtes et même clôture transitive.
-
Trouver une condition pour que la réduction transitive soit unique.
- Trouver un algorithme de calcul d'une réduction transitive.
This document was translated from LATEX by
HEVEA.