owned this note
owned this note
Published
Linked with GitHub
<script
src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"
type="text/javascript">
</script>
# Rapport des TP de théorie des graphes
Ce rapport présente notre travail effectué dans le cadre du module de Théorie des Graphes à l'ENSIIE.
L'ensemble du rapport et des travaux pratiques ont été réalisés par Yanis HESSINI, Michel KADILAR et Reda EZ-ZRIOULI.
# Séance 1
## Fermeture transitive
### Définition
La fermeture transitive F d’un graphe G est également un graphe, où pour tout sommet x du graphe, il existe un chemin vers tout sommet y.
Un chemin d’origine x et d’extrémité y, est défini par une suite finie d’arcs consécutifs, reliant x à y. En d’autres termes, un chemin de x à y peut passer par différents sommets pour aller de x à y.
*Ci-dessous un schéma d’un graphe G et de sa fermeture transitive :*
### Algorithme de résolution
Afin de déterminer la fermeture transitive d'un graphe, nous pouvons utiliser **l'algorithme de Roy-Warshall.**
Cet algorithme utilise la matrice d'adjacence en entrée, et retourne en sortie une autre matrice d'adjacence, celle de la fermeture transitive.
Ci-dessous le pseudo-code de cet algorithme :
```
Fonction ROY_WARSHALL(M) :
F = Graphe représenté par M
POUR tout sommet du graphe faire :
Relier chaque prédécesseur dans F à chaque successeur dans F
F = Le graphe obtenu par la modification effectuée
FIN POUR
```
Le principe de l'algorithme est le suivant : il copie au départ le graphe qui lui est donné dans une autre variable, ici appelée F.
A chaque itération de la boucle, on utilise un sommet qui servira de "pivot".
L'algorithme calcule une suite de matrice $C_k$, pour $k = 0, 1,..., N$.
### Implémentation en Python
L'algorithme en Python est le suivant :
```python
def roy_marshall(matrix):
n = len(matrix)
m_adj = matrix.copy()
for k in range(n):
for i in range(n):
for j in range(n):
m_adj[i][j] = m_adj[i][j] or (m_adj[i][k] and m_adj[k][j])
return m_adj
```
La complexité de l'algorithme est de $O(N^3)$, avec $N$ le nombre de sommets du graphe. Nous avons un parcours du graphe avec deux boucles (i et j), puis nous le faisons k fois pour s'assurer que la propriété suivante est respectée :
**La matrice $C_k$ vérifie que $C_k[i, j] = 1$ s'il existe un chemin de i à j passant uniquement par des sommets inférieurs ou égaux à k, et 0 dans le cas contraire.**
A la fin de l'algorithme nous avons $k = N$, donc cela signifie qu'il existera un chemin d'un sommet x à un sommet y, passant par un ou plusieurs sommets du graphe.
### Tests et résultats obtenus
Nous avons réalisé plusieurs tests.
Le premier, sur le graphe présenté plus haut :
L'algorithme a résulté du graphe de fermeture transitive suivant :
Nous pouvons vérifier l'algorithme en vérifiant que pour chaque paire de sommet il existe un chemin :
```
Paire 0, 1 -> Arête [0, 1]
Paire 0, 2 -> Arête [0, 2]
Paire 0, 3 -> Arête [0, 3]
Paire 0, 4 -> Arête [0, 4]
Paire 1, 2 -> Arête [2, 1]
Paire 1, 3 -> Arête [1, 3]
Paire 1, 4 -> Arête [1, 4]
Paire 2, 3 -> Arête [2, 3]
Paire 2, 4 -> Arête [2, 4]
Paire 3, 4 -> Arête [3, 4]
```
Le choix des sommets est **commutatif** : la paire [0, 1] équivaut aussi à la paire [1, 0]. Cela signifie que si un chemin existe pour la première paire, ce même chemin est valable pour l'autre paire avec cet algorithme (et pour la définition de fermeture transitive en général).
## Parcours en profondeur
### Définition
Le parcours en profondeur (Depth-First Search en anglais) est un algorithme de parcours de graphe. Cet algorithme permet de trouver **l'ensemble des sommets accessibles depuis un sommet *S* donné**, c'est-à-dire ceux vers lesquels il existe un chemin partant de *S*.
Ci-dessous une image animée qui présente le principe de l'algorithme.
### Algorithme de résolution
L'algorithme de résolution, en pseudo-code, est le suivant :
```
Fonction PARCOURS_PROFONDEUR(L, M, S) :
TANT QUE (la liste L est plus petite que le nombre de colonnes dans M
ET que S n'est pas dans L)
Ajouter S dans L
POUR TOUT sommet i du graphe
SI il y a une arête de S vers i
PARCOURS_PROFONDEUR(L, M, i)
FIN SI
FIN POUR
FIN TANT QUE
```
*L est une liste, qui contient les sommets visités.
M est la matrice d'adjacence du graphe.
S est le sommet de départ choisi sur lequel appliquer l'algorithme.*
----
L'algorithme est récursif. A chaque fois que l'algorithme repère une arête entre le sommet itéré et le sommet S, il continue d'appeler la fonction, qui va ajouter le sommet dans la liste L.
Dès qu'il n'y a plus d'arête pour avancer vers un autre sommet, la fonction se termine et remonte. Elle redescend ensuite vers un autre chemin si elle en trouve un. En effet, au tout départ, l'algorithme effectue une boucle sur les sommets du graphe. Il commence à trouver des arêtes et continue de parcourir un certain chemin, jusqu'à que ce ne soit plus possible. Il remonte alors, et la première boucle continue d'itérer sur les sommets, pouvant découvrir d'autres chemins sur lequels parcourir en profondeur.
Les sommets sont cependant ajoutés que s'il ne sont pas déjà dans L, auquel cas nous nous retrouverions avec une liste avec une répétition des sommets (il s'agirait de la liste représentant tous les sommets par lesquels l'algorithme est passé.)
### Implémentation en Python
Ci-dessous l'implémentation en Python de l'algorithme que nous avons utilisé.
```python
def parcours_profondeur(visited, matrix_graph, node):
while len(visited) < len(matrix_graph) and node not in visited:
visited.append(node)
for i in range(len(matrix_graph)):
if matrix_graph[node][i] == 1:
parcours_profondeur(visited, matrix_graph, i)
```
Afin de vérifier que la liste L est plus petite que le nombre de colonnes dans M, nous utilisons la fonction `len()` de Python.
Pour parcourir les sommets du graphe, nous utilisons une boucle sur la taille de la matrice d'adjacence. Cela permet ensuite de faire la vérification de l'arête entre le sommet *i* et le sommet *node*.
La fonction prend en entrée un tableau appelé `visited`, permettant de stocker les sommets visités.
Elle prend ensuite la matrice d'adjacence du graphe. Enfin, elle prend le sommet sur lequel commencer le parcours en profondeur.
La complexité de l'algorithme est de $O(S + A)$ avec $S$ le nombre de sommets et $A$ le nombre d'arêtes.
A noter que $A$ peut varier entre $O(1)$ et $O(S^2)$, selon la densité du graphe.
Nous avons développé une fonction secondaire, qui utilise la fonction du parcours en profondeur pour récupérer la liste des sommets de tout le graphe :
```python=
def liste_sommets(visited, matrix_graph):
for i in range(len(matrix_graph)):
if i not in visited:
parcours_profondeur(visited, matrix_graph, i)
visited.sort()
```
La fonction effectue simplement un parcours en profondeur sur chaque colonne de la matrice d'adjacence du graphe. Cela a pour effet de faire un parcours en profondeur sur tous les sommets.
La liste des sommets est ensuite triée par ordre croissant.
### Tests et résultats obtenus
Les fonctions ont été testées sur le graphe suivant :
Nous avons obtenu le résultat suivant :
```
Sommets parcourus du graphe depuis le sommet 2 : [2, 3, 4]
Sommets du graphe : [0, 1, 2, 3, 4]
```
Commencer le parcours à partir du sommet deux amène l'algorithme vers le sommet 3 puis 4. Il ne va pas chercher les sommets 0 et 1, car il n'y a pas de chemin de 2 vers ces arêtes.
Le résultat obtenus pour le parcours depuis le sommet 2 est donc cohérent. Enfin, nous pouvons aussi voir que la liste des sommets est triée et fonctionnelle.
## Composantes fortement connexes
### Définition
En théorie des graphes, une composante fortement connexe d'un graphe **orienté** G est un sous-graphe possédant la propriété suivante, et qui est maximal pour cette propriété : pour tout couple (u, v) de nœuds dans ce sous-graphe, il existe un chemin de u à v.
En d'autres termes, dans une composante fortement connexe, il existe un chemin entre chaque paire de sommet.
Ci-dessous un exemple d'un graphe possédant 3 composantes fortement connexes :
### Algorithme de résolution
Afin de déterminer les composantes fortement connexes d'un graphe, nous pouvons utiliser une méthode de marquage des sommets.
Ci-dessous l'algorithme de recherche des composantes fortement connexes :
```
Fonction F-Connexe(M)
Récupérer la liste des sommets dans une liste E
TANT QUE E n'est pas vide
Marquer + et - un sommet S de E
TANT QUE le marquage est possible
Marquer par + tout successeur (non encore marqué par +)
d'un sommet déjà marqué +.
Marquer par - tout prédécesseur (non encore marqué par -)
d'un sommet déjà marqué -.
FIN TANT QUE
Récupérer l'ensemble des sommets marqués + et - dans une liste C
Supprimer les sommets de cet ensemble de la liste E
FIN TANT QUE
```
L'algorithme prend en entrée la matrice d'adjacence du graphe.
Le principe de l'algorithme est le suivant : nous commençons d'un sommet, qui est marqué par un + et -. Nous marquons ensuite les successeurs et prédecesseurs de ce sommet. Nous continuons ensuite sur chaque sommet marqué de marquer ses prédécesseurs et successeurs. L'algorithme de marquage s'arrête lorsque tous les sommets déjà marqué + n'ont plus de successeurs non marqués, et idem pour le marquage des -.
Nous pouvons remarquer de la récursivité, puisque nous effectuons le même procédé de marquage pour un sommet, qui en marque d'autres, qui eux même en marquent.
### Implémentation en Python
Notre implémentation en Python est la suivante :
```python
def compo_fort_connexe(matrix_graph):
# Parcours en profondeur du graphe
visited_nodes = []
compos_fc = []
liste_sommets(visited_nodes, matrix_graph)
sommets_plus = []
sommets_moins = []
visited_nodes = list(set(visited_nodes))
node_list = visited_nodes.copy()
while len(visited_nodes) > 0:
n = list(visited_nodes)[0]
sommets_plus.append(n)
sommets_moins.append(n)
marquer_successeurs(matrix_graph, n, visited_nodes, node_list, sommets_plus)
marquer_predecesseurs(matrix_graph, n, visited_nodes, node_list, sommets_moins)
inter = list(set(sommets_plus) & set(sommets_moins))
compos_fc.append(inter)
visited_nodes = list(set(visited_nodes) - set(inter))
sommets_plus = []
sommets_moins = []
return compos_fc
```
Le plus gros de l'algorithme ici est le marquage des successeurs et des prédécesseurs. Ces fonctions font les marquage + et - tant que c'est possible.
L'implémentation du marquage des successeurs est la suivante :
```python
def marquer_successeurs(matrix_graph, node, visited_nodes, node_list, sommets_plus):
successeurs = []
# Récupérer la liste des successeurs du noeud
for i in range(len(matrix_graph)):
if matrix_graph[node][i] == 1:
successeurs.append(i)
for u in successeurs: # Parcourir les successeurs de v
if (u in visited_nodes) and (not u in sommets_plus): # Si un successeur u n'est pas marqué +
sommets_plus.append(u) # Marquer u avec +
# Marquer les successeurs de u avec +
marquer_successeurs(matrix_graph, u, visited_nodes, node_list, sommets_plus)
```
Cette fonction effectue le marquage + des sommets. Elle prend en entrée :
- Matrice d'adjacence du graphe
- Noeud sur lequel le marquage commence
- Liste des noeuds restant (équivalent de E dans l'algorithme)
- Liste des sommets du graphe
- Liste des sommets marqués +
L'algorithme s'appuie sur la récursion pour effectuer le marquage *tant que c'est possible*, comme spécifié dans le pseudo-code.
En effet, lorsque l'algorithme marque un nouveau sommet, il va effectuer un autre appel récursif pour essayer de marquer les successeurs de ce sommet marqué. Si ce n'est plus possible (c'est-à-dire si il n'y a plus de successeurs non marqués), la fonction se terminera et remontera.
L'implémentation du marquage des prédécesseurs est la suivante :
```python
def marquer_predecesseurs(matrix_graph, node, visited_nodes, node_list, sommets_moins):
successeurs = []
for u in node_list: # Parcourir les éléments u du graphe
if u in visited_nodes:
successeurs = []
# Récupérer la liste des successeurs du noeud
for i in range(len(matrix_graph)):
if matrix_graph[u][i] == 1:
successeurs.append(i)
# si node est un successeur de u et u n'est pas marqué
if (node in successeurs) and (u not in sommets_moins):
# si node est un successeur de u, alors u est un prédecesseur de node,
# donc il faut marquer u
sommets_moins.append(u) # Marquer u avec -
# Marquer les prédécesseurs de u avec -
marquer_predecesseurs(matrix_graph, u, visited_nodes, node_list,
sommets_moins)
```
Cette fonction effectue le marquage - des sommets. Elle prend en entrée :
- Matrice d'adjacence du graphe
- Noeud sur lequel le marquage commence
- Liste des noeuds restant (équivalent de E dans l'algorithme)
- Liste des sommets du graphe
- Liste des sommets marqués -
L'algorithme s'appuie également sur la récursion pour effectuer le marquage *tant que c'est possible*, comme spécifié dans le pseudo-code.
Le principe est le même que pour le marquage des successeurs, mais ici il est codé pour les prédecesseurs et les -.
### Tests et résultats obtenus
L'algorithme a été testé sur le graphe suivant (le même que le graphe de la définition):
Le résultat sur ce graphe a été :
```
Composantes fortement connexes du graphe : [[0, 1, 4], [2, 3, 7], [5, 6]]
```
Nous avons donc 4 composantes fortement connexes dans ce graphe.
Le résultat est correct, puisque cela correspond aux composantes fortement connexes de la définition.
## Séance 2 : Tri topologique
### DEFINITION A REFAIRE
Il s’agit ici de résoudre le problème d’une mise en ordre topologique des sommets d’un graphe orienté acyclique (respectivement d’un graphe non-orienté sans circuit). Une mise en ordre topologique des sommets signifie que nous allons classer les sommets tels que ∀(u, v) ∈ A, u apparaît avant v. Grâce à cela, nous pouvons déterminer des “niveaux” correspondant chacun à tous les sommets ayant le même nombre de successeurs. Par exemple, si nous avons 4 sommets, un premier qui a 1 successeur. Pour cela, nous utilisons un algorithme nommé le “tri topologique”.
### Descriptif de l’algorithme de résolution :
Pseudo-code :
```
tri_topologique(liste_successeurs): les niveaux et les sommets associés
Y <- liste de tous les sommets
N = 1
TANT QUE Y n'est pas vide:
mettre sur le niveau N tous les sommets de Y n'ayant
aucun prédécesseur dans Y
Xn <- ensemble des sommets de niveau N
Y <- Y - Xn #On enlève tous les sommets désormais du
niveau N de l'ensemble Y
N = N + 1
```
L’algorithme appliqué consiste à parcourir l’ensemble Y de sommets du graphe courant étudié, et, tant qu’il n’est pas vide, on va mettre tous les sommets sans successeur sur le même niveau N. Tous les sommets sélectionnés et mis sur le même niveau durant l’itération courante sont ensuite enlevés de l’ensemble Y des sommets. Nous réitérons ensuite en plaçant les nouveaux sommets sans successeur au niveau N+1. Et ainsi de suite, jusqu’à ce que tous les sommets de l’ensemble Y aient été traités.
### Descriptif de l’implémentation en Python :
Pseudo-code de notre implémentation :
```
tri_topologique(liste_successeurs): les niveaux et les sommets associés
Y <- liste de tous les sommets
N = 1
tableau_niveaux = []
TANT QUE Y n'est pas vide:
tab = []
POUR i de 0 à longueur(liste_successeurs):
# On ajoute les sommets sans sucesseur à une liste
Si liste_successeurs[i] != None
et que longueur(liste_successeurs[i]) == 0:
Ajouter i à tab
# Alors le sommet i n'a pas de successeur
dans le graphe étudié
indice = 0
TANT QUE indice < longueur(tab):
On parcourt la liste_successeurs pour enlever de
chaque sous-liste les sommets présents dans
la liste tab.
# On enlève les sommets sélectionnés
(sans successeurs) des sous-listes de successeurs
des autres sommets
On enlève les sommets sans successeurs sélectionnés
de Y, la copie des sommets du graphe
N = N + 1
Ajouter à tableau_niveaux au niveau courant les sommets
sélectionnés
RENVOYER tableau_niveaux
```
Explication du code python :
Tout d’abord, nous n’avons utilisé aucune bibliothèque externe pour cet exercice. La fonction tri_topologique prend en entrée une liste de liste représentant les successeurs et renvoie en sortie une liste de liste, chaque liste contenant les sommets du niveau à l’indice courant.
Par exemple, si la fonction retourne : [ [1], [2,3], [4,5,6,7]], alors cela signifie que le sommet 1 se trouve au niveau 1, que les sommets 2 et 3 se trouvent au niveau 2 et que les sommets 4,5,6,7 se trouvent au niveau 3.
Le cœur de notre implémentation repose sur la liste de liste de successeurs.
Nous créons une liste Y qui contient tous les sommets du graphe étudié. Nous parcourons ensuite la liste de liste de successeurs, nous ajoutons tous les sommets sans successeur (on les reconnaît grâce à une liste de successeur de taille 0) à une nouvelle liste nommée “tab”.
```python=
y = []
for i in range(len(liste_successeurs)):
y.append(i)
n = 1
niveaux = []
while len(y) > 0:
tab = []
for i in range(len(liste_successeurs)):
if liste_successeurs[i] is not None and len(liste_successeurs[i]) == 0 :
tab.append(i)
liste_successeurs[i] = None
```
Le but est désormais d’enlever les sommets ajoutés à la liste tab (qui n’ont donc aucun successeur) des sous-listes de successeur des autres sommets (car ces sommets vont être enlevés de la liste des sommets, l’ensemble Y). Pour cela, nous mettons les sommets déjà sélectionnés à la valeur None, nous parcourons la liste “tab” et les sous-listes de successeurs du départ, et on enlève tous les éléments appartenant à tab des sous-listes de successeurs.
```python=
indice = 0
while indice < len(tab):
for k in range(len(liste_successeurs)):
if liste_successeurs[k] is not None:
if tab[indice] in liste_successeurs[k]:
liste_successeurs[k].remove(tab[indice])
if tab[indice] in y:
y.remove(tab[indice])
indice += 1
```
De cette façon, ces sommets sélectionnés sont comme “enlevés” du graphe, et nous aurons donc de nouveau des sommets qui se retrouveront sans successeur.
Nous arrivons à la fin de la boucle principale, qui va alors recommencer. Mais avant cela, on incrémente le niveau et on ajoute les sommets sélectionnés à une liste de niveaux.
```python=
n += 1
niveaux.append(tab)
```
On incrémente le niveau, on resélectionne parmi les sommets de l’ensemble Y ceux sans successeur, on les ajoute au niveau N et on les enlève de l’ensemble Y, etc.
A la fin de l’algorithme, tous les sommets du graphe étudié ont un niveau, et tout cela est renvoyé dans une liste de listes où tous les sommets de niveau i ont pour indice i.
```python=
return niveaux
```
La complexité de l'implémentation est de $O(V * 2S)$ avec $S$ le nombre de sommets (parcours de la grande liste des successeurs) et $V$ le nombre de fois que l'on va itérer sur la boucle while principale (on ne peut pas prévoir un nombre exact de fois, car cela dépends du graphe étudié et des suppressions réalisées)
Cette complexité ne prend pas en compte les suppressions que l'on réalise, car on ne peut pas prévoir combien d'éléments vont être supprimés à chaque itération, sachant que ce nombre est variable, on peut en supprimer un seul comme on peut en supprimer des milliers dans un très gros graphe.
### Instances de test :
Nous avons testé l'implémentation sur deux graphes :
* Le premier (sous forme de liste de successeurs : [[1, 2], [2], [3], [4], []])
Soumis à notre implémentation, il nous donne le résultat suivant :
[[4], [3], [1, 2], [0]], autrement dit, le sommet 4 au niveau 1, le sommet 3 au niveau 2, etc.
Cela semble correct !
* Le deuxième : [[1, 2], [3], [3], [4], []]
Soumis à notre implémentation, il nous donne le résultat suivant :
[[4], [3], [1, 2], [0]]
## Séance 3 : Coloration des sommets d'un graphe
### Définition du problème :
Il s’agit ici de résoudre le problème du nombre chromatique, c’est-à-dire du nombre minimum de couleurs qu’on doit utiliser afin de colorier tous les sommets du graphe en s’assurant que deux sommets adjacents ne soient pas de la même couleur.
### Descriptif de l’algorithme de résolution :
Nous allons utiliser ici un algorithme bien connu, appelé “algorithme de Welsh-Powell”, qui consiste à trier dans l’ordre décroissant les sommets selon leur degré (c’est-à-dire leur nombre de voisins), puis de sélectionner d’abord un sommet, de parcourir tous les autres sommets, de les sélectionner s’ils ne sont pas voisins de sommets déjà sélectionnés, et enfin de colorier l’ensemble des sommets sélectionnés, qui sont forcément tous non-voisins les uns des autres, de la même couleur.
A l’itération suivante, nous enlevons les sommets précédemment séléctionnés de l’ensemble étudié, nous changeons de couleur, et nous recommençons à séléctionner les sommets non-voisins les uns des autres, etc.
Pseudo-code :
```
welsh_powell(G): le graphe avec toutes les couleurs associées aux sommets
G' = G
Trier les sommets par ordre décroissants selon leur degré
# Trier les sommets est au final moins couteux qu'affecter des numéros
TANT QUE G' n'est pas vide:
selectionner dans l'ordre de la liste des sommets triés
tout sommet non-voisin d'un sommet déjà sélectionné
Colorier de la même couleur tous les sommets sélectionnés
Retirer les sommets sélectionnés de G'
```
### Descriptif de l’implémentation en python :
Ici encore, nous n’avons pas utilisé de librairie externe dans les algorithmes implémentés, en revanche nous avons utilisé la librairie networkx ainsi que matplotlib pour afficher les graphes avec des sommets colorés de la bonne couleur.
Nous avons réalisé deux implémentations de l'algorithme de Welsh-Powell :
#### L’algorithme de Welsh-Powell tel que décrit ci-dessus :
Cette implémentation prend en paramètre une liste de liste des voisins du sommet d’indice i, et renvoie un dictionnaire avec pour clé une couleur, et en valeur une liste des sommets portant cette couleur.
Par exemple, si nous partons avec cette matrice d’adjacence : [ [1,0,0], [1,0,1], [0,0,0] ]
Grâce à la fonction matrice_adj_to_liste_voisins, qui prend en paramètre une matrice d’adjacence et renvoie la liste des voisins de chaque sommet, nous obtenons la liste suivante : [ [1], [0,2], [1] ]. Elle semble correcte puisque le sommet 1 a bien pour voisins le sommet 0 et le sommet 2, et, comme le sommet 2 n’a pas de successeur et que le sommet 0 n’a pour successeur que lui-même, alors les sommets 2 et 0 sont uniquement considérés voisins du sommet 1.
On remarquera qu’on ne prend pas comptabilise pas comme “voisin d’eux-mêmes” les sommets ayant un arc sur eux-mêmes tels que le sommet 0, dans la production de la liste des voisins de chaque sommet. 0 est donc uniquement voisin du sommet 1.
```python=
def matrice_adj_to_liste_voisins(matrice_adj):
liste_voisins = []
for b in range(len(matrice_adj)):
liste_voisins.append([])
for k in range(len(matrice_adj)):
for j in range(len(matrice_adj[k])):
if matrice_adj[k][j] != 0 and j != k \
and k not in liste_voisins[j] and j not in liste_voisins[k]:
liste_voisins[j].append(k)
liste_voisins[k].append(j)
return liste_voisins
```
La relation "voisin" est réciproque entre sommets. Si le sommet 1 a pour voisin le sommet 2, alors le sommet 2 a pour voisin le sommet 1. C'est ce que nous faisons dans cette fonction.
Il s'agit de la seule fonction écrite par nous-mêmes qui est utilisée dans le cadre de welsh_powell, afin de lui donner paramètre adéquat.
La complexité de cette fonction est de $O(S + (S * V * B)) = O(S*(1+(V*B)))$ avec $S$ le nombre de sommets (parcours de la matrice d'adjacence), $V$ le nombre d'itération sur chaque sous-liste de la matrice d'adjacence, et $B$ le nombre de fois que l'on exécute "k not in liste_voisins[j]" et "j not in liste_voisins[k]"
Désormais, parlons du coeur de cette fonction :
Pseudo-code de l'implémentation :
```
weslh_powell(liste_voisins): dictionnaire couleurs-sommets associés
Création d'un dictionnaire contenant un panoplie de couleurs
Création d'une liste contenant des couples (sommet, liste de ses sommets voisins)
On trie cette liste de couples par taille décroissante des listes de voisins
TANT QU'il reste des couples dans cette liste:
Création d'une liste des sommets séléctionnés d'une même couleur
On choisit temporairement le sommet du premier couple de cette liste
POUR chaque couple de la liste :
SI le sommet choisi n'est pas dans la liste des voisins du couple ET
le sommet du couple courant n'est pas dans la liste des sommets séléctionnés :
Ajouter le sommet choisi à la liste des sommets séléctionnés
Ajouter dans le dictionnaire les sommets séléctionnés, à la couleur courante
Supprimer de la liste des couples les couples aux indices des sommets séléctionnés
Changer de couleur
Renvoyer un dictionnaire avec uniquement les couleurs utilisées et les sommets associés
```
Explication du code concret :
Tout d’abord, nous créons un dictionnaire, contenant 9 clés, chacune désignant une couleur.
```python=
couleurs = ["red", "blue", "green", "pink", "purple", "brown", "cyan",
"magenta"]
for f in range(len(couleurs)):
couleurs_sommets[couleurs[f]] = [] #Création d'un dictionnaire de couleurs
```
Ensuite, nous créons une liste nommée “elements”. Cette liste va contenir des tuples composé en premier membre du numéro d’un sommet, et en deuxième membre de la liste de ses voisins (sur l’exemple précédent, cela donne par exemple (1, [0,2]) qui signifie que le sommet 1 a pour voisins les sommets 0 et 2).
```python=
for k in range(len(liste_voisins)):
elements.append((k, liste_voisins[k])) (sommet, liste de ses voisins)
```
Une fois cette liste créée, nous allons la trier, selon un ordre décroissant du degré de chaque sommet (autrement dit, selon son nombre de voisins). Pour cela, il nous suffit de trier selon la longueur de la liste en deuxième membre de chaque couple de la liste “elements”. Nous utilisons pour cela une fonction pré-faite en Python.
```python=
elements.sort(reverse=True, key=lambda a: len(a[1]))
```
Suite à cela, la boucle principale commence.
Elle sert à définir la condition d'arrêt : tous les sommets sont coloriés :
```python=
while len(elements) > 0:
```
Nous gérons dans ce programme 3 listes :
* indices_sommets_selectionnes, qui sert à supprimer plus facilement de la liste “elements” les sommets déjà sélectionnés (sans avoir à faire de recherche par valeur)
* sommets_selectionnes, qui sert à ajouter plus facilement dans la couleur courante l’ensemble des sommets sélectionnés
* elements_selectionnes, qui permet de faire plusieurs opérations de comparaison dans l’algorithme, c’est par exemple avec cette liste qu’on va vérifier qu’un élément peut être sélectionné ou non.
```python=
indices_sommets_selectionnes = []
sommets_selectionnes = []
elements_selectionnes = []
```
Suite à cela, nous sélectionnons le sommet du premier élément de cette liste triée, et si ce sommet ne fait pas partie des voisins des autres sommets (on peut le savoir grâce à la liste des voisins en deuxième membre de chaque tuple), alors on le sélectionne également.
```python=
for h in range(len(elements)):
if elements[0][0] not in elements[h][1]: #element[0][0] est le premier element
if len(elements_selectionnes) == 0: # Si aucun sommet n'a été séléctionné,
# alors on ne vérifie pas si le sommet choisit existe déjà dans la liste
# des éléments séléctionnés
indices_sommets_selectionnes.append(h)
sommets_selectionnes.append(elements[h][0])
elements_selectionnes.append(elements[h]) # Couple séléctionné
else: # Des sommets ont déjà été séléctionnés
ajouter = True
for b in elements_selectionnes:
if b[0] in elements[h][1]:
ajouter = False
if ajouter:
indices_sommets_selectionnes.append(h)
sommets_selectionnes.append(elements[h][0])
elements_selectionnes.append(elements[h]) # Couple séléctionné
```
A la fin de cette fonction, nous parcourons à l’envers la liste des indices des sommets sélectionnés (à l’envers afin de ne pas décaler les éléments de la liste “elements”, dans laquelle on va pop() l’élément présent à l’indice “j”, ce qui fait que l’on va pop() de l’indice le plus grand vers l’indice le plus petit et ainsi éviter un décalage) afin de les enlever de la liste des “elements”, et ainsi itérer sur les autres sommets par la suite, mais on va aussi ajouter l’ensemble des sommets sélectionnés au dictionnaire “couleurs_sommets” afin d’associer les sommets séléctionnés à une couleur.
Au final, nous renvoyons uniquement un dictionnaire contenant uniquement les couleurs possédant des sommets.
```python=
for j in reversed(indices_sommets_selectionnes):
couleurs_sommets[couleurs[indice_couleur_courante]].append(sommets_selectionnes.pop(0))
elements.pop(j)
```
La complexité de l'implémentation est de $O(S + T + (E * ((H* N) + J)))$ avec $S$ le nombre de sommets (parcours de la grande liste des successeurs), $T$ la complexité du tri des sommets par degré décroissants, $E$ le nombre de fois que l'on va itérer dans la boucle principale (while), H le nombre de fois que l'on va parcourir la liste des sommets seléctionnés, $N$ la complexité du "if elements[0][0] not in elements[h][1]" et $J$ le parcours de la liste renversée des éléments sélectionnés
Cette complexité ne prend pas en compte les suppressions que l'on réalise, car on ne peut pas prévoir combien d'éléments vont être supprimés à chaque itération.
#### Et l’algorithme “souple” de Welsh-Powell :
Il consiste en la même chose que welsh_powell, mais qui va prendre en paramètre, en plus de la liste des voisins de chaque sommet, une liste qui correspond à l’ordre de traitement des sommets du graphe.
La nuance entre la précédente fonction et celle-ci est que cette fonction ne fait pas de tri des sommets selon leur degré, mais selon l’ordre indiqué en paramètre, ce qui fait que les éléments se retrouvent triés dans l’ordre de traitement souhaité, et qu’on n’a plus qu’à prendre comme premier sommet le premier élément de la liste ordre_parcours et itérer sur tous les autres sommets de la liste “liste_ordonnee” dans l’ordre, puisque de toute façon ils sont triés dans l’ordre de parcours souhaité.
On gère dans cette implémentation une liste supplémentaire, qui sert à avoir les sommets triés selon l'ordre indiqué en paramètre.
```python=
liste_ordonnee = []
for i in ordre_parcours:
liste_ordonnee.append(elements[i])
```
Notre condition principale dans l'algorithme devient alors :
```python=
if ordre_parcours[0] not in liste_ordonnee[h][1]
```
A la place de :
```python=
if elements[0][0] not in elements[h][1]:
```
La fin de l'algorithme change également un peu, puisque désormais nous devons supprimer autant d'éléments de la liste de l'ordre de parcours que nous avons de sommets dans la couleur actuelle (car si on traite p sommets, alors on aura traité p ordres (dans l'ordre))
```python=
for j in reversed(indices_sommets_selectionnes):
ordre_parcours.remove(sommets_selectionnes[0])
couleurs_sommets[couleurs[indice_couleur_courante]].append(sommets_selectionnes.pop(0))
liste_ordonnee.pop(j)
```
La complexité de cette version souple est très similaire à la complexité de l'algorithme implémenté précédemment.
### Instances de test :
#### Welsh-Powell classique :
Nous avons testé l'implémentation sur deux graphes :
* Le premier (avec sa matrice d'adjacence) :
[[0 1 1 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 0 0 0]]
On lui applique la fonction "matrice_adj_to_liste_voisins" afin de récupérer la liste des voisins de chaque sommet du graphe, on fournit cela à la fonction welsh_powell, qui nous donne le résultat suivant : {'red': [2, 4], 'blue': [0, 3], 'green': [1]}.
Pour l'affichage en couleur des graphes, nous avons décidé d'enlever les arcs qui bouclent sur le même sommet.
Autrement dit, les sommet 2 et 4 sont de couleur rouge, les sommets 0 et 3 sont bleu, et le sommet 1 est vert.
L'algorithme semble correct puisque c'est le nombre chromatique de ce graphe : 3 est le nombre minimum de couleurs qu'on puisse avoir pour ce graphe.
* Le deuxième :
[[1 0 1 1 1]
[0 1 1 0 1]
[1 0 1 1 1]
[0 1 1 1 1]
[1 0 1 0 1]]
Soumis à notre implémentation de la même façon que le premier graphe, cela nous donne le résultat suivant :
{'red': [2], 'blue': [3], 'green': [4], 'pink': [0, 1]}
Pour l'affichage en couleur des graphes, nous avons décidé d'enlever les arcs qui bouclent sur le même sommet.
Cela semble une nouvelle fois correct, 4 est le nombre chromatique de ce graphe.
#### Welsh-Powell avec ordre souple :
Nous avons testé l'implémentation sur deux graphes, chacun avec deux ordres différents en paramètres :
* Le premier (avec sa matrice d'adjacence) :
[[0 1 1 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 0 0 0]]
Avec l'ordre suivant : [0,1,2,3,4]
On lui applique la fonction "matrice_adj_to_liste_voisins" afin de récupérer la liste des voisins de chaque sommet du graphe, on fournit cela à la fonction welsh_powell_souple, qui nous donne le résultat suivant : {'red': [0, 3], 'blue': [1, 4], 'green': [2]}
Autrement dit, les sommet 0 et 3 sont de couleur rouge, les sommets 1 et 4 sont bleu, et le sommet 2 est vert.
L'algorithme semble s'être déroulé correctement, puisqu'il donne bien le nombre de couleurs à appliquer qu'on attendait selon l'ordre donné.
Désormais, essayons d'appliquer le même algorithme avec le même graphe, mais avec l'ordre suivant : [2,4,0,3,1]
Le résultat est le suivant : {'red': [2, 4], 'blue': [0, 3], 'green': [1]}
Qui semble également correct...
Mais le graphe choisi n'est pas ici un choix judicieux pour tester l'efficacité des colorations des sommets avec/sans ordre. En effet, ce graphe, peu importe l'ordre dans lequel on cherche à le colorier, aura toujours au maximum 3 couleurs. 3 est d'ailleurs son nombre chromatique.
* Le deuxième :
[[0 0 0 1 0 1]
[0 0 1 0 1 0]
[0 1 0 0 0 1]
[1 0 0 0 1 0]
[0 1 0 1 0 0]
[1 0 1 0 0 0]]
Avec l'ordre suivant : [0,1,2,3,4,5]
Soumis à notre implémentation de la même façon que le premier graphe, cela nous donne le résultat suivant :
{'red': [0, 1], 'blue': [2, 3], 'green': [4, 5]}
L'algorithme s'est passé comme prévu. Ici, nous avons volontairement choisi un ordre qui ne donnerait pas le nombre chromatique de ce graphe, afin de montrer que l'ordre de parcours des sommets à réellement un impact sur la coloration. Nous avons donc ici 3 couleurs de coloration des sommets du graphe étudié.
Alors qu'avec l'ordre suivant : [0,2,4,1,3,5]
Soumis à notre implémentation de la même façon, cela nous donne le résultat suivant :
{'red': [0, 2, 4], 'blue': [1, 3, 5]}
L'algorithme s'est également passé comme prévu. Ici, nous avons choisi le meilleur ordre de parcours, puisque ce graphe est biparti. Le nombre chromatique de ce graphe est donc par propriété de 2, comme renvoyé par l'algorithme.
On voit donc sur ce deuxième exemple l'impact de l'ordre de parcours sur la coloration des sommets d'un graphe. Nos algorithmes semblent d'ailleurs fournir les bonnes solutions selon nos demandes.
### Réponses aux questions :
On travaille sur le graphe suivant :
Nous avons donc testé d'abord l'algorithme de Welsh-Powell souple avec l'ordre suivant : [0,1,2,3]
Cela nous donne le résultat suivant : {'red': [0, 1], 'blue': [2], 'green': [3]}.
On voit clairement ici que ce n'est pas l'ordre de coloration optimal puisque nous obtenons 3 couleurs différentes au lieu des deux suffisantes à colorier tous les sommets du graphe.
En effet, c'est le but de la question suivante : La coloration optimale serait par exemple obtenue à partir de l'ordre suivant : [0,3,1,2] ou encore [1,2,3,0]. Nous obtenons avec cet ordre là le résultat suivant : {'red': [0, 3], 'blue': [1, 2]}, qui semble alors correct et optimal.
Question suivante :
On étudie le graphe suivant :
Si on y applique Welsh-Powelle souple avec l'ordre suivant : [0, 1, 2, 3, 4, 5, 6, 7], nous obtenons le résultat suivant : {'red': [0, 1], 'blue': [2, 3], 'green': [4, 5], 'pink': [6, 7]}.
Il s'agit là en fait d'un graphe biparti, bien que la librairie networkX ait décidé de l'afficher sous forme de cube dans un premier temps, puis sous forme d'un graphe quelconque. Dans cet ordre de parcours de coloration des sommets, nous obtenons 4 couleurs différentes pour colorier tous les sommets. Ce qui n'est évidemment pas l'ordre optimal, puisqu'un graphe biparti a en théorie 2 comme nombre chromatique. Avec seulement deux couleurs, on peut colorier tous les sommetsn non-voisins entre eux.
Appliquons désormais l'ordre suivant : [0, 2, 4, 6, 1, 3, 5, 7].
Nous obtenons le résultat suivant : {'red': [0, 2, 4, 6], 'blue': [1, 3, 5, 7]}, c'est-à-dire que seules 2 couleurs ont été utilisées pour colorier l'ensemble des sommets du graphe.
Nous avons ici choisi un ordre optimal.
L'important est dans ce cas précis de parcourir les sommets impairs d'abord, puis les sommets pairs, ou inversement d'abord les sommets pairs, puis les sommets impairs.
## Séance 4 : Arbre couvrant de poids minimal
### Définition
Le but de cette séance est de coder les algorithmes de Kruskal et de Prim, les deux ayant un même objectif, mais traité différemment : trouver l’arbre couvrant de poids minimal dans un graphe connexe pondéré. Cela signifie que chaque arête possède une valeur : un poids, et que l’on cherche le chemin de plus faible poids passant par tous les sommets du graphe.
### Kruskal
#### Description de l'algorithme :
Cet algorithme consiste à trier toutes les arêtes du graphe étudié par ordre croissant, du poids le plus faible au poids le plus élevé, puis de parcourir la liste triée, de trouver la première arête (donc forcément celle de poids le plus faible par rapport à celles qui la suivent) qui ne forme pas de cycle avec les précédentes arêtes déjà sélectionnées, de l’ajouter à l’ensemble des arêtes sélectionnées, et cela n-1 fois, afin d’avoir tous les sommets reliés par des arêtes à au moins un autre sommet. En effet, en ayant dans un graphe n sommets, et que l’on veut une chaîne allant d’un sommet A à un sommet Z en passant une seule fois par tous les sommets, alors nous aurons dans cette chaîne n-1 arêtes.
Pseudo-code de l'algorithme :
```
kruskal(graphe): arbre couvrant de poids minimal
k=0
V = {}
Trier les arêtes par ordre de poids croissant
TANT QUE k < n-1:
Parcourir la liste triée
Sélectionner la première arête qui ne fait pas de cycle avec les précédentes
k = k + 1
V = V ∪ {arête sélectionnée}
```
#### Description de l'implémentation :
Nous n’utilisons encore une fois aucune librairie externe, mais nous utilisons encore la fonction “sort()” pré-faite de Python afin de trier les arêtes par ordre croissant selon leur poids.
Cependant, nous avons implémenté une structure toute particulière pour Kruskal : la structure Union-Find. Elle contient trois fonctions : makeSet(), qui permet de créer n ensembles disjoints au départ, en l’occurrence qui correspondent chacun à un entier appelé “représentant”. Ces représentants permettront de savoir si un sommet fait partie du même ensemble qu’un autre ou non, et si ce n’est pas le cas, les unir grâce à la fonction union(). Cette fonction permet tout simplement d’unir deux entiers, c'est-à-dire de changer le représentant de l’un des deux dans le tableau des représentants. Pour savoir si un sommet fait partie du même ensemble qu’un autre, on doit vérifier si leurs représentants sont identiques ou non, et pour cela, nous avons la fonction find(), qui permet de trouver le représentant d’un sommet dans le tableau des représentants.
Voici une explication de mon implémentation de l’algorithme de Kruskal avec la structure Union-find avec quelques illustrations :
Voici tout d’abord le graphe étudié :
En triant les arêtes du poids le plus faible au plus élevé : [ [2,3], [1,2], [1,3] ]
Au départ, tous les sommets ont leur propre ensemble, et se représentent eux-mêmes.
C’est-à-dire que le sommet 1 a pour représentant 1, le sommet 2 a pour représentant 2…
Les ensembles sont donc tous disjoints, car ils ont tous un représentant différent.
Ces ensembles disjoints sont crées grâce à la fonction makeSet().
On étudie donc les arêtes du poids le plus faible au poids le plus élevé, nous traitons donc en premier l’arête [2,3], de poids 1 < 4 < 9 (premier élément du tri réalisé au début de l’exemple), on fait un appel à la fonction find() sur les sommets 2 et 3, qui nous renvoie donc les représentants des ensembles auxquels appartiennent 2 et 3. Plus simplement dit, il nous renvoie le représentant de l’ensemble auquel appartient 2, et il renvoie le représentant de l’ensemble auquel appartient le sommet 3, en l’occurrence, leurs représentants sont respectivement 2 et 3. Ils sont donc différents, cela signifie que nous ne sommes pas encore passés par ces sommets et que donc il n’y a pas de cycle si on sélectionne cette arête. On va donc la sélectionner, ce qui fait qu’on va unir les ensembles des sommets 2 et 3. On va donc choisir un représentant parmi ceux des deux ensembles afin de représenter désormais les deux ensembles. Nous choisissons 2 comme représentant de l’union des ensembles des sommets 2 et 3.
Nous avons donc ici un nouvel ensemble : l’ensemble contenant les sommets 2 et 3, qui a pour représentant 2.
Nous étudions désormais l’arête de plus faible poids suivante : [1,2], de poids 4 < 9
On appelle la fonction find sur les sommets de cette arête : find(2), et find(1), qui nous renvoie respectivement 2 et 1, puisque 2 a pour représentant 2, suite à l’union, et 1 a pour représentant lui-même, n’ayant pas subi d’union pour le moment.
Comme 2 != 1, alors ils n’ont pas le même représentant et leurs ensembles peuvent être unis grâce à la fonction union(), nous décidons que le nouveau représentant de ce nouvel ensemble issu de l’union est 2.
Voici donc l’état de notre solution après ces opérations :
On traite ensuite la dernière arête qu’il reste, de poids 9 : [1,3].
On appelle find(1) et find(3) et on compare les résultats. Comme les sommets 1 et 3 font partie du même ensemble, ils renvoient tous deux le résultat “2”.
Or, 2 = 2, alors cela signifie que nous sommes face à un cycle, et que nous ne devons pas ajouter cette arête à la solution finale pour trouver un arbre couvrant de poids minimal.
En réalité, l’algorithme codé ne va même pas jusqu’à cette dernière étape, puisqu’il s’arrête à l’itération n-1 = 2. Autrement dit, après avoir uni l’ensemble {2,3} au singleton {1}, il aurait pris fin car il aurait ajouté assez d’arêtes à la solution pour avoir un arbre couvrant de poids minimal.
Fin de l’exemple.
En réalité, le code est légèrement différent, en effet, on ne gère pas des “ensembles” mais simplement le représentant de chaque sommet. Nous avons une liste de représentants où par exemple representants[2] correspondrait au représentant du 3ème sommet, puisque nous commençons à 0. En ne gérant pas des ensembles, find(x) revient simplement à renvoyer la valeur se trouvant à l’indice x de la liste representants, et l’union revient simplement à changer le représentant du représentant d’un des deux sommets passés en paramètre par l’autre représentant, et, évidemment, à mettre à jour tous les représentants des autres sommets qui avaient comme représentant celui qui vient d’être récemment modifié.
Pseudo-code de l'implémentation :
```python=
kruskal(n, liste_aretes_couples): arbre couvrant de poids minimal
k=0
copie_liste_arêtes_couples = liste_arêtes_couples
Créer les ensembles de chaque sommet
Trier les arêtes par ordre de poids croissant
TANT QUE k < n-1:
SI le representant du premier sommet de l'arête courante est différent du
représentant du deuxième sommet de l'arête courante :
ajouter à l'arbre couvrant l'arête courante
Unir les ensembles de ces sommets
k = k + 1
RETOURNER arbre_couvrant_poids_minimal
```
En effet, on remarque qu'on prend en paramètre le nombre de sommets et une liste de couples. Chaque couple correspond à (arête, poids de l'arête).
Explication du code concret :
Tout d'abord, étudions la structure Union-Find.
Au départ, nous créons des "ensembles" (nous donnons un représentant à chaque sommet), nous le faisons ainsi :
```python=
def make_set(u):
for i in u:
representants[i] = i
```
Au départ, tous les sommets sont leurs propres représentants.
Ensuite, nous utilisons une opération find(), qui consiste à chercher le représentant d'un "ensemble" :
```python=
def op_find(k):
return representants[k]
```
Et enfin, nous utilisons une opération d'union "d'ensembles", qui revient à changer le représentant de tous les ensembles concernés :
```python=
def op_union(a, b):
x = op_find(a)
y = op_find(b)
for i in range(len(representants)):
if representants[i] == x:
representants[i] = y
```
Désormais, passons à l'implémentation concrète de l'algorithme de Kruskal.
On gère dans cette implémentation 3 listes :
```python=
aretes_selectionnees = []
```
Qui permet d'avoir les arêtes sélectionnées pour l'arbre couvrant de poids minimal.
```python=
copie_liste_aretes_couples = liste_aretes_couples
```
Qui est une copie des arêtes (et de leur poids) du graphe d'origine
Et enfin :
```python=
sommets = []
```
Qui permet d'avoir la liste des sommets du graphe.
Nous avons également une variable qui va contenir le poids total de l'arbre couvrant de poids minimal (qui vaut 0 au départ) :
```python=
cout = 0
```
L'algorithme commence donc par la création des "ensembles" de cette façon :
```python=
for s in range(nombre_sommets):
sommets.append(s)
make_set(sommets)
```
Ici, nous ajoutons donc tous les sommets du graphe à la liste des sommets, et nous créons un ensemble pour chaque sommet. Les ensembles sont disjoints au départ.
```python=
copie_liste_aretes_couples.sort(key=lambda a: a[1])
```
Nous trions la liste des arêtes du graphe par ordre de poids croissant, avant d'engager la boucle principale :
```python=
while k < nombre_sommets - 1:
arete_courante = copie_liste_aretes_couples[indiceListeAretes][0]
if op_find(arete_courante[0]) != op_find(arete_courante[1]):
l_aretes.append(arete_courante)
op_union(arete_courante[0], arete_courante[1])
k += 1
cout += couple_courant[1]
indiceListeAretes += 1
```
Ici, nous sélectionnons l'arête courante, nous vérifions que les représentants des deux sommets de cette arête ne sont pas les mêmes, si tel est le cas, nous sélectionnons cette arête et nous unissons les ensembles concernés.
Suite à cela, nous incrémentons le nombre d'arêtes séléctionnées (lié à la variable k), nous ajoutons le poids de l'arête séléctionnée au poids de l'arbre couvrant et nous passons à l'arête suivante afin de l'étudier.
Cela est réalisé n - 1 fois, afin d'avoir les n-1 arêtes nécessaires pour considérer avoir un arbre couvrant de poids minimal.
Enfin, nous renvoyons l'arbre couvrant minimal sous la forme d'un tableau à deux éléments, le premier contenant le poids de l'arbre, et le deuxième élément contenant les arêtes de l'arête (sous forme de couples avec le poids associé) :
```python=
return [l_aretes, cout]
```
La complexité de l'implémentation est de $O(S + (A * log(A)) + K)$ avec $S$ le nombre de sommets (création des sommets), $K$ est le nombre de fois qu'on parcourt la boucle principale (while) et $A$ le nombre d'arête du graphe. $A*log(A)$ est la complexité du tri des arêtes par poids croissant (le tri fusion est par défaut utilisé).
### Prim
#### Description de l’algorithme :
Ici, il n’y a pas de tri des arêtes, contrairement à l’algorithme de Kruskal. Nous prenons au départ un sommet au hasard, puis nous itérons n-1 fois pour les mêmes raisons que pour l’algorithme de Kruskal : pour avoir les n-1 arêtes nécessaires à l’arbre couvrant de poids minimal. Dans ces itérations, nous cherchons à chaque fois une arête [u, v] telle que le sommet u soit présent dans l’ensemble S et que le sommet v n’y soit pas présent (ou l’inverse, c’est-à-dire que v soit dans l’ensemble S et que u n’y soit pas) tout en ayant un poids minimal par rapport aux autres arêtes du même type (respectant la condition d’appartenance ou non des sommets à l’ensemble S).
Une fois une telle arête trouvée, nous l’ajoutons à l’ensemble T qui va contenir l’ensemble des arêtes sélectionnées pour l’arbre couvrant de poids minimal.
Nous ajoutons également à l’ensemble S le sommet de cette arête qui n’y appartenait pas (seul un des deux sommets de l’arête n’y appartient pas en raison de la condition de sélection). Nous ajoutons finalement le poids de l’arête sélectionnée au poids total de l’arbre couvrant de poids minimal.
Pseudo-code de l'algorithme :
Il est tiré du site : https://www.pairform.fr/doc/1/32/180/web/co/Prim.html
#### Description de l'implémentation :
Cette fois, nous avons utilisé la librairie random afin de produire un entier aléatoire compris entre 0 et n-1 inclus afin de sélectionner un premier sommet aléatoirement pour l’ensemble S. Notre algorithme de Prim prend en entrée la liste des sommets du graphe étudié et une liste de tuples contenant en premier membre une arête du graphe et en deuxième membre le poids de l’arête. Cet algorithme renvoie en sortie l’arbre couvrant de poids minimal, en l’occurrence nous renvoyons les arêtes sélectionnées pour l’arbre couvrant de poids minimal, sous forme de liste de listes, chaque sous-liste correspondant à une arête sélectionnée.
Pseudo-code de l'implémentation :
```
prim(liste_sommets, liste_aretes_couples): arbre couvrant de poids minimal :
cout = 0
sommets_visites = []
r1 = nombre aléatoire entre 0 et n
Ajout du sommet d'indice r1 aux sommets visités
POUR i allant de 0 à n-1 inclus :
POUR chaque couple de liste_aretes_couples:
On étudie l'arête courante
SI ((sommet1 est dans les sommets visités mais pas sommet2)
OU que (sommet2 est dans les sommets visités mais pas sommet1))
ET que l'arête a le poids minimal:
on sélectionne l'arête
on ajoute l'arête séléctionnée à l'arbre couvrant de poids minimal
on ajoute les sommets de cette arête aux sommets visités
RETOURNER l'arbre couvrant de poids minimal
```
Le code en lui-même n’a pas vraiment de particularité, il suit à la lettre le pseudo-code de l'algorithme, à la seule différence que dans la boucle principale, nous n’itérons pas sur les arêtes mais sur des couples contenant une arête et son poids, et que dans le condition principale (if), nous ne vérifions pas l’appartenance ou non des sommets que dans un seul sens, puisque dans le cadre de ce TP et des graphes sur lesquels nous testons nos algorithmes, nous pourrions avoir une arête [u,v] qui soit présentée sous la forme [v, u], il faut donc prendre en compte les deux cas (u appartient à S mais pas v, ou v appartient à S et pas u).
A la fin d’une itération de la boucle principale, nous ajoutons à l’ensemble résultat T l’arête nouvellement sélectionnée et nous ajoutons à l’ensemble S le sommet de cette arête qui n’y appartient pas encore.
Explication du code concret :
Tout d'abord, nous initialisons la fonction et les premières variables :
```python=
def prim(liste_sommets, liste_aretes_couples):
cout = 0
nombre_sommets = len(liste_sommets)
r1 = random.randint(0, nombre_sommets - 1) # 0 et n inclus
s = [liste_sommets[r1]]
t = []
```
On définit les paramètres de la fonction comme étant la liste des sommets du graphe étudié et une liste de couples (arête, poids) des arêtes du graphe initial. La fonction renvoie à la fin le poids et les arêtes composant l'arbre couvrant de poids minimal.
On initialise ensuite le cout, le nombre de sommets du graphe, un premier sommet aléatoire ajouté à la liste des sommets visités, et enfin la liste des arêtes de l'arbre couvrant de poids minimal, pour l'instant vide.
Suite à ça, on entre dans la boucle principale :
```python=
for i in range(0, nombre_sommets - 1):
poids_min_courant = MAX_INT
arete_selectionee = None
```
On parcourt jusqu'à ce toutes les arêtes nécessaires à un arbre couvrant soient présentes. On définit le poids_min_courante de l'itération courante comme étant un entier très grand. Cela nous permet de faire des comparaisons de poids et au final en tirer l'arête de plus faible poids.
Au départ, on ne sélectionne pas d'arête.
Suite à cela, on se retrouve dans une nouvelle boucle :
```python=
for couple in liste_aretes_couples:
arete_courante = couple[0]
sommet1_courant = arete_courante[0]
sommet2_courant = arete_courante[1]
if ((sommet1_courant in s and sommet2_courant not in s) or (
sommet2_courant in s and sommet1_courant not in s)) and
couple[1] <= poids_min_courant:
poids_min_courant = couple[1]
arete_selectionee = couple
```
Cette boucle sert à parcourir toutes les arêtes du graphes, à sélectionner au fur et à mesure celle qui répond à nos conditions et qui a le poids le plus faible.
Au final, nous ajoutons dans les listes initialisées au départ les éléments dont nous avons besoin pour continuer l'algorithme :
```python=
t.append(arete_selectionee[0])
if arete_selectionee[0][1] not in s:
v = arete_selectionee[0][1]
s.append(v)
if arete_selectionee[0][0] not in s:
v = arete_selectionee[0][0]
s.append(v)
cout += arete_selectionee[1]
```
On ajoute à la liste des arêtes sélectionnées l'arête courante sélectionnée, puis on ajoute à la liste des sommets visités les sommets de l'arête sélectionnée s'ils ne font pas déja partie de la liste.
Puis nous incrémentons le poids total de l'arbre couvrant minimal avec le poids de l'arête sélectionnée.
Pour finir, nous renvoyons l'arbre couvrant de poids minimal sous la forme d'un tableau [liste des arêtes de l'arbre, poids de l'arbre] :
```python=
return [t, cout]
```
La complexité de l'implémentation est de $O(S² * A)$ environ, avec $S$ le nombre de sommets (S² car parcours boucle principale (while) et opérations diverses de vérifications d'existences des sommets), et $A$ le nombre d'arête du graphe
Maintenant que le coeur de ces implémentations ont été vues, il s'agit désormais de parler des quelques fonctions "annexes" que nous avons implementé afin que le tout fonctionne de manière plus agréable.
```python=
def matrice_adjacence_valuee_to_liste_sommets(matrice_adj):
liste_sommets = []
for i in range(len(matrice_adj)):
liste_sommets.append(i)
return liste_sommets
```
Cette simple fonction ajoute tout simplement à une liste tous les sommets de 0 à taille(matrice_adj)-1 inclus. Cela permet de facilement avoir tous les sommets d'un graphe (avec sa matrice d'adjacence et non pas la liste des sommets successeurs) sans utiliser le parcours en profondeur, qui est coûteux.
Nous avons également une fonction qui renvoie tous les arcs (avec leur poids) d'un graphe sous forme d'une liste de couples (arête, poids) :
```python=
def matrice_adjacence_valuee_to_liste_aretes(matrice_adj):
indice_general_matrice_adj = 1
indice_sommet_courant = 0
liste_arete = []
nombre_sommets = len(matrice_adj[0])
while indice_general_matrice_adj < nombre_sommets + 1:
ligne = [0] * (nombre_sommets - indice_general_matrice_adj)
for i in range(len(ligne)):
ligne[i] = matrice_adj[indice_sommet_courant][indice_general_matrice_adj + i]
if ligne[i] != 0:
liste_arete.append(([indice_general_matrice_adj - 1, indice_general_matrice_adj + i], ligne[i]))
indice_general_matrice_adj += 1
indice_sommet_courant += 1
return liste_arete
```
Cette fonction est un peu particulière car elle ne parcourt pas toute la matrice mais uniquement le triangle haut droit puisque cette fonction est appelée dans le cas d'un graphe non-orienté, ce qui fait qu'une même arête est présente dans "les deux sens", ainsi il n'est pas nécessaire de parcourir toute la matrice mais seulement la moitié, séparée par une diagonale de 0 (car dans un graphe non-orienté, un sommet n'a pas de lien avec lui-même).
Nous avons également un équivalent pour les arcs (orientés) :
```python=
def matrice_adjacence_valuee_to_liste_arcs(matrice_adj):
liste_arete = []
nombre_sommets = len(matrice_adj[0])
for s in range(len(matrice_adj)):
ligne = [0] * nombre_sommets
for i in range(len(ligne)):
ligne[i] = matrice_adj[s][i]
if ligne[i] != 0:
liste_arete.append(([s, i], ligne[i]))
return liste_arete
```
Cette fois-ci, nous parcourons toute la matrice d'adjacence car il n'y a pas forcément réciprocité de la relation entre deux sommets d'un graphe orienté.
Passons désormais aux instances de test.
### Instances de test
Nous avons testé les implémentations de Prim et Kruskal sur deux graphes :
* Le premier (avec sa matrice d'adjacence valuée (une valeur > 0 signifie qu'il y a une arête)) :
[[0 10 5 3]
[10 0 8 0]
[5 8 0 0]
[3 0 0 0]]
Les algorithmes de Prim et de Kruskal nous ont donné le même arbre couvrant de poids minimal, à savoir :
L'arbre couvrant de poids minimal ci-dessus a un poids de 16.
* Deuxième instance de test :
[[0 6 5 0 0 0],
[0 0 3 0 0 8],
[0 0 0 7 2 0],
[0 0 0 0 4 0],
[0 0 0 0 0 1],
[9 0 0 0 0 0]]
Les algorithmes de Prim et de Kruskal nous ont donné le même arbre couvrant de poids minimal, à savoir :
L'arbre couvrant de poids minimal ci-dessus a un poids de 15.
### Réponse aux questions :
En termes de vitesse de convergence vers une solution, Kruskal semble au dessus de Prim.
Pour affirmer cela, nous nous sommes apuyés sur 3 grands types de graphes :
* Les graphes peu denses, c'est-à-dire qui ont 3 * n arêtes ;
* Les graphes denses, qui ont n²/3 arêtes ;
* Les graphes complets, qui ont n²/2 arêtes.
Pour chaque type de graphe, nous avons réalisé de nombreux tests, mais nous allons ici n'en exposer que quelques uns.
Nous allons notamment exposer, pour chaque type de graphe, la vitesse de convergence et la qualité de la solution fournie par les algorithmes.
Nous testons pour chaque type de graphe, un graphe à 10 sommets, à 100 sommets, et un graphe à 1000 sommets.
Kruskal et Prim sont évidemment comparés simultanément sur le même graphe à chaque fois.
Les graphes dont nous vous parlons sont en fait générés grâce à des fonctions que nous avons réalisées, nous en exposerons deux ici afin de comprendre les bases de notre génération de graphe :
```python=
def genererGrapheConnexe(nombre_sommets):
sommets = []
aretes = []
for i in range(nombre_sommets):
sommets.append(i)
for i in range(len(sommets) - 1):
poidsRandom = random.randint(1, 1000)
aretes.append(([sommets[i], sommets[i + 1]], poidsRandom))
return [sommets, aretes]
```
Cette première fonction nous permet de générer un graphe connexe tel que pour n sommets, nous aurons dans ce graphe uniquement les arêtes : [0,1], [1,2], [2,3], ..., [n-1,n]. Cette fonction est nécessaire car si on génère un graphe qui n'est pas connexte, les algorithms de Prim et Kruskal ne fonctionneront pas. Cette fonction assure donc que le graphe généré sera au moins connexe. Chaque arête a un poids compris entre 1 et 1000.
Cette fonction est utilisée dans les autres servant à générer des graphes plus complexes, par exemple :
```python=
def genererGraphePeuDense(nombre_sommets):
grapheConnexe = genererGrapheConnexe(nombre_sommets)
aretes = grapheConnexe[1]
sommets = grapheConnexe[0]
while len(aretes) < nombre_sommets * 3:
indiceSommet1 = random.randint(0, nombre_sommets - 1)
indiceSommet2 = random.randint(0, nombre_sommets - 1)
while indiceSommet2 == indiceSommet1:
indiceSommet2 = random.randint(1, nombre_sommets - 1)
poidsRandom = random.randint(1, 1000)
if not existeArete([sommets[indiceSommet1], sommets[indiceSommet2]], aretes):
aretes.append(([sommets[indiceSommet1], sommets[indiceSommet2]], poidsRandom))
return [sommets, aretes]
```
Cette fonction permet de générer un graphe peu dense. On commence donc par gnérer un graphe connexe (on voit l'appel à la fonction genererGrapheConnexe au début) puis on génére autant d'arêtes qu'il en faut pour atteindre 3 * N arêtes. Chaque arête est générée entre deux sommets choisis aléatoirement et chaque arête à un poids aléatoire compris entre 1 et 1000.
Nous avons également une fonction très similaire pour générer un graphe dense (n²/3 arêtes).
Enfin, nous avons une fonction pour générer un graphe complet :
```python=
def genererGrapheComplet(nombre_sommets):
sommets = []
aretes = []
for i in range(nombre_sommets):
sommets.append(i)
for j in range(nombre_sommets):
k = j + 1
while k < nombre_sommets:
poidsRandom = random.randint(1, 1000)
aretes.append(([sommets[j], sommets[k]], poidsRandom))
k = k + 1
return [sommets, aretes]
```
Cette fonction permet de générer un graphe complet selon le nombre de sommets fourni. Un graphe complet est un graphe dans lequel tous les sommets sont voisins. Ils sont tous un lien avec tous les autres sommets du graphe. Il n'est pas possible de générer un graphe contenant plus d'arêtes que dans un graphe complet, pour un nombre de sommets donné.
On ne fait pas appel à genererGrapheConnexe ici afin de ne pas détériorer la complexité algorithme et puis un graphe complet est forcément connexe.
Passons désormais à notre étude.
En théorie, la qualité de la solution fournie par les algorithmes sera la même. En effet, on mesure la qualité d'une solution à l'aide du poids de l'arbre couvrant de poids minimal. Le résultat sera normalement identique pour Kruskal et Prim pour chaque graphe.
Tests :
#### Pour N = 10
Graphe peu dense :
Kruskal :
Poids arbre couvrant : 1693
Temps d'execution : 0.024599999999985744 ms
Prim :
Poids arbre couvrant : 1693
Temps d'execution : 0.07370000000000987 ms
On voit que dans un graphe peu dense à 10 sommets les temps d'execution sont sensiblement les mêmes (moins d'1 ms) et que le résultat est le même pour les deux algorithmes. Ils donnent tous deux le poids le plus petit possible pour l'arbre couvrant.
Graphe dense :
Kruskal :
Poids arbre couvrant : 921
Temps d'execution : 0.031899999999973616 ms
Prim :
Poids arbre couvrant : 921
Temps d'execution : 0.07570000000001187 ms
On voit que dans un graphe dense à 10 sommets les temps d'execution sont toujours sensiblement les mêmes (moins d'1 ms) et que le résultat est le même pour les deux algorithmes.
Graphe complet :
Kruskal :
Poids arbre couvrant : 1128
Temps d'execution : 0.024100000000026878 ms
Prim :
Poids arbre couvrant : 1128
Temps d'execution : 0.09239999999999249 ms
On voit que dans un graphe complet à 10 sommets les temps d'execution sont toujours sensiblement les mêmes (moins d'1 ms, bien que l'écart commence doucement à se creuser en faveur de Kruskal) et que le résultat est le même pour les deux algorithmes.
#### Pour N = 100
Graphe peu dense :
Kruskal :
Poids arbre couvrant : 19299
Temps d'execution : 0.5734000000000017 ms
Prim :
Poids arbre couvrant : 19299
Temps d'execution : 32.292500000000004 ms
On voit que dans un graphe peu dense à 100 sommets les temps d'execution commencent à diverger. Kruskal a duré moins d'1 ms alors que Prim a pris environ 32 ms (soit au moins 32 fois plus de temps). Le résultat est toujours le même pour les deux algorithmes. Ils donnent tous deux le poids le plus petit possible pour l'arbre couvrant.
Graphe dense :
Kruskal :
Poids arbre couvrant : 2225
Temps d'execution : 1.1160999999999532 ms
Prim :
Poids arbre couvrant : 2225
Temps d'execution : 365.95540000000005 ms
On voit que dans un graphe dense à 100 sommets les temps d'execution divergent sérieusement. Kruskal a duré environ 1 ms alors que Prim a pris environ 371 ms (soit 365 fois plus de temps). Le résultat est toujours le même pour les deux algorithmes.
Graphe complet :
Kruskal :
Poids arbre couvrant : 1333
Temps d'execution : 3.4583000000000252 ms
Prim :
Poids arbre couvrant : 1333
Temps d'execution : 569.6711999999999 ms
On voit que dans un graphe complet à 100 sommets les temps d'execution divergent. Kruskal a duré environ 3,5 ms alors que Prim a pris environ 569 ms. Le résultat est toujours le même pour les deux algorithmes.
Pour le moment, Kruskal continue d'être l'algorithme le plus efficace. Voyons ce qu'il en est pour n=1000.
#### Pour N = 1000
Graphe peu dense :
Kruskal :
Poids arbre couvrant : 194583
Temps d'execution : 54.977000000000054 ms
Prim :
Poids arbre couvrant : 194583
Temps d'execution : 30281.1199 ms
On voit que dans un graphe peu dense à 1000 sommets, les temps commencent à décoller, puisque même Kruskal qui jusqu'ici n'avait pas dépassé 3 ms prend maintenant 55 ms pour un graphe peu dense de 1000 sommets. les temps d'execution commencent à diverger. Kruskal a duré environ 55 ms alors que Prim a pris environ 30 secondes. Nous passons donc à une toute autre échelle et l'algorithme de Kruskal commence à se montrer vraiment plus efficace. Le résultat est cependant toujours le même pour les deux algorithmes. Ils donnent tous deux le poids le plus petit possible pour l'arbre couvrant.
Graphe dense :
Kruskal :
Poids arbre couvrant : 2225
Temps d'execution : 1.1160999999999532 ms
Prim :
Poids arbre couvrant : 2225
Temps d'execution : 365.95540000000005 ms
On voit que dans un graphe dense à 1000 sommets les temps d'execution divergent sérieusement. Kruskal a duré environ 1 ms alors que Prim a pris environ 371 ms (soit 365 fois plus de temps). Le résultat est toujours le même pour les deux algorithmes.
Graphe complet :
Kruskal :
Poids arbre couvrant : 1727
Temps d'execution : 162.34880000000018 ms
Prim :
Poids arbre couvrant : NAN
Temps d'execution : > 4 minutes, nous ne sommes pas arrivés à la fin
On voit que dans un graphe complet à 1000 sommets les temps d'execution divergent énormément. Kruskal a duré environ 162 ms, un temps plus qu'acceptable, alors que Prim n'a meme pas fini son execution en 4 minutes.
Kruskal est donc l'algorithme qui semble surpasser toutes les statistiques dans nos exemples, alliant une qualité de résultat excellente et un temps d'exécution très bon lui aussi.
Désormais, essayons de trouver à partir de combien de sommets d'un graphe peu dense, d'un graphe dense et d'un graphe complet Prim et Kruskal connaissent des grands écarts de temps d'exécution.
Les valeurs que nous avons trouvées sont les suivantes :
Graphe peu dense :
Pour n = 320 environ, nous observons une grande divergence dans l'efficacité des algorithmes de Kruskal et de Prim :
Kruskal :
Poids arbre couvrant : 66817
Temps d'execution : ~ 5.2 ms
Prim :
Poids arbre couvrant : 66817
Temps d'execution : ~ 990 ms
Graphe dense :
Pour n = 130 environ, nous observons une grande divergence dans l'efficacité des algorithmes de Kruskal et de Prim :
Kruskal :
Poids arbre couvrant : 1972
Temps d'execution : ~ 1.85 ms
Prim :
Poids arbre couvrant : 1972
Temps d'execution : ~ 1 seconde
Graphe complet :
Pour n = 115 environ, nous observons une grande divergence dans l'efficacité des algorithmes de Kruskal et de Prim :
Kruskal :
Poids arbre couvrant : 1235
Temps d'execution : ~ 1.82 ms
Prim :
Poids arbre couvrant : 1235
Temps d'execution : ~ 1 seconde
On voit donc que le nombre de sommets nécessaires à un certain seuil de divergence des temps d'execution diminue au fur et à mesure que le graphe possède de plus en plus d'arêtes.
Un graphe peu dense a besoin d'environ 320 sommets (donc 960 arêtes afin de voir une divergence).
Un graphe dense a besoin d'environ 130 sommets (donc 5633 arêtes afin de voir une divergence).
Un graphe complet a besoin d'environ 115 sommets (donc 6555 arêtes afin de voir une divergence).
Avec nos implémentations, il se trouve que Kruskal domine largement les temps d'execution, il est bien meilleur, même sur les plus gros graphes.
Cela est plutôt perturbant, puisque nous savons que théoriquement, Prim est censé être meilleur sur les graphes denses (et complets), et Kruskal meilleur sur les graphes peu denses.
Cependant, cela peut s'expliquer par plusieurs facteurs :
* Notre implémentation de l'algorithme de Kruskal est l'une des plus efficaces, utilisant une structure "d'arbre" (bien que nous n'en ayons pas vraiment crée un).
* Notre implémentation de Prim n'est certainement pas la meilleure qui soit, en effet, nous vérifions l'existence de l'arête [u,v] mais aussi l'existence de [v, u] également, avant d'ajouter une arête qui aurait pour sommets u et v. Nous faisons donc deux parcours différents sur la même liste, ce qui forcément ralentit l'algorithme.
#### Difficultés rencontrées :
Les difficultés rencontrées concernent surtout la génération des graphes.
En effet, au delà de 400-500 sommets, la génération d'un graphe dense devient très très longue. Cela est dû au fait que nous cherchions un indice de deuxième sommet différent du premier sommet, mais aussi au fait que nous vérifier que l'arête ainsi formée n'existe pas déjà dans le graphe, et que nous répétions ces opérations si l'une des conditions citées n'est pas respectée.
De plus, Prim prend également beaucoup de temps à se finaliser sur un graphe dense ou complet pour n > 400 (2 minutes et 15 secondes environ pour n = 400 sur un graphe complet), cela est dû aux diverses vérifications que nous effectuons dans cet algorithme.
Google Drive
Gist
Clipboard
Sign in with Wallet
