Algorithmique M1 TD 1 : Graphes et repr esentations 1 Trois fa cons de repr esenter un graphe

1 4 3 6 2

Exercice 1 : Donner une repr esentation du graphe ci-dessus au moyen dune liste dadjacence, puis au moyen dune matrice dadjacence. Consid erons un graphe G = (V, E ) sans boucle triviale. On appelle matrice dincidence du graphe G, la matrice a ` |V | lignes et |E | colonnes, B = (bi,j ) d enie par : ete j part du sommet i 1 si lar bi,j = 1 si lar ete j arrive dans sommet i 0 sinon. Exercice 2 : Donner une repr esentation du m eme graphe (ci-dessus) en matrice dincidence. Quels probl` emes rencontre-t-on ? Exercice 3 : Proposer un algorithme de construction de la matrice dincidence a ` partir de la liste dadjacence dun graphe, puis a ` partir de sa matrice dadjacence. Exercice 4 : Si B T d esigne la transpos ee de B , que repr esente la matrice BB T ?

Algorithmique sur chacune des repr esentations

esentations, quel temps faut-il pour d eterminer si Exercice 5 : Dans chacune des trois repr deux sommet u et v donn es sont voisins ? Exercice 6 : Dans chacune des trois repr esentations, quel temps faut-il pour pour calculer le degr e sortant dun sommet ? M eme question pour le degr e entrant. Exercice 7 : R e- ecrivez lalgorithme g en erique de parcours dun graphe vu en cours de fa con adapt ee a ` chaque repr esentation. Quel est le temps dexecution, a ` chaque fois ?

Exercice 8 : Consid erons un graphe orient e G = (V, E ). Un sommet v est un puits universel 1 sil est de degr e entrant |V | 1 et de degr e sortant 0. Etant donn ee une repr esentation dun graphe G = (V, E ) par une matrice dadjacence, proposer un algorithme permettant de d eterminer sil existe un puits universel.

Graphes et mod elisation

Exercice 9 : Combien y a-t-il de circuits simples dans le graphe de sommets V = {vi , si , ti }, i [0..n 1] et darcs E = {(vi , si ), (vi , ti ), (si , vj ), (ti , vj ) avec j = 1 + i mod n}, i [0..n 1] ? ere avec un loup, une ch` evre et une Exercice 10 : Un passeur se trouve au bord dune rivi` salade. Comme vous le savez probablement, les loup mangent les ch` evres mais pas les salades, les ch` evres mangent les salades mais pas les loups, et les salades ne mangent personne. Dans sa barque, le passeur ne peut transporter quun seul des trois protagonistes a ` la fois. Lorsquil est dans sa barque ou sur la rive oppos ee, il ne peut emp echer de carnage alimentaire. On souhaite savoir sil peut amener, sains et saufs, de lautre c ot e de la rive le loup, la ch` evre et la salade. Si cela est possible, combien de travers ees sont n ecessaires ? Pour r epondre a ` ce probl` eme, vous en donnerez une mod elisation par un graphe, et le reformulerez dans ce cadre. Exercice 11 : Des etudiants A, B , C , D, E et F doivent passer des examens dans di erentes disciplines, chaque examen occupant une demi-journ ee : Algorithmique : etudiants A et B . Compilation : etudiants C et D. Bases de donn ees : etudiants C , E , F et G. Java : etudiants A, E , F et H . Architecture : etudiants B , F , G et H . On cherche a ` organiser la session dexamen la plus courte possible. Pour r epondre a ` ce probl` eme, vous en donnerez une mod elisation par un graphe, et le reformulerez dans ce cadre.

Graphes euleriens

Exercice 12 : Un circuit eul erien dans un graphe orient e est un circuit qui passe exactement une fois par chaque arc. Soit G un graphe orient e sans sommet isol e. D emontrer que sil existe un circuit eul erien dans G alors G est fortement connexe (il existe un chemin u w pour chaque couple de sommets u, w) et pour chaque sommet u deg (u) = deg+ (u) (les degr es sortant et entrant sont egaux). Exercice 13 : Inversement, supposant que G est un graphe fortement connexe et pour chaque sommet u, deg (u) = deg+ (u). Comment trouver dans ce graphe un cycle simple ? (Un cycle simple passe au plus une fois par un arc.) Si on a d ej` a trouv e un cycle simple dans G alors quest-ce que nous pouvons dire de degr es entrant et sortant de chaque sommets du graphe H obtenu a ` partir de G en supprimant dans G tous les arc de ce cycle ? D emontrer que G poss` ede un circuit eul erien, donner un algorithme permettant de trouver ce circuit.

1 puits

veut dire de degr e sortant z ero, et universel quil voit tout le monde

Trois fa cons de repr esenter un graphe

3 : (5,6)

En listes : 1 : (1,2,3,4) ; 2 : (2) 4 : (4,3) ; 5 : (5,3) 6 : (6,5,3) Bien s ur, il sagit en fait de listes cha n ees !

1 2 En matrice dadjacence (z eros omis pour plus de clart e) 3 4 5 6

1 1

2 1 1

3 1

4 1

1 1 1 1 1 1 1

Correction 2 : On rencontre deux dicult es : Les ar etes nont pas de nom ; il faut en donner Les boucles ! On d ecide de mettre pour cet exercice seulement un 2 en bu,e dans la matrice dincidence, si e est une boucle autour du sommet u. Notons quon etend ainsi la d enition standard. a b c d e f g h i j k l m n 1 2 -1 -1 -1 2 1 2 3 1 -1 -1 1 1 1 4 1 2 -1 5 1 2 -1 1 6 1 2 -1 -1 Correction 3 : Pour construire la matrice dincidence : tout dabord on d etermine sa taille et pour cela on compte le nombre dar etes du graphes. Ensuite, pour chaque ar ete on remplit la matrice (qui est au d epart initialis ea ` 0). Cas des listes dadjacence :
Entr ee: tableau de liste dadjacence E de taille $n$ Variables: entier i initialis e a ` 0 sommet x,y

D ebut: Pour x de 1 a ` n faire Pour tout voisin de y de x faire i++ fin du pour fin du pour B = matrice de taille n*i i=0 Pour x de 1 a ` n faire Pour tout voisin de y de x faire i++ B(x,i)=-1 B(y,x)=1 fin du pour fin du pour Fin. Cas des matrices dadjacence :

Entr ee: matrice dadjacence M de taille $n$ Variables: entier i initialis e a ` 0 sommet x,y D ebut: Pour x de 1 a ` n faire Pour tout y de 1 a ` n faire si M(x,y)=1 faire i++ fin du si fin du pour fin du pour B = matrice de taille n*i i=0 Pour x de 1 a ` n faire Pour tout y de 1 a ` n faire si M(x,y)=1 faire i++ B(x,i)=-1 B(y,x)=1 fin du si fin du pour fin du pour Fin.

Correction 4 : La matrice M = BB T = (mi,j ) est carr e de taille n. De plus : nbX aretes Pour tout i = j , mi,j = bi,k bj,k vaut le nombre dar etes existant entre les sommets i et j
k=1

(ind ependamment de lorientation) nbaretes X bi,k bi,k vaut le degr e de i. Pour tout i, mi,i =
k=1

Algorithmique sur chacune des repr esentations

Correction 5 : Listes : O(d+ (x)) (on parcours la liste de u a ` la recherche de v ) Matrice dadjacence : O(1) (simple acc` es a ` Eu,v ) Matrice dincidence : O(m) (pour toute ar ete i on teste bui et bvi qui doivent etre non-nuls tous les deux) Correction 6 : Degr e sortant : Listes : O(d+ (x)) (taille dune liste, standard) Matrice dadjacence : O(n) (compter les 1 dans la u` eme ligne de la matrice) Matrice dincidence : O(m) (on compte pour toute ar ete i les bui valant 1) Degr e entrant : Listes : O(m) (il faut parcourir toutes les listes et compter les listes o` u u appara t) Matrice dadjacence : O(n) (compter les 1 dans la u` eme col de la matrice) Matrice dincidence : O(m) (on compte pour toute ar ete i les bui valant 1)

Correction 7 : Seule la ligne pour tout voisin v de u est a ` r e ecrire Listes : C = u.tete Tant que C != null v = C.val ... // calcul sur v Fin tant que Se fait en O(d+ (u)) pour chaque sommet u. Chaque sommet est vu une fois. On est donc en O(n + m) EN TOUT. Matrice dadjacence : Pour v de 1 a n Si E(u,v) = 1 ... // calcul sur v Fin si Fin pour Se fait en O(n) pour chaque sommet u donc O(n2 ) en tout. Matrice dincidence : Pour e de 1 a m Si b(u,e) = 1 // u origine de e, cherchons la destination Pour v de 1 a n Si b(v,e) = -1 ... // calcul sur v Fin si Fin pour Fin si Fin pour La complexit e est immonde : O(nm) pour chaque sommet u donc O(n2 m2 ) en tout. Correction 8 : i est un puits universel si et seulement si dans la matrice la ligne i ne contient que des 0 et la colonne i ne contient que des 1 sauf a ` lintersection de la ligne i. On peut donc tester de fa con exhaustive, ce qui prend un temps quadratique en |V |.

Graphes et mod elisation

Correction 9 : 2n , le graphe se dessine comme un cycle de losanges. Les cycles contiennent tout les vi , et a ` chaque fois, pour passer de lun a ` lautre il y a 2 possibilit es, soit par le haut, soit par le bas. Bref n choix binaires a ` faire. Correction 10 : On construit un graphe correspondant a ` l evolution du syst` eme. Il sut alors de regarder sil y a un chemin de la conguration initiale a ` la conguration nale. On a le graphe (non orient e) page suivante. Correction 11 : On construit un graphe (non orient e ici) dans lequel chacune des disciplines par un sommet, et relier par des ar etes les sommets correspondant aux examen incompatibles (ayant des etudiants en commun) Il sagit alors de colorier chacun des sommets du graphes en utilisant le moins de couleurs possible, des sommets voisins ne pouvant etre de la m eme couleur. Ici trois couleurs susent, et on ne peut faire mieux. Le probl` eme est dans le cas g en eral NP-complet, donc dur ! Java A Algo B Archi F,H F,G E,F BD C Compil

PCLS,C LS,PC PLS,C L S,PLC C PSC,L S C,PLS PC,LS B -,PLCS L S L,PSC C LPC,S

Fig. 1 Corrig e de lexercice 7

Graphes euleriens

Correction 12 : Il sut de montrer que le circuit passe par tous les sommets. Si ce n etait pas le cas, il existerait un sommet incident a ` aucun arc (puisque le circuit les contient tous) donc isol e. Le circuit rentre autant de fois dans un sommet quil en sort (loi des nuds) donc les degr es entrants et sortants sont les m emes. Correction 13 : Remarquons que tout graphe simplement connexe avec deg (u) = deg+ (u) est fortement connexe. Toute marche dans un tel graphe revient au point de d epart. En eet, une marche qui grille les ar etes d eja vues maintient la propri et e de l egalit e des degr es, sauf pour le sommet de d epart. Le sommet de d epart est toujours accessible, car on ne si on deconnecte (simplement) le graphe la marche est dans la composante qui le contient (elle a franchi un nombre pair de fois la fronti` ere). D` es quon a bouvcl e une marche, il sut dn recommencer une en partant dun sommet du sycle ayant des arcs non-grill es : on reviendra a ` ce sommet et on a ainsi agrandi le cycle.