Chapitre 3 td theorie des graphes et applications -Programma

Télécharger PDF

Théorie des Graphes : Exercices d'Application sur les Réseaux et l'Optimisation

La théorie des graphes est un outil essentiel pour modéliser et résoudre des problèmes complexes de connectivité et de flux. Qu'il s'agisse de déployer des infrastructures de télécommunications ou d'optimiser la distribution de ressources, les algorithmes de graphes permettent de trouver les solutions les plus économiques et efficaces.

Exercice 1 : Réseau de Fibres Optiques et Algorithmes de Cheminement

On souhaite relier six villes (a, b, c, d, e, f) par un réseau de fibres optiques. Les liaisons possibles et leurs coûts respectifs (en milliers de dinars) sont définis par les arêtes du graphe suivant :

Liaisons depuis a : (a, b)=4, (a, e)=6, (a, f)=5
Liaisons depuis b : (b, c)=4, (b, d)=2, (b, f)=2
Liaisons depuis c : (c, d)=8, (c, f)=1
Liaisons depuis d : (d, e)=2
Liaisons depuis e : (e, f)=1

1. Connexion de toutes les villes à coût minimal

Pour obtenir un réseau connectant toutes les villes avec un coût minimum, nous utilisons l'algorithme de Kruskal, qui consiste à sélectionner les arêtes de poids minimal tout en évitant de créer des cycles :

On sélectionne l'arête (c, f) : coût 1
On sélectionne l'arête (e, f) : coût 1
On sélectionne l'arête (b, d) : coût 2
On sélectionne l'arête (b, f) : coût 2
On sélectionne l'arête (a, b) : coût 4

Le coût total du réseau minimal est de 10 milliers de dinars. Toutes les villes sont désormais reliées de façon optimale.

2. Plus court chemin entre les villes d et f

En utilisant l'algorithme de Dijkstra pour trouver la distance minimale entre d et f :

Chemin via e : d-e-f (2 + 1) = 3
Chemin via b : d-b-f (2 + 2) = 4

Le coût minimal de connexion entre les villes d et f est donc de 3.

Exercice 2 : Optimisation de la Distribution d'Eau

Dans ce problème, trois châteaux d'eau (C1, C2, C3) doivent alimenter quatre villages (V1, V2, V3, V4). Il s'agit d'équilibrer les débits disponibles avec les besoins des consommateurs tout en respectant les capacités des canalisations.

Analyse des besoins et des ressources :

Débits disponibles : C1 (45 L/s), C2 (25 L/s), C3 (20 L/s).
Besoins des villages : V1 (30 L/s), V2 (10 L/s), V3 (20 L/s), V4 (30 L/s).

Plan d'alimentation suggéré :

Pour satisfaire les demandes en fonction des capacités maximales des tuyaux :

Village V1 (30 L/s) : Reçoit 10 de C1 et 20 de C2 (capacités saturées).
Village V2 (10 L/s) : Reçoit 10 de C1 (capacité disponible de 15).
Village V3 (20 L/s) : Reçoit 10 de C3 et 5 de C2 (selon les limites de C2 et C3).
Village V4 (30 L/s) : Reçoit 20 de C1 et 10 de C3.

Ce plan permet de couvrir la majorité des besoins en respectant les contraintes physiques des infrastructures existantes.

Exercice 3 : Théorie du Flot Maximum

Le concept de flot maximum est crucial pour comprendre la capacité limite d'un réseau de transport. Dans un tel système, on cherche à faire transiter la plus grande quantité possible d'un flux (données, liquide, trafic) d'une source vers une destination. L'algorithme de Ford-Fulkerson est la méthode de référence pour résoudre ce type de problème en identifiant des chaînes augmentantes jusqu'à ce qu'aucune amélioration ne soit possible.

Foire Aux Questions (FAQ)

Quelle est la différence entre l'algorithme de Prim et celui de Kruskal ?
L'algorithme de Prim construit l'arbre couvrant de poids minimum de proche en proche à partir d'un sommet initial, tandis que l'algorithme de Kruskal traite l'ensemble des arêtes du graphe triées par poids croissant.

Quand faut-il utiliser l'algorithme de Dijkstra ?
Dijkstra est utilisé pour trouver le plus court chemin entre un point de départ et tous les autres points d'un réseau, à condition que les poids des arêtes (distances, coûts, temps) soient positifs.

Qu'est-ce qu'une capacité dans un graphe de flot ?
La capacité est la valeur maximale que peut supporter une arête. Elle représente une contrainte physique, comme le diamètre d'un tuyau ou la bande passante d'une connexion internet.