NOM Prénom : .......................................... 30 mai 2007 Examen de
Contents
1. NOM Pr nom sise 30 mai 2007 Examen de graphes 3 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 arcs cas orient Pour les questions algorithmiques on suppose que les graphes sont donn s par leurs listes d adjacence N dans le cas non orient N dans le cas orient Les notes et documents de cours sont autoris s Exercice 1 QCM sur le cours et les expos s 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 Le terme O n d signe la meilleure complexit connue ce jour pour multiplier deux matrices n x n QUESTION REPONSE Consid rer la classe des graphes d intersection de rectangles les 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 La proposition suivante est elle vraie toute classe caract ris e par une famille infinie de mineurs interdits peut aussi tre caract ris e par une famille finie de mineurs interdits Quelle est la complexit du probl me consistant enlever le minimum de sommets un graphe non orient pour qu il devienne acyclique Donner l2. a meilleure complexit avec laquelle on sait calculer le car dinal max d un ind pendant pour les graphes de clique width lt 5 Avec quelles complexit s sait on r soudre le probl me de fermeture transitive d un graphe orient Est ce que le graphe de Petersen ci dessous est planaire AS Soit G V E non orient Parmi les deux familles suivantes lesquelles sont des matro des A AC E Ga V A est sans cycle B BC E Gg V B a au moins un cycle Dans le mod le d Erd s Renyi avec probabilit d avoir une ar te pour chaque paire de sommets quand n 00 quel est en moyenne le diam tre d un graphe n sommets Soit G un graphe biparti 10 sommets ayant un ind pendant de cardinal maximum avec 6 sommets quel est le cardinal maximum d un couplage Quelle est la meilleure complexit avec laquelle on sait v rifier si deux arbres n sommets non enracin s sont isomorphes Avec quelle complexit sait on calculer un cycle de longueur minimum O n O n n m NP dur Si on sait effectuer la multiplication dans l alg bre min de deux O n O n logn OR matrices n x n en O n avec quelle complexit sait on calculer les distances pour tout couple de sommets dans un graphe orient pond r sans cycle de poids strictement n gatif Est ce qu on peut exprimer l existence d une 4 coloration d un graphe avec une formule du langage logique 71 quantification sur les sommet
3. la pr sence ventuelle d autres ar tes qui elles ne sont pas modifi es Ces r ductions suppriment une ar te et ou un sommet chaque fois Pour avoir la r sistance quivalente entre s et t il faut r ussir appliquer ces transformations jusqu Pi D s rie J N o E fi x f parallele A ET x R Rz R E N toile triangle SR S R gt A i X R R _ l ce que le graphe soit r duit une seule ar te st Montrer pour le graphe ci dessous qu on peut appliquer les trois r gles jusqu obtenir le graphe r duit l ar te st les valeurs des r sistances sont omises car ne jouant aucun r le dans le succ s ou pas de la m thode Est ce que les trois r gles pr sent es permettent toujours de se ramener une unique ar te st pour tout graphe connexe et tout couple s t de sommets D montrer le th or me suivant pour G V E et s t V en supposant que G V E U st est 2 connexe Pour les trois r gles pr sent es il existe une suite de r ductions transformant G en l ar te st si et seulement si G V E U st est de largeur arborescente lt 3 Indication Utiliser la caract risation tw G min w H 1 H surgraphe triangul de G Pour le sens construire un bon surgraphe de G qui soit triangul Pour le sens lt construire la suite en travaillant sur un surgraphe triangul de G Remarque dans le cas g n ral plut t que de g
4. n rer puis r soudre de gros syst mes lin aires les meilleurs algorithmes utilisent la th orie des graphes Question subsidiaire Une derni re classe pour la route 1 pt En relachant les conditions sur la classe des divisibles on d finit la classe des splits G V E est un split s il existe une partition des sommets V IU K IN K f telle que T soit un ind pendant et K une clique Donner une caract risation des splits par une famille finie de sous graphes induits interdits Remarque exceptionnellement pas de justification demand e pour cette derni re question vous pouvez juste donner votre proposition
5. pouvez Justifier la correction de votre algorithme Exercice 4 Calcul de r sistance dans les r seaux lectriques 4 pts Vous avez s rement d j t amen s calculer la r sistance quivalente entre deux points s et t s t d un r seau lectrique qui est un graphe non orient G V E o chaque ar te xy porte une r sistance Rzy gt 0 Le mot graphe d signera ventuellement un multigraphe s il y a des r sistances en parall le entre deux sommets Pour rappel entre s et t un tel r seau compos uniquement de r sistances se comporte comme une unique r sistance dont on cherche la valeur Une mani re de r soudre le probl me est d introduire les variables izy intensit et uxy tension pour xy E et d crire un nombre suffisant d quations partir de la loi d Ohm uzy Rryiry et des lois de Kirchhoff loi des n uds loi des mailles On peut ainsi se ramener la r solution d un syst me d quations lin aires dont on tire la r sistance quivalente Une autre m thode consiste r aliser une suite de transformations locales qui rem placent chaque fois un morceau du r seau par un nouveau morceau au comportement quivalent mais de taille plus petite La figure ci dessous pr sente trois r gles classiques de transformation avec respectivement R R R r duction s rie t F r duction parall le et S R1R2 R2R3 R3R1 r duction toile triangle Les pointill s indiquent
6. s et les ensembles de sommets tests d appartenance et d adjacence op rations logiques de base Exercice 2 Coloration de graphes particuliers 6 pts On rappelle qu une technique pour calculer une coloration valide des sommets d un graphe consiste prendre une s quence des sommets puis colorer les sommets dans l ordre de la s quence en donnant comme couleur le plus petit entier pas utilis parmi les voisins d j color s coloration goutonne Si G est un cographe montrer que pour n importe quelle s quence des sommets la coloration gloutonne est optimale c d utilise exactement x G couleurs Si G est triangul monter qu il existe une s quence des sommets telle que la coloration gloutonne est optimale Exercice 3 Une nouvelle esp ce pour le Zoo des Graphes 4 pts Un graphe G V E est divisible s il existe une partition des sommets V TU K INK telle que I soit un ind pendant et K une clique et telle que tout sommet de K a au moins un voisin dans J et aucun des sommets de I n est reli tous les sommets de K La figure ci dessous donne un exemple Clique see Est ce que la classe des divisibles peut tre caract ris e par une famille de mineurs interdits Est ce que la classe des divisibles est incluse dans la classe des cographes Et dans la classe des graphes triangul s Donner un algorithme de reconnaissance des divisibles avec la meilleure complexit que vous
Download Pdf Manuals
Related Search