Théorie des graphes : Graphes representations algorithmique m1
Télécharger PDFAlgorithmique — M1
TD1 : Graphes et représentations
Considérons un graphe G = (V, E) sans boucle triviale.
Exercice 1 : Donner une représentation du graphe ci-dessous au moyen d’une liste d’adjacence, puis au moyen d’une matrice d’adjacence.
Exercice 2 : Donner une représentation du même graphe (ci-dessus) en matrice d’incidence.
Quels problèmes rencontre-t-on ?
Les arêtes n’ont pas de nom ; il faut en donner.
Les boucles ! On décide de mettre pour cet exercice seulement un 2 en bu,e dans la matrice d’incidence, si e est une boucle autour du sommet u. Notons qu’on étend ainsi la définition standard.
Exercice 3 : Proposer un algorithme de construction de la matrice d’incidence à partir de la liste d’adjacence d’un graphe, puis à partir de sa matrice d’adjacence.
Pour construire la matrice d’incidence : tout d’abord on détermine sa taille et pour cela on compte le nombre d’arêtes du graphe. Ensuite, pour chaque arête on remplit la matrice (qui est au départ initialisée à 0).
Cas des listes d’adjacence :
Entrée : table de listes d’adjacence E de taille n
Variables : entier i initialisé à 0, sommet x, y
Début :
Pour x de 1 à n faire
Pour tout voisin y de x faire i++
fin du pour
fin du pour
B = matrice de taille n × i
i = 0
Pour x de 1 à n faire
Pour tout voisin y de x faire
i++
B(x, i) = -1
B(y, x) = 1
fin du pour
fin du pour
Fin.
Cas des matrices d’adjacence :
Entrée : matrice d’adjacence M de taille n
Variables : entier i initialisé à 0, sommet x, y
Début :
Pour x de 1 à n faire
Pour tout y de 1 à 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 à n faire
Pour tout y de 1 à 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.
Exercice 4 : Si BT désigne la transposée de B, que représente la matrice B × BT ?
La matrice M = B × BT est carrée de taille n.
De plus :
Pour tout i ≠ j, mi,j vaut le nombre d’arêtes existant entre les sommets i et j (indépendamment de l’orientation).
Pour tout i, mi,i vaut le degré de i.
Exercice 5 : Dans chacune des trois représentations, quel temps faut-il pour déterminer si deux sommets u et v donnés sont voisins ?
– Listes : O(d+(x)) (on parcourt la liste de u à la recherche de v)
– Matrice d’adjacence : O(1) (simple accès à M(u, v))
– Matrice d’incidence : O(m) (pour toute arête on teste bu,i et bv,i qui doivent être non nuls tous les deux)
Exercice 6 : Dans chacune des trois représentations, quel temps faut-il pour calculer le degré sortant d’un sommet ? Même question pour le degré entrant.
Degré sortant :
– Listes : O(d+(x)) (taille d’une liste, standard)
– Matrice d’adjacence : O(n) (compter les 1 dans la ligne de la matrice)
– Matrice d’incidence : O(m) (on compte pour toute arête les bu,i valant 1)
Degré entrant :
– Listes : O(m) (il faut parcourir toutes les listes et compter les listes où u apparaît)
– Matrice d’adjacence : O(n) (compter les 1 dans la colonne de la matrice)
– Matrice d’incidence : O(m) (on compte pour toute arête les bu,i valant -1)
Exercice 7 : Réécrire l’algorithme générique de parcours d’un graphe vu en cours de façon adaptée à chaque représentation. Quel est le temps d’exécution, à chaque fois ?
Seule la ligne « pour tout voisin v de u » est à réécrire.
– Listes :
C = u.tête
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 d’adjacence :
Pour v de 1 à n
Si M(u, v) = 1
... // calcul sur v
Fin si
Fin pour
Se fait en O(n) pour chaque sommet u donc en O(n2) en tout.
– Matrice d’incidence :
Pour e de 1 à m
Si b(u, e) = 1 // u est origine de e, cherchons la destination
Pour v de 1 à n
Si b(v, e) = -1
... // calcul sur v
Fin si
Fin pour
Fin si
Fin pour
La complexité estimée : O(nm) pour chaque sommet u donc en O(n2m2) en tout.
Exercice 8 : Considérons un graphe orienté G = (V, E). Un sommet est un puits universel si et seulement si dans la matrice d’adjacence, la ligne i ne contient que des 0 et la colonne i ne contient que des 1 sauf à l’intersection de la ligne i.
Étant donnée une représentation d’un graphe G = (V, E) par une matrice d’adjacence, proposer un algorithme permettant de déterminer s’il existe un puits universel.
Graphes et modélisation
Exercice 9 : Combien y a-t-il de circuits simples dans le graphe de sommets V = {vi, si, ti}, i ∈ [0..n-1] et d’arcs E = {(vi, si), (vi, ti), (si, vj), (ti, vj) avec j = 1 + i mod n}, i ∈ [0..n-1] ?
2n : le graphe se dessine comme un cycle de losanges. Les circuits contiennent tous les vi, et à chaque fois, pour passer de l’un à l’autre, il y a 2 possibilités, soit par le haut, soit par le bas. Bref, n choix binaires à faire.
Exercice 10 : Un passeur se trouve au bord d’une rivière avec un loup, une chèvre et une salade.
Comme vous le savez probablement, les loups mangent les chèvres mais pas les salades, les chèvres mangent les salades mais pas les loups, et les salades ne mangent personne.
Dans sa barque, le passeur ne peut transporter qu’un seul des trois protagonistes à la fois. Lorsqu’il est dans sa barque ou sur la rive opposée, il ne peut empêcher de carnage alimentaire.
On souhaite savoir s’il peut amener, sain et sauf, de l’autre côté de la rive le loup, la chèvre et la salade.
Si cela est possible, combien de traversées sont nécessaires ?
Pour répondre à ce problème, vous donnerez une modélisation par un graphe, et le reformulerez dans ce cadre.
Exercice 11 : Des étudiants A, B, C, D, E et F doivent passer des examens dans différentes disciplines, chaque examen occupant une demi-journée :
– Algorithmique : étudiants A et B.
– Compilation : étudiants C et D.
– Bases de données : étudiants C, E, F et G.
– Java : étudiants A, E, F et H.
– Architecture : étudiants B, F, G et H.
On cherche à organiser la session d’examen la plus courte possible.
Pour répondre à ce problème, vous donnerez une modélisation par un graphe, et le reformulerez dans ce cadre.
Graphes eulériens
Exercice 12 : Un circuit eulérien dans un graphe orienté est un circuit qui passe exactement une fois par chaque arc.
Soit G un graphe orienté sans sommet isolé. Démontrer que s’il existe un circuit eulérien dans G alors G est fortement connexe (il existe un chemin pour chaque couple de sommets u, w) et pour chaque sommet u, deg-(u) = deg+(u) (les degrés entrant et sortant sont égaux).
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éjà trouvé un cycle simple dans G alors que peut-on dire des degrés entrant et sortant de chaque sommet du graphe H obtenu à partir de G en supprimant dans G tous les arcs de ce cycle ?
Démontrer que G possède un circuit eulérien, donner un algorithme permettant de trouver ce circuit.
Un puits veut dire de degré sortant zéro, et universel qu’il voit tout le monde.
Trois façons de représenter un graphe
En listes : 1 : (1, 2, 3, 4) ; 2 : (2) ; 3 : (5, 6) ; 4 : (4, 3) ; 5 : (5, 3) ; 6 : (6, 5, 3)
Bien sûr, il s’agit en fait de listes chaînées !
FAQ
Qu’est-ce qu’un puits universel dans un graphe orienté ?
Un puits universel est un sommet dont le degré sortant est nul et qui est accessible depuis tous les autres sommets du graphe.
Comment construire une matrice d’incidence à partir d’une liste d’adjacence ?
On compte d’abord le nombre d’arêtes, puis on initialise une matrice de taille n × m (où n est le nombre de sommets et m le nombre d’arêtes). Ensuite, pour chaque sommet, on parcourt ses voisins et on remplit la matrice avec -1 et 1 selon l’orientation des arêtes.
Quelle est la différence entre un circuit simple et un circuit eulérien ?
Un circuit simple passe au plus une fois par chaque arc, tandis qu’un circuit eulérien passe exactement une fois par chaque arc du graphe.