Chapitre 1 td theorie des graphes et applications -Programma
Télécharger PDFThéorie des Graphes : Exercices et Applications Pratiques
La théorie des graphes est un domaine fondamental des mathématiques et de l'informatique, permettant de modéliser des relations complexes entre des objets. Voici une série d'exercices pratiques portant sur les concepts de degrés, de coloration, d'algorithmes de connectivité et de matrices d'adjacence.
Exercice 1 : Étude des degrés dans un graphe d'ordre 7
Considérons un graphe G d'ordre 7 (comportant 7 sommets) avec 10 arêtes. Ce graphe possède 6 sommets de degré a et un sommet de degré b. Selon le lemme des poignées de main, la somme des degrés de tous les sommets est égale à deux fois le nombre d'arêtes. Nous avons donc l'équation : 6a + b = 2 * 10, soit 6a + b = 20.
Si l'on considère que G est un graphe simple (sans boucles ni arêtes multiples), le degré maximum d'un sommet est n - 1, soit 6. Dans ce cas, les valeurs entières possibles pour a et b doivent satisfaire cette contrainte. Par exemple, si a = 3, alors b = 2. Si a = 2, alors b = 8 (impossible pour un graphe simple d'ordre 7).
Exercice 2 : Répartition des sommets selon leur degré
Soit G un graphe d'ordre 12 comportant 14 arêtes. On sait que chaque sommet est soit de degré 2, soit de degré 3. Soit x le nombre de sommets de degré 2 et y le nombre de sommets de degré 3. Nous pouvons établir le système d'équations suivant :
- x + y = 12 (Nombre total de sommets)
- 2x + 3y = 28 (Somme des degrés, soit 2 * 14 arêtes)
En résolvant ce système, nous multiplions la première équation par 2 : 2x + 2y = 24. En soustrayant cette ligne de la deuxième équation, nous obtenons y = 4. Par conséquent, x = 8. Le graphe possède donc 8 sommets de degré 2.
Exercice 3 : Propriété des sommets de même degré
Démontrons que dans tout graphe non orienté simple d'ordre n (n ≥ 2), il existe au moins deux sommets ayant le même degré. Dans un graphe simple de n sommets, les degrés possibles pour chaque sommet appartiennent à l'ensemble {0, 1, 2, ..., n-1}. Cependant, un graphe ne peut pas contenir à la fois un sommet de degré 0 (isolé) et un sommet de degré n-1 (relié à tous les autres). Il n'y a donc que n-1 valeurs de degrés disponibles pour n sommets. Selon le principe des tiroirs, au moins deux sommets doivent partager la même valeur de degré.
Exercice 4 : Algorithme de Havel-Hakimi
L'algorithme de Havel-Hakimi permet de vérifier si une suite d'entiers est "graphique", c'est-à-dire s'il existe un graphe simple dont les sommets ont ces degrés. Le processus consiste à retirer le plus grand terme (k) et à soustraire 1 aux k termes suivants, puis à réitérer jusqu'à obtenir une suite connue ou aberrante.
Exemples de suites à tester :
- 5, 5, 4, 4, 3, 3, 3, 1, 0, 0
- 7, 6, 2, 2, 2, 1, 0, 0
- 3, 3, 2, 2, 2, 2, 1
Exercice 5 : Optimisation du transport de produits chimiques
Un chimiste doit transporter sept produits (A, B, C, D, E, F, G). Certains produits réagissent dangereusement entre eux et ne peuvent pas être dans la même caisse. Les incompatibilités sont les suivantes : (A,B,C) en conflit mutuel ; A avec F et D ; E avec F et D ; G avec C, E et F. Pour trouver le nombre minimal de caisses, nous utilisons la coloration de graphe : chaque produit est un sommet et chaque incompatibilité est une arête. Le nombre minimal de caisses correspond au nombre chromatique du graphe.
Exercice 6 : Planification de surveillances policières
Un commissariat doit organiser 8 missions de surveillance avec des horaires précis. Pour minimiser le nombre de policiers, on construit un graphe d'intervalle où chaque mission est un sommet. Une arête relie deux sommets si les horaires des missions se chevauchent. Le nombre minimal de policiers nécessaires est égal à la taille de la plus grande clique du graphe, correspondant au nombre maximum de missions simultanées.
Exercice 7 : Matrice d'adjacence et composantes connexes
La matrice d'adjacence est un outil puissant pour représenter un graphe de manière numérique. Pour identifier les composantes connexes d'un graphe à partir de sa matrice, on utilise généralement l'algorithme de Warshall. Cet algorithme calcule la fermeture transitive, permettant de savoir si un chemin existe entre n'importe quelle paire de sommets.
Exercice 8 : Chemins et puissances de matrices
Dans un graphe orienté, si M est la matrice d'adjacence, le nombre de chemins de longueur k entre un sommet i et un sommet j est donné par le coefficient de la ligne i et de la colonne j de la matrice M élevée à la puissance k (M^k). Cette propriété est essentielle pour l'analyse de réseaux et la détection de cycles. Un cycle existe dans un graphe d'ordre n s'il existe un chemin de longueur n revenant à son point de départ.
FAQ : Questions fréquentes sur les graphes
Qu'est-ce qu'une suite graphique ?
Une suite graphique est une suite d'entiers naturels qui correspond aux degrés des sommets d'un graphe simple existant. L'algorithme de Havel-Hakimi est la méthode de référence pour la tester.
Comment définit-on le nombre chromatique ?
Le nombre chromatique d'un graphe est le nombre minimal de couleurs nécessaires pour colorer ses sommets de telle sorte que deux sommets adjacents n'aient jamais la même couleur.
Quelle est l'utilité de l'algorithme de Warshall ?
L'algorithme de Warshall sert à déterminer la connexité d'un graphe en calculant sa fermeture transitive, ce qui permet de lister toutes les paires de sommets reliées par un chemin, quelle que soit sa longueur.