Remerciez-le!

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

Travaux diriges de th des graphes

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 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é ?nit 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 capacité de litres plein et deux récipients respectivement de litres et litres vides Les récipients ne sont pas gradués et nous ne disposons d ? aucun autre moyen de mesure 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 Le jeu de la Tour de Hanoi est décrit comme suit Trois tours A B et C permettent d'empiler des disques les uns sur les autres au départ n disques sont empilés sur la tour A les disques sont de tailles di ?érentes allant du plus petit au plus grand n sur une même tour les disques ne peuvent être empilés de bas en haut que du plus grand au plus petit 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 à I'aide d'un graphe 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 Montrez qu'un graphe simple a un nombre pair de sommets de degré impair Exercice Soit G X E un