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. Cheminement dans les graphes 3. Problèmes de cheminement dans les Graphes 4. Problèmes d'ordonnancement 5. Arbres et Arborescences 6. 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éfini 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 quinzaine de litres plein de liquide et deux récipients respectivement de 8 litres et 5 litres, vides. 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 Montrez qu'un graphe simple a un nombre pair de sommets de degré impair. 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 Soit G = (X,E) un graphe simple tel que ∣X∣= n 1. Montrer que x Є X, dG(x) ≤ n-1, 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, x1 x2 x3 x6 x5 x4 a b c d e f g h i j k l m n Travaux dirigés de théorie des graphes 3 3. Montrer qu'il existe deux sommets ayant le même degré dans G. Exercice 8 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 9 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 10 (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 11 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 ? Voie A Voie B Voies de triage Travaux dirigés de théorie des graphes 4 Chapitre 2 Cheminement dans les graphes Exercice 1 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 2 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 nécessite ̂ M 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 fsi fait fait fin. Exercice 3 Soit le graphe orienté G=(X,U) représenté dans le tableau ci-dessous: x x1 x2 x3 x4 x5 x6 x7 x8 pred(x) x3,x7 x4,x6 x5 x1 x1 x7,x8 x5 x2 x1 x7 x2 x5 x3 x4 x6 Travaux dirigés de théorie des graphes 5 1. Donner la matrice d'adjacence M du graphe G 2. G est-il connexe ? 3. G admet-il un parcours Eulerien ? Pourqoui ? 4. Donner la matrice de fermeture transitive du graphe G. G amet-il un circuit ? 5. T rouver les composantes fortement connexes de G Exercice 4 Soit G = (X,U) un graphe orienté et M sa matrice d'adjacenc ̂ M e, la fermeture transitive de M. 1. Décrire un algorithme permettant d'obtenir les composantes fortement connexes de G 2. Comment Cet algorithme peut-il être utilisé pour simplifier l'énumération des circuits de G ?. A quoi se réduit cet algorithme lorsque le graphe est sans circuit ?. 3. Définir la matrice booléenne de G, le graphe réduit de G. Montrer comment obtenir ses éléments à partir de . ̂ M 4. Appliquer cet algorithme au graphe donné par le tableau suivant: x 1 2 3 4 5 6 7 8 9 10 11 12 succ 12 1, 3 10 5, 6 4, 6 3, 9 8, 9 8, 9 10 9 10 2, 3 Exercice 5 Démontrer que si deux sommets x et y appartiennent à une même composante fortement connexe C, alors tout chemin de x à y est entièrement inclus dans C. Exercice 6 Est-il possible de tracer les figures suivantes sans lever le crayon (et sans passer deux foix sur le même trait!) ? Exercice 7 On considère des dominos dont les faces sont numérotées 1, 2, 3, 4 ou 5. ♦En excluant les dominos doubles, de combien de dominos dispose- t-on ? ♦Montrez que l’on peut arranger ces dominos de façon à former une boucle fermée (en utilisant la règle habituelle de contact entre les dominos). ♦Pourquoi n’est-il pas nécessaire de considérer les dominos doubles ? ♦Si l’on prend maintenant des dominos dont les faces sont numérotées de 1 à n, est-il possible de les arranger de façon à former une boucle fermée ? Exercice 7 Soit G=(X,U) un 1-graphe orienté complet fortement connexe. Montrer alors que G admet un circuit Hamiltonien. Exercice 8 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. Travaux dirigés de théorie des graphes 6 Chapitre 3 Problèmes de uploads/Philosophie/ tdtg.pdf