Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université des Sciences et Technologie Houari Boumediene Faculté d’Électronique

Université des Sciences et Technologie Houari Boumediene Faculté d’Électronique et Informatique Département Informatique Travaux Dirigés de Théorie des Graphes Licence Informatique, L3 Table des matières : 1. Concepts fondamentaux des graphes 2. Problèmes de cheminement dans les Graphes 3. Problèmes d'ordonnancement 4. Arbres et Arborescences 5. Les flots Travaux dirigés de théorie des graphes 2 Chapitre 1 Concepts fondamentaux des graphes Exercice 1 Donner la représentation matricielle du graphe suivant, T rouvez les degrés extérieurs et intérieurs de chacun des sommets. Exercice 2 On considère l'ensemble E d'habitant d'un immeuble, on définit dans E la relation R telle que : a R b ⇔ b est la sœur de a. Soit G le graphe représentant cette relation. 1. Est-il possible de déterminer à partir du graphe G tous les couples vérifiant la relation R' : a R' b ⇔ b est le frère de a. 2. Soit R* la relation définie par : a R* b ⇔ b est le frère ou la sœur de a, et soit G* le graphe associé. Que peut-on dire de G* 3. Caractériser G par rapport à G*. 4. Si on ne considère que les éléments {f,g,h,i,j,k,l,m} nous aurions un autre graphe G'. Caractériser G' par rapport à G. Exercice 3 On Dispose d’un récipient d’une capacité de 15 litres plein, et deux récipients respectivement de 8 litres et 5 litres, vides. Les récipients ne sont pas gradués et nous ne disposons d’aucun autre moyen de mesure. On veut isoler 7 litres de liquide dans le récipient de 8 litres sans perdre de liquide. Résoudre ce problème en utilisant un graphe. Exercice 4 Le jeu de la T our de Hanoi est décrit comme suit : 1. Trois (03) tours A, B et C permettent d'empiler des disques les uns sur les autres ; 2. au départ, n disques sont empilés sur la tour A; 3. les disques sont de tailles différentes, allant du plus petit (1) au plus grand (n). 4. sur une même tour, les disques ne peuvent être empilés de bas en haut que du plus grand au plus petit; 5. on ne peut déplacer qu'un disque à la fois. Le jeu consiste à déplacer tous les disques de la tour A vers une autre tour. Modéliser ce jeu pour n = 3 à I'aide d'un graphe. Exercice 5 On s'intéresse aux graphes 3-réguliers. Construisez de tels graphes ayant 4 sommets, 5 sommets, 6 sommets, 7 sommets. Qu'en déduisez-vous? Prouvez-le! Exercice 6 Un groupe de 15 fans d’un chanteur célèbre, possède les deux particularités suivantes : • Chaque personne connaît au moins 7 autres • T oute information détenue par une personne est répercutée dans la minute qui suit à ses connaissances (et uniquement à elles) . Quel est le temps maximal entre le moment où une des 15 fans apprend une chose nouvelle sur leur idole, et celui où le groupe entier est au courant ? Exercice 7 Montrez qu'un graphe simple a un nombre pair de sommets de degré impair. Exercice 8 Soit G = (X,E) un graphe simple tel que ∣X∣= n 1. Montrer que x Є X, dG(x) ≤ n-1, x1 x2 x3 x6 x5 x4 h a b c d e f g i j k l m n Travaux dirigés de théorie des graphes 3 2. Montrer qu'il ne peut y avoir dans G à la fois un sommet de degré égal à zéro et un sommet de degré égal à n-1, 3. Montrer qu'il existe deux sommets ayant le même degré dans G. 4. Donner (en justifiant) le nombre d’arêtes dans le cas où G est complet. Exercice 9 Soit G=(X,U) un graphe d’ordre n, le nombre d’arcs est désigné par m. Soient δ(G) et ΔG) respectivement les degrés minimum et maximum du graphe G montrer que : δ(G) ≤ 2m n ≤ Δ(G) Exercice 10 1. Montrer qu'un graphe régulier d'ordre impair ne peut être biparti. 2. Soit G un graphe simple biparti d’ordre n, montrer que le nombre d’arêtes m ≤ n²/4 . En déduire qu’il existe un sommet x tel que dG( x ) ≤n/2 . Exercice 11 (organisation d’un examen ) On veut organiser un examen comportant, outre les matières communes, 6 matières d’options : Français (F), Anglais (A), Mécanique (M), Dessin industriel (D), Informatique (I), Sport (S). Les profils des candidats à options multiples sont : F,A,M - D,S - I,S - I,M 1. Quel est le nombre maximum d’épreuves qu’on peut mettre en parallèle ? 2. Une épreuve occupe une demi-journée ; quel est le temps minimal nécessaire pour ces options ? Exercice 12 On a 6 wagons à trier. Dans la gare de triage, les wagons entrent dans l'ordre 2, 5, 3, 6, 1, 4 et doivent sortir dans l'ordre croissant, Deux wagons i et j peuvent être mis sur la même voie de triage si et seulement s'ils entrent dans l'ordre dans lequel ils doivent sortir. Dessiner le graphe illustrant la situation, en indiquant ce que représentent les sommets et les arêtes du graphe. Quel sera le nombre minimal de voies de triage nécessaires ? Exercice 13. Dans un groupe de personnes est tel que chaque personne est membre d’exactement deux (2) associations, chaque association comprend exactement trois (3) membres et deux (2) associations quelconques ont toujours exactement un (1) membre en commun. Combien y a-t-il de personnes ? Combien y a-t-il d’associations ? Exercice 14. Montrez que dans un groupe de six (6) personnes, il y en a nécessairement trois (3) qui se connaissent mutuellement ou trois (3) qui ne se connaissent pas (on suppose que si A connaît B, B connaît également A). Cela est-il nécessairement vrai dans un groupe de cinq (5) personnes. Exercice 15. Soit G=(X, E) un graphe simple, d’ordre n. Si G est k-régulier, dans quelles conditions il est isomorphe à son complémentaire ? Voie A Voie B Voies de triage Travaux dirigés de théorie des graphes 4 Chapitre 2 Cheminement dans les graphes Exercice 1 Dans un réseau téléphonique constitué de 2n centraux téléphoniques disposés de telle façon que chaque centrale est reliée par une ligne téléphonique directe avec au moins n autres centraux. Montrez qu’il est toujours possible d’établir une liaison entre deux centraux quelconques. Exercice 2 Soit G=(X, E) un graphe connexe. Montrons qu'il existe un sommet x tel que le sous-graphe de G engendré par le sous ensemble de sommets X-{x} est toujours connexe. Exercice 3 Une société est constituée de Quinze (15) sites. Chaque site est relié par une ligne spécialisée à au moins sept (7) autres. Le serveur de bases de données est placé sur l’un des sites. Est-il possible d’accéder au serveur de bases de données à partir de n’importe quel autre site. Exercice 4 Soit G=(X,E) un graphe non orienté, simple et connexe d'ordre n. – On appelle longueur d'une chaîne μ(x,y) joignant les deux sommets x et y, |μ(x,y)|, le nombre d'arêtes de cette chaîne. – On désigne par e(x,y), l'écart entre x et y, la longueur de la plus courte chaîne joignant x et y; e(x,y) = min{|μ(x,y)|} e(x,x) = 0. On appelle: – Écartement d'un sommet x, le nombre E(x) = max{e(x,y)}, y ЄX – Diamètre de G, le nombre e(G) = max{e(x,y)}, x, y ЄX – Rayon de G, le nombre r(G) = min{E(x)}, x ЄX – Centre de G, un sommet s Є X tel que E(s) = r(G) Déterminer le diamètre, le rayon et le ou les centres du graphes suivants: Exercice 5 Soit G = (X, U) un graphe orienté simple et M (de terme général mij) sa matrice d'adjacence. On définit par récurrence sur l'entier k ≥ 2, la puissance booléenne M[k] qui est la matrice de terme général: m[k ] ij = n ∨ l=1 (m[k−1] il ∧mlj) et on pose M [1]=M et ̂ M = M [1] ∨M [2] ∨... ∨M [n] 1. Donner une interprétation aux éléments de M[l]. 2. Interpréter les éléments de ̂ M en particulier ̂ mii . 3. Montrer que I∨̂ M= (I∨M) [n] = (I∨M) [ p], ∀p⩾n 4. En déduire un procédé de calcul de (I∨̂ M ) . comportant au plus E[log2(n)] + 1 produits booléens de matrices. Et comparer le avec le nombre d'opérations nécessaires au calcul de ̂ M Algorithme de Warshall. Le calcul direct de la matrice ^ M nécessite trop d'opérations matricielles. L'algorithme de Warshall, donné ci-dessous, permet de calculer ^ M avec un gain considérable en nombre d'opérations (n2 tests et au plus n3 opération V, c'est donc un algorithme en O(n3). Procédure Warshall (Donnée: M, résultat: ) ̂ M Début Pour i de 1 à n faire pour j de 1 à n faire si mji = 1 alors pour k de 1 à n faire mjk = mjk v mik fait x1 x7 x2 x5 x3 x4 x6 Travaux dirigés de théorie des graphes 5 fsi fait fait fin. Exercice 6 Soit le graphe orienté G=(X,U) représenté dans le tableau ci-dessous: x x1 x2 x3 x4 uploads/Philosophie/ travaux-diriges-de-th-des-graphes.pdf