Cours Recherche Master Informatique Fondamentale Théorie des
Contents
1. connexe Quelle est la meilleure complexit avec laquelle on sait d tecter si un graphe orient contient un circuit Quelle est la meilleure complexit avec laquelle on sait d tecter si un graphe non orient contient un cycle 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 Quel est le nombre minimum d ar tes d un graphe connexe n som une fois et une seule 13 Avec quelle complexit sait on calculer un arbre couvrant de poids 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 17 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 ieurs ou aucune de juste REPONSE M Onrm On O NP complet QUESTION graphe est biparti 19 Quelle est la complexit de v rifier si un graphe G contient une clique de taille k pour G et k gt 3 quelconques 0 Soit k gt 3 fix quelle est la complexit de v rifier si un graphe G 5 contient une clique de taille k pour G quelconque 1 Quelle est la complexit de v rifier si un graphe G est2. Cours Recherche Master Informatique Fondamentale Th orie des graphes QCM de rentr e Notations Pour un graphe G V E non orient resp des sommets et E l ensemble des ar tes resp arcs on note orient o V est l ensemble ra 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 plus QUESTION Ecrire la d finition que C V est une clique de G V E bal 2 Ecrire la d finition que S V est un ensemble ind pendant ou 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 Dans une classe de 9 l ves chaque l ve envoie des cartes de St Valentin a 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 M me question en rempla ant 2 par 3 Lesquels de ces graphes admettent un cycle eul rien mets sans sous graphe induit isomorphe He Tout arbre admet au moins un couplage parfait Quelle est la meilleure complexit avec laquelle on sait d tecter si un graphe non orient est
3. k colorable S pour G et k gt 3 quelconques 22 Soit k gt 3 fix quelle est la complexit de v rifier si un graphe G est Ds k colorable pour G quelconque Un mini gala r unit 5 filles et 5 garcons Sachant que chaque fille a Quelle est la meilleure complexit avec laquelle on sait v rifier si un d ja fait connaissance de exactement 3 des 5 garcons et chaque garcon a d ja fait connaissance de exactement 3 des 5 filles est il toujours possible de r partir les 10 en 5 couples fille gargon disjoints tel que chaque couple r unit deux personnes se connaissant d ja 24 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 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 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 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 28 Quel est le nombre maximu
4. m d ar tes que peut contenir un graphe K 40 sommets qui n a pas de clique de taille 5 29 Soit G un graphe sans triangle ni carr de diam tre 2 non r gulier f et avec un sommet de degr 7 Combien y a t il de sommets dans G REPONSE OUI NON OUI NON OUI NON OUI NON OUI NON Cadre pour des commentaires et ou pour justifier vos r ponses aux questions 27 28 et 29
Download Pdf Manuals
Related Search