PLAN DES TRAVAUX PRATIQUES DE THEORIE DES GRAPHES

Theorie des Graphes. Travaux Pratiques

Trương Mỹ Dung, F.I.T, ĐHKHTN, ĐHQG-HCM

www.is-edu.hcmuns.edu.vn;

Mail: [email protected]

PLAN DES TRAVAUX PRATIQUES DE

THEORIE DES GRAPHES.

I. OBJECTIF.

Eùcrire des programmes et impleùmenter un nombre d’algorithmes relatifs aø la

theùorie des graphes. Le contenu est comme suit:

1. EXERCICE N0

1.

ƒ Organiser la mise en meùmoire de l’ensemble des areâtes, la matrice d’adjacence

d’un graphe orienteù (non orienteù).

ƒ Eùcrire une proceùdure pour l’entreùe de l’ensemble des sommets, de la matrice

d’adjacence (on peut utiliser un fichier).

ƒ Eùcrire une proceùdure pour imprimer de l’ensemble des sommets, de la matrice

d’adjacence.

2. EXERCICE N0

2. Eùcrire une proceùdure de parcours en profondeur (en largeur)

d’un graphe orienteù (non orienteù).

3. EXERCICE N0

3. Eùcrire une proceùdure pour trouver les composantes connexes

d’un graphe non orienteù.

4. EXERCICE N0

4. Eùcrire une proceùdure pour l’algorithme de PRIM.

5. EXERCICE N0

5. Eùcrire une proceùdure pour l’algorithme de KRUSKAL.

6. EXERCICE N0

6. Eùcrire une proceùdure pour l’algorithme de DIJKSTRA-MOORE.

7. EXERCICE N0

7. Eùcrire une proceùdure pour l’algorithme de BELLMAN-FORD.

8. EXERCICE N0

8. Eùcrire une proceùdure pour l’algorithme de FLOYD.

II. EXAMENS. Epreuves pratiques en deux temps: une fois au milieu du cours et une

autre aø la fin.