qcm corrigé
Contents
1. les OUI sommets sont des rectangles du plan et deux sommets sont adjacents si et seulement si l intersection de leurs rectangles est non vide Est ce que cette classe est incluse dans la classe des graphes parfaits 7 La proposition suivante est elle vraie tout classe de graphes sta NON ble par mineur peut aussi tre caract ris e par une famille finie de mineurs interdits 8 Quelle est la meilleure complexit avec laquelle on sait reconna tre GO O n O n NP dur les graphes qui n admettent pas K1 3 comme mineur 9 La proposition suivante est elle vraie toute classe caract ris e par NON une famille infinie de mineurs interdits peut aussi tre caract ris e par une famille finie de mineurs interdits 10 Lesquels de ces graphes sont planaires 11 Soient et B deux modules quelconques d un graphe G Parmi les AUB A B ensembles suivants lesquels sont toujours des modules 12 M me question si A et B sont des modules tels que AN B Exercice 2 Calcul de w pour des classes particuli res 5 pts 1 Pour un graphe G quelle est la complexit connue pour calculer le cardinal maximum d une clique de G polynomiale ou NP dure question culturelle pas besoin de justifier votre r ponse 2 Ayant en entr e un cographe G et un arbre de d composition modulaire de G donner un algorithme polynomial aussi efficace que possible pour calculer le cardinal maximum2. Votre identifiant 22 5 janvier 2010 Examen de graphes 2 heures Notations dans les exercices suivants le mot complexit d signera la complexit en temps dans le pire des cas Pour un graphe on notera n son nombre de sommets et m son nombre d ar tes cas non orient ou d ares cas orient Sauf indication contraire les graphes sont par d faut sans boucle et sans multi ar tes ou arcs Pour les questions algorithmiques on suppose que les graphes sont donn s par leurs listes d adjacence Les notes et documents de cours sont autoris s Exercice 1 QCM 6 pts Mode d emploi Pour chacune des questions entourer la ou les r ponse s justes il peut ventuellement y en avoir plusieurs ou aucune de juste QUESTION REPONS 1 Existe t il un graphe non orient dont la liste des degr s des sommets OUI est 4 2 2 2 2 M me question si la liste des degr s est 3 3 2 1 OUI 3 M me question si la liste des degr s est 3 2 2 1 NON 4 Quelle est la complexit du probl me consistant enlever le minimum NP dur d ar tes un graphe non orient pour qu il devienne acyclique 5 Un graphe G est parfait si pour tout sous graphe induit H x H i w H o x H resp w H est le nombre chromatique resp le TD t te cardinal max d une clique de H Quels sont les graphes parfaits s 6 Consid rer la classe des graphes d intersection de rectangles
3. avant d avoir num rot un sommet de T 4 Montrer que si G est chordal connexe et n a pas de sommet universel alors Lex BFS termine toujours sur un sommet simplicial Suggestion vous pouvez montrer que quand Lex BFS a satur tous les s parateurs il reste encore des sommets non num rot s Utiliser le fait que chaque tape de l algorithme le graphe induit par les sommets num rot s est connexe 5 D duire de la question pr c dente que pour tout graphe chordal Lex BFS fournit une num rotation qui est l ordre inverse d une s quence d limination simpliciale
4. d une clique de G Analyser la complexit de votre algorithme en fonction de n et m 3 Ayant en entr e un graphe chordal G et une s quence d limination simpliciale de G donner un algorithme polynomial aussi efficace que possible pour calculer le cardinal maximum d une clique de G Analyser la complexit de votre algorithme en fonction de n et m 4 Ayant en entr e un graphe G tel que tw G lt 5 et une d composition arborescente de G de largeur au plus 5 donner un algorithme polynomial aussi efficace que possible pour calculer le cardinal maximum d une clique de G Analyser la complexit de votre algorithme en fonction de n et m Exercice 3 La gallerie d art 4 pts Un graphe planaire est dit outerplanar si l une de ses repr sentations planaires est telle que tous ses sommets sont sur la face externe voir l exemple ci dessous 1 Montrer que tout graphe outerplanar est 3 colorable 2 Montrer le Th or me de la Galerie d Art 1975 tant donn e une galerie d art dont les murs forment un polygone simple n c t s alors il est possible de placer n 3 gardiens tels que tout point dans la galerie soit visible par au moins un des gardiens Suggestion vous avez le droit d utiliser autant que vous voulez le lemme g om trique qui assure que tout polygone simple admet deux sommets que l on peut relier par un segment qui reste l int rieur du polygon
5. e Exercice 4 Lex BFS pour les graphes chordaux 5 pts Soit G V E un graphe non orient Au cours de l ex cution d un parcours Lex BFS un ensemble de sommets U C V est dit touch s il existe au moins un sommet u U qui a t num rot par l algorithme L ensemble U est dit satur si tout ses sommets ont t num rot s Soit e une ar te d un arbre T on note Tf et T les deux composantes connexes du graphe T e r sultant de la suppression de e dans T Soit T un arbre de cliques d un graphe chordal G et T un sous arbre de T Les sommets x de G tels que le sous arbre Ty de T induit par les cliques maximales contenant x v rifie Ts C T sont appel s sommets propres T Au cours d une ex cution de Lex BFS on dira que T est vierge si aucun de ses sommets propres n a encore t num rot 1 Montrer que pour toute ar te e d un arbre de cliques T d un graphe chordal G T et T5 contiennent tous les deux au moins un sommet propre 2 Au cours d une ex cution de Lex BFS sur G montrer que quand un s parateur de G est touch pour la premi re fois alors pour toute ar te e de T tiquet e par S un et un seul des deux sous arbres T et T est vierge 3 Soit e une ar te de T tiquet e par un s parateur S Soit T le sous arbre qui est vierge quand S est touch pour la premi re fois Montrer que Lex BFS num rote alors tous les sommets de S
Download Pdf Manuals
Related Search