correction du quizz
Contents
1. CORRECTION Cours Recherche Master Informatique Fondamentale Th orie des graphes QCM de rentr e Notations Pour un graphe G V E non orient resp orient o V est l ensemble des sommets et E l ensemble des ar tes resp arcs on notera n son nombre de sommets et m son nombre d ar tes resp d arcs Pour les questions algorithmiques on suppose que les graphes sont donn s par leurs listes d adjacence et le mot complexit d signera la complexit en temps dans le pire des cas Mode d emploi Pour chacune des questions remplir la case vide ou bien entourer la ou les r ponse s justes il peut ventuellement y en avoir plusieurs ou aucune de juste QUESTION REPONSE Ecrire la d finition que C V est une clique de G V E pur tout x y diff rents dans C xy dans I E Ecrire la d finition que S V est un ensemble ind pendant pour tout x y dans S xy pas dans E stable de G V E La proposition suivante est elle vraie si S est un ensemble ind pendant de G V E alors V S est une clique de G en 4 Dans une classe de 9 l ves chaque l ve envoie des cartes de St NOUI J NON Valentin 2 autres l ves de son choix Est il possible que chaque l ve recoive des cartes des 2 l ves qui il a crit ATN az e Lesquels de ces graphes admettent un cycle eul rien AT Quel est le nombre minimum d ar tes d un nn connexe n som Nr mets sans sous graphe i2. bre maximum d ar tes que peut contenir un graphe 40 sommets qui n a pas de clique de taille 5 Soit G un graphe sans triangle ni carr de diam tre 2 non r gulier et avec un sommet de degr 7 Combien y a t il de sommets dans G 25 Etant donn un ensemble de n individus o chacun a au plus 4 amis est il toujours possible de diviser cet ensemble en 5 groupes tel qu il Cadre pour des commentaires et ou pour justifier vos r ponses aux questions 27 28 et 29
3. e taille k pour G et k gt 3 quelconques 20 Soit k gt 3 fix quelle est la complexit de v rifier si un graphe G conten ne he de taile pouz gileangue 21 Quelle est la complexit de v rifier si un graphe G est k colorable Polynomial P pour Get a Soit k gt 3 fix quelle est la complexit de v rifier si un graphe G est k colorable pour G quelconque Un mini gala r unit 5 filles et 5 gar ons Sachant que chaque fille a d j fait connaissance de exactement 3 des 5 gar ons et chaque gar on a d j fait connaissance de exactement 3 des 5 filles est il toujours possible de r partir les 10 en 5 couples fille gar on disjoints tel que chaque couple r unit deux personnes se connaissant d j Etant donn trois maisons position es dans le plan ainsi que trois sources eau lectricit gaz peut on relier chacune des maisons aux trois sources en dessinant des canalisations qui ne se coupent pas n y ait pas deux amis au sein d un m me groupe M me question si on veut diviser l ensemble en 4 groupes Soit S un ensemble de n individus tel que pour toute paire d individus il y en a toujours un qui est strictement plus fort que l autre Un Roi est un individu x pour lequel il existe une partie A S x son arm e tel que x bat tous les individus de et tout autre individu est battu par un l ment de A ou par x Existe t il toujours un Roi dans S Quel est le nom
4. nduit isomorphe Tout arbre admet au moins un couplage parfait MARA ES ATON Quelle est la meilleure complexit avec laquelle on sait d tecter si un graphe non orient est connexe Quelle est la meilleure complexit avec laquelle on sait d tecter si un O n m O n NP complet graphe orient contient un circuit Quelle est la meilleure complexit avec laquelle on sait d tecter si un O n Ofn m O n NP complet graphe non orient contient un cycle men Quelle est la meilleure complexit avec laquelle on sait d tecter si un graphe non orient contient un cycle qui passe par tous les sommets une fois et une seule LT aaa 13 Avec quelle complexit sait on calculer un arbre couvrant de poids log n On minimum dans un graphe non orient pond r Idem quand toutes les ar tes ont des poids gaux 1 Avec quelle complexit sait on calculer les distances partir d une source dans un graphe orient dont les arcs ont des poids positifs Idem quand tous les arcs ont des poids gaux 1 Avec quelle complexit sait on calculer les distances pour tous les couples de sommets dans un graphe orient dont les arcs ont des poids positifs meilleur classique QUESTION REPONSE Quelle est la meilleure complexit avec laquelle on sait v rifier si un KO m graphe est biparti Quelle est la complexit de v rifier si un graphe G contient une clique Polynomial P complet d
Download Pdf Manuals
Related Search