Remerciez-le!

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

Tdtg Université des Sciences et Technologie Houari Boumediene Faculté d ? Électronique et Informatique Département Informatique Travaux Dirigés de Théorie des Graphes Table des matières Concepts fondamentaux des graphes Cheminement dans les graphes Problè

Université des Sciences et Technologie Houari Boumediene Faculté d ? Électronique et Informatique Département Informatique Travaux Dirigés de Théorie des Graphes Table des matières Concepts fondamentaux des graphes Cheminement dans les graphes Problèmes de cheminement dans les Graphes Problèmes d'ordonnancement Arbres et Arborescences Les ots Licence Informatique L CTravaux dirigés de théorie des graphes Chapitre Concepts fondamentaux des graphes Exercice Donner la représentation matricielle du graphe suivant Trouvez les degrés extérieurs et intérieurs de chacun des sommets x x x x x x Exercice On considère l'ensemble E d'habitant d'un immeuble on dé ?ni 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 a d f c h k i l m b e g j n Est-il possible de déterminer à partir du graphe G tous les couples véri ?ant la relation R' a R' b ?? b est le frère de a Soit R la relation dé ?nie 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 Caractériser G par rapport à G 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 On Dispose d ? un récipient d ? une quinzaine de litres plein de liquide et deux récipients respectivement de litres et litres vides On veut isoler litres de liquide dans le récipient de litres sans perdre de liquide Résoudre ce problème en utilisant un graphe Exercice Montrez qu'un graphe simple a un nombre pair de sommets de degré impair Exercice On s'intéresse aux graphes -réguliers Construisez de tels graphes ayant sommets sommets sommets sommets Qu'en déduisez-vous Prouvez-le Exercice Un groupe de fans d ? un chanteur célèbre possède les deux particularités suivantes ? Chaque personne conna? t au moins autres ? Toute 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 fans apprend une chose nouvelle sur leur idole et celui o? le groupe entier est au courant Exercice Soit G X E un graphe simple tel que ??X ?? n Montrer que ? x X dG x ? n- 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- CTravaux dirigés de théorie des graphes Montrer qu'il existe deux sommets ayant le même degré dans G Exercice 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 ? m n ? ? G Exercice Soit G un graphe simple biparti d ? ordre n montrer que le nombre