1. 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.
   1. Quelle est la différence entre un arbre et une arborescence ?
   2. 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.
   
   
2. 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.
   1. Trouver un algorithme qui dit si un graphe est enraciné.
   
   
3. 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.
   1. 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.
   2. Proposer un algorithme pour trouver s'il existe un cycle de poids négatif.
   3. Proposer un algorithme pour calculer un chemin de poids minimal dans le cas général.
   
   
4. 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.
   1. Proposer un algorithme pour trouver une arborescence recouvrante de poids minimal pour un graphe non-orienté.
   2. Regarder le cas des graphes orientés.
   
   
5. 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.
   1. Montrer que la relation de domination décrit une arborescence.
   2. Trouver un algorithme qui calcule cette arborescence.
   
   
6. 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.
   1. Trouver une condition pour que la réduction transitive soit unique.
   2. Trouver un algorithme de calcul d'une réduction transitive.

This document was translated from L^AT_EX by H^EV^EA.