Un graphe est un ensemble de sommets reliés par des arêtes. Il peut être orienté ou non orienté.
Voici un exemple de graphe orienté et de graphe non orienté:
Soit ${\tt G}$ est un graphe dont les sommets sont numérotés de $0$ à $n$.
$M_{i,j}=\left\{\begin{array}{cl}1&\hbox{ si }j\hbox{ est un successeur de }i\\
0&\hbox{ sinon}\end{array}\right.$.
Lorsqu'un graphe est non orienté, sa matrice d’adjacence est symétrique.
Lorsqu'on interdit les boucles (arête d'un sommet vers lui-même), une matrice d’adjacence n'a que des 0 sur sa diagonale.
tout $i\in[\![0,n]\!]$, la liste ${\tt L[i]}$ est la liste des voisins de $i$.
Ainsi les deux graphes précédents peuvent être représentés par les matrices d'adjacence: $$M1=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 1\\ 0& 1& 0& 0\\ 1& 1& 0& 0\end{array}\right)\qquad\hbox{et}\qquad M2=\left(\begin{array}{cccc}1& 0& 0& 0\\ 1& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right) $$ qui s'écrivent en Python:
M1 = [ [0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [1, 1, 0, 0] ]
M2 = [ [1, 0, 0, 0], [1, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0] ]
On peut aussi les réprésenter par leur liste d'adjacences:
L1 = [ [1, 3], [0, 2, 3], [1], [0, 1] ]
L2 = [ [0], [0, 2], [3], [0] ]
La représentation d’un graphe à l’aide d’une matrice d’adjacence offre les avantages suivants:
(temps constant).
La représentation des graphes à l’aide de listes d’adjacences a l'avantage suivant:
Toutefois, elle admet également plusieurs inconvénients potentiels. Par exemple, pour déterminer si une arête/un arc donné ${\tt (i,j)}$ est présent dans le graphe, il n’existe pas de moyen plus rapide que de rechercher ${\tt j}$ dans la liste d’adjacence ${\tt L[i]}$ de ${\tt i}$. Par conséquent, ce mode de représentation est en général utilisé pour les graphes peu denses,
Dans cet exercice on supposera que les sommets du graphe sont les entiers de $0$ à $n$.
Q1. Ecrire une fonction ${\tt nbSommetsL(L)}$ qui prend pour argument la liste d'adjacence ${\tt L}$ d'un graphe (orienté ou non) et renvoie le nombre de sommets de ce graphe.
# cellule à compléter
def nbSommetsL(L):
# exécuter cette cellule pour tester avec les exemples précédents:
L1 = [ [1, 3], [0, 2, 3], [1], [0, 1] ]
L2 = [ [0], [0, 2], [3], [0] ]
print( nbSommetsL(L1) == 4 )
print( nbSommetsL(L2) == 4 )
True True
# cellule pour tests libres
Q2. Ecrire une fonction ${\tt nbSommetsM(M)}$ qui prend pour argument la matrice d'adjacence ${\tt M}$ d'un graphe (orienté ou non) et renvoie le nombre de sommets de ce graphe.
# cellule à compléter
def nbSommetsM(M):
# exécuter cette cellule pour tester avec les exemples précédents:
M1 = [ [0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [1, 1, 0, 0] ]
M2 = [ [1, 0, 0, 0], [1, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0] ]
print( nbSommetsM(M1) == 4 )
print( nbSommetsM(M2) == 4 )
True True
# cellule pour tests libres
Q3. Ecrire une fonction ${\tt degreL(L,i)}$ qui prend pour argument la liste d'adjacence ${\tt L}$ d'un graphe (orienté ou non) et un sommet ${\tt i}$ et renvoie le degré du sommet ${\tt i}$ (ie son nombre de voisins dans le graphe).
# cellule à compléter
def degreL(L, i):
# exécuter cette cellule pour tester avec les exemples précédents:
L1 = [ [1, 3], [0, 2, 3], [1], [0, 1] ]
L2 = [ [0], [0, 2], [3], [0] ]
print( degreL(L1, 1) == 3 )
print( degreL(L1, 2) == 1 )
print( degreL(L2, 3) == 1 )
print( degreL(L2, 1) == 2 )
True True True True
# cellule pour tests libres
Q4. Ecrire une fonction ${\tt degreM(M,i)}$ qui prend pour argument la matrice d'adjacence ${\tt M}$ d'un graphe (orienté ou non) et un sommet ${\tt i}$ et renvoie le degré du sommet ${\tt i}$ (ie son nombre de voisins dans le graphe).
# cellule à compléter
def degreM(M, i):
# exécuter cette cellule pour tester avec les exemples précédents:
M1 = [ [0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [1, 1, 0, 0] ]
M2 = [ [1, 0, 0, 0], [1, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0] ]
print( degreM(M1, 1) == 3 )
print( degreM(M1, 2) == 1 )
print( degreM(M2, 3) == 1 )
print( degreM(M2, 1) == 2 )
True True True True
# cellule pour tests libres
Q5. Ecrire une fonction ${\tt ListeAd(M)}$ qui prend pour argument la matrice d'adjacence ${\tt M}$ d'un graphe (orienté ou non) et renvoie la liste d'adjacence de ce graphe.
# cellule à compléter
def ListeAd(M):
# exécuter cette cellule pour tester avec les exemples précédents:
M1 = [ [0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [1, 1, 0, 0] ]
M2 = [ [1, 0, 0, 0], [1, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0] ]
L1 = [ [1, 3], [0, 2, 3], [1], [0, 1] ]
L2 = [ [0], [0, 2], [3], [0] ]
print( ListeAd(M1) == L1 )
print( ListeAd(M2) == L2 )
True True
# cellule pour tests libres
Q6. Ecrire une fonction ${\tt MatAd(L)}$ qui prend pour argument la liste d'adjacence ${\tt L}$ d'un graphe (orienté ou non) et renvoie la matrice d'adjacence de ce graphe.
# cellule à compléter
def MatAd(L):
# exécuter cette cellule pour tester avec les exemples précédents:
M1 = [ [0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [1, 1, 0, 0] ]
M2 = [ [1, 0, 0, 0], [1, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0] ]
L1 = [ [1, 3], [0, 2, 3], [1], [0, 1] ]
L2 = [ [0], [0, 2], [3], [0] ]
print( MatAd(L1) == M1 )
print( MatAd(L2) == M2 )
True True
# cellule pour tests libres
On souhaite colorier un graphe ${\tt G}$ non orienté dont les sommets sont numérotés de $0$ à $n$. La proposition de coloration est donnée par une liste ${\tt C}$: ainsi ${\tt C[s]}$ donne le numéro de la couleur attribuée au sommet ${\tt s}$. Comme les sommets, les couleurs sont numérotées à partir de zéro.
Pour commencer, on souhaite déterminer si une coloration proposée est valide: deux sommets du graphe reliés par une arête ne doivent pas être de la même couleur.
Pour tester vos fonction vous pourrez utiliser le graphe suivant:
LA=[[1, 3, 4, 6, 7], [0, 2, 3], [1, 3], [0, 1, 2, 4], [0, 3, 5, 6, 7], [4, 6, 7], [0, 4, 5, 7], [0, 4, 5, 6]]
Q7 Ecrire une fonction ${\tt coloration}\_{\tt valide}$ qui reçoit en argument une liste d’adjacence ${\tt LA}$, une liste de couleurs ${\tt C}$ et renvoie ${\tt True}$ si le coloration est valide, ${\tt False}$ sinon.
# cellule à compléter
def coloration_valide(LA, C):
# exécuter cette cellule pour tester avec l'exemple précédent:
LA = [[1, 3, 4, 6, 7], [0, 2, 3], [1, 3], [0, 1, 2, 4], [0, 3, 5, 6, 7], [4, 6, 7], [0, 4, 5, 7], [0, 4, 5, 6]]
C1 = [0,1,0,2,1,0,2,3]
C2 = [0,1,0,2,1,0,2,1]
print( coloration_valide(LA, C1) == True )
print( coloration_valide(LA, C2) == False )
True True
# cellule pour tests libres
Q8. Pour un graphe comportant ${\tt nb}$ sommets, quelle est la complexité dans le pire des cas de la fonction ${\tt coloration}\_{\tt valide}$?
# Répondre ici:
Nous allons maintenant implenter un algorithme intuitif de coloration:
attribuée au sommet ${\tt s}$
sont attribuées.
Q9. Ecrire une fonction ${\tt colore}\_{\tt sommet}$ de trois arguments, la liste ${\tt C}$ des couleurs attribuées, le
numéro ${\tt s}$ du sommet à colorer et la liste d’adjacence ${\tt LA}$ caractérisant le graphe.
Cette fonction ne renvoie rien mais modifie la liste ${\tt C}$ en donnant à ${\tt C[s]}$ la plus petite couleur
possible, en fonction des couleurs des sommets voisins qui sont déjà colorés.
Par exemple, pour le graphe donné en exemple , prenons ${\tt C = [0,1,-1,-1,-1,-1,-1,-1]}$. Les sommets 0 et 1
ont donc déjà été colorés avec les couleurs ${\tt C[0]=0}$ et ${\tt C[1]=1}$.
L’appel ${\tt colore}\_{\tt sommet(C,2,LA)}$ modifie la liste ${\tt C}$ en ${\tt C=[0,1,0,-1,-1,-1,-1,-1]}$. Cela veut
dire que la couleur $0$ a été attribuée au sommet $2$.
# cellule à compléter
def colore_sommet(C,s,LA):
# exécuter cette cellule pour tester avec l'exemple précédent:
LA = [[1, 3, 4, 6, 7], [0, 2, 3], [1, 3], [0, 1, 2, 4], [0, 3, 5, 6, 7], [4, 6, 7], [0, 4, 5, 7], [0, 4, 5, 6]]
C = [0, 1, -1, -1, -1, -1, -1, -1]
colore_sommet(C, 2, LA)
print( C == [0, 1, 0, -1, -1, -1, -1, -1] )
True
# cellule pour tests libres
Q10. À l’aide de Q9., écrire une fonction ${\tt colorer}$ d’argument une liste ${\tt LA}$ caractérisant un graphe et renvoyant la liste ${\tt C}$ des numéros des couleurs attribuées, en colorant les sommets un par un
par ordre croissant de leurs numéros.
Par exemple, l’application de la fonction ${\tt colorer}$ au graphe donné en exemmple renverra la liste de couleurs
${\tt [0,1,0,2,1,0,2,3]}$.
# cellule à compléter
def colorer(LA):
# exécuter cette cellule pour tester avec l'exemple précédent:
LA = [[1, 3, 4, 6, 7], [0, 2, 3], [1, 3], [0, 1, 2, 4], [0, 3, 5, 6, 7], [4, 6, 7], [0, 4, 5, 7], [0, 4, 5, 6]]
C = colorer(LA)
print( C == [0, 1, 0, 2, 1, 0, 2, 3] )
True
# cellule pour tests libres