#!/usr/bin/env python
# coding: utf-8
#
#
TP n°15 (graphes) : Éléments de correction
# $\require{color}$
# $\require{xcolor}$
# $\require{cancel}$
# $\newcommand{\myfbox}[1]{\fcolorbox{red}{white}{$\textrm{#1}$}}$
# $\require{stmaryrd}$
# $\newcommand{\ient}{[\![}$
# $\newcommand{\rrbracket}{]\!]}$
# $\newcommand{\llbracket}{[\![}$
# $\newcommand{\fient}{]\!]}$
# $\newcommand{\R}{\mathbb R}$
# $\newcommand{\K}{\mathbb K}$
# $\newcommand{\N}{\mathbb N}$
# $\newcommand{\C}{\mathbb C}$
# $\newcommand{\P}{\mathbb P}$
# $\newcommand{\E}{\mathbb E}$
# $\newcommand{\V}{\mathbb V}$
# $\newcommand{\Z}{\mathbb Z}$
# $\newcommand{\dt}{\mathrm d}$
# $\newcommand{\sh}{\operatorname{sh}}$
# $\newcommand{\ch}{\operatorname{ch}}$
# $\newcommand{\id}{\operatorname{Id}}$
# $\newcommand{\mat}{\operatorname{mat}}$
# $\newcommand{\sp}{\operatorname{Sp}}$
# $\newcommand{\In}{\operatorname{I}}$
# $\newcommand{\vect}{\operatorname{Vect}\ }$
# $\newcommand{\rg}{\operatorname{rg}}$
# $\newcommand{\tr}{\operatorname{Tr}}$
# $\newcommand{\dis}{\displaystyle}$
# $\renewcommand{\Im}{\operatorname{Im}}$
# $\newcommand{\im}{\operatorname{Im}}$
# $\newcommand{\bordermatrix}[3]{ \begin{matrix} \begin{matrix}#1\end{matrix} & \\ #3 & \hspace{-1em} \begin{matrix}#2\end{matrix} \end{matrix}}$
# $\newcommand{\fonction}[5]{#1\ \colon \left\{\begin{array}{ccl}#2 & \longrightarrow & #3\\#4 & \longmapsto & #5\end{array}\right.}$
# $\newcommand{\fonctionsansnom}[4]{\left\{\begin{array}{ccl}#1 & \longrightarrow & #2\\#3 & \longmapsto & #4\end{array}\right.}$
# $\newcommand{\revdots}{\mathinner{\mkern1mu\raise1pt{\kern7pt\hbox{.}}\mkern2mu\raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}}$
# $\newcommand{\tendvers}[2]{\xrightarrow[#1\to#2]{}}$
# In[1]:
import matplotlib.pyplot as plt
import networkx as nx
# In[2]:
get_ipython().run_line_magic('run', 'villes.py')
# In[3]:
#%run labyrinthe.py
# ## 1. Implémentation des graphes
#
# Exercice 1 (Représentation des graphes)
#
# In[3]:
sommets = [k for k in range(4)]
arcs1 = [(0, 1), (1, 2), (2, 3), (3, 0)]
arcs2 = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
G1 = [sommets, arcs1]
G2 = [sommets, arcs2]
# In[13]:
RG1 = nx.DiGraph()
RG1.add_nodes_from(G1[0])
RG1.add_edges_from(G1[1])
nx.draw(RG1, with_labels=True, node_color='cyan')
plt.show()
# In[5]:
RG2 = nx.Graph()
RG2.add_nodes_from(G2[0])
RG2.add_edges_from(G2[1])
nx.draw(RG2, with_labels=True, node_color='cyan')
plt.show()
# In[6]:
RV = nx.Graph()
RV.add_nodes_from(Villes[0])
RV.add_edges_from(Villes[1])
nx.draw(RV, with_labels=True, node_color='cyan')
plt.title("Vive la géographie !")
plt.xlim(-1.2,1.2) # pour ne pas couper les noms des villes
plt.show()
#
# Exercice 2 (Implémentation des graphes)
#
#
# Question 1 (matrice d'adjacence)
#
# In[25]:
def matrice_adjacence(G):
N = len(G[0]) # le nombre de sommets
M = [[0 for j in range(N)] for i in range(N)]
for arc in G[1]:
i, j = arc
M[i][j] = 1
return M
# In[26]:
M2 = matrice_adjacence(G2)
# In[27]:
print(M2)
# Pour afficher joliment une matrice :
# In[28]:
def prettyprint(M):
for ligne in M:
print(ligne)
return None
# In[31]:
prettyprint(matrice_adjacence(G2))
#
# Question 2 (liste d'adjacence)
#
# In[13]:
def liste_adjacence(G):
n = len(G[0])
L = [[] for k in range(n)]
for arc in G[1]:
i, j = arc
L[i].append(j)
return L
# In[14]:
L1 = liste_adjacence(G1)
print(L1)
# In[15]:
L2=liste_adjacence(G2)
print(L2)
#
# Question 3 (dictionnaire d'adjacence)
#
# In[16]:
def dict_adjacence(G):
n = len(G[0])
D = {k: [] for k in range(n)}
for arc in G[1]:
i, j = arc
D[i].append(j)
return D
# In[17]:
dict_adjacence(G1)
# In[18]:
dict_adjacence(G2)
#
# Question 4 (fonctions inverses)
#
# In[19]:
def mat2graph(M):
n = len(M) # nombre de sommets
sommets = [k for k in range(n)]
arcs = [(i, j) for i in range(n) for j in range(n) if M[i][j] == 1]
return [sommets, arcs]
# In[20]:
mat2graph(M2)
# In[21]:
G2
# In[22]:
def list2graph(L):
n = len(L) # nombre de sommets
sommets = [k for k in range(n)]
arcs = [(i, j) for i in range(n) for j in L[i]]
return [sommets, arcs]
# In[23]:
list2graph(L2)
# In[24]:
G2
# In[25]:
def dict2graph(D):
n = len(D) # nombre de sommets
sommets = [k for k in range(n)]
arcs = [(i, j) for i in range(n) for j in D[i]]
return [sommets, arcs]
# In[26]:
dict2graph(L2)
# In[27]:
G1
#
# Question 5 (cas des graphes non orientés)
#
# Il faut "symétriser" les fonctions précédentes :
# In[28]:
def matrice_adjacence_no(G):
n = len(G[0]) # le nombre de sommets
M = [[0 for j in range(n)] for i in range(n)]
for arc in G[1]:
i, j = arc
M[i][j] = 1
M[j][i] = 1
return M
# In[29]:
def liste_adjacence_no(G):
n = len(G[0])
L = [[] for k in range(n)]
for arc in G[1]:
i, j = arc
L[i].append(j)
L[j].append(i)
return L
# In[34]:
def dict_adjacence_no(G):
n = len(G[0])
D = {k: [] for k in range(n)}
for arc in G[1]:
i, j = arc
D[i].append(j)
D[j].append(i)
return D
# **Remarque :** Les fonctions inverses restent quant à elles inchangées.
# ## 2. Parcours de graphe
#
# Exercice 3 (labyrinthe DFS)
#
#
# Question 1
#
# On adapte l'algorithme vu en cours :
# In[35]:
def profondeur(G, s0):
n = len(G)
visite = [False for _ in range(n)]
liste = []
pile = [s0]
while len(pile) != 0:
x = pile.pop()
if not visite[x]:
visite[x] = True
liste.append(x)
for y in G[x]:
pile.append(y)
return liste
# In[36]:
RV = nx.Graph()
RV.add_nodes_from(Villes_num[0])
RV.add_edges_from(Villes_num[1])
nx.draw(RV, with_labels=True, node_color='cyan')
plt.show()
DV = dict_adjacence_no(Villes_num)
profondeur(DV, 0)
#
# Question 2.i
#
# In[37]:
sommets = [k for k in range(12)]
aretes = [(0, 1), (1, 5), (4, 5), (4, 8), (8, 9), (9, 10), (2, 6), (6, 7), (6, 10), (3, 7), (7, 11)]
labyrinthe = [sommets, aretes]
laby = dict_adjacence_no(labyrinthe)
#
# Question 2.ii
#
# On adapte le parcours en profondeur, pour qu'il renvoie également la liste des précédesseurs de chaque sommet du chemin :
# In[38]:
def profondeur(G, s0):
n = len(G)
visite = [False for _ in range(n)]
pile = [s0]
P = [None for k in range(n)]
while len(pile) != 0:
x = pile.pop()
if not visite[x]:
visite[x] = True
for y in G[x]:
pile.append(y)
if P[y] == None:
P[y] = x
return P
# In[39]:
def sortir(G, s0, s1):
P = profondeur(G, s0)
if P[s1] == None:
return [] # on ne peut pas sortir
else:
sortie = [s1]
position = s1
while position != s0:
position = P[position]
sortie.append(position)
return sortie
# In[40]:
sortir(laby, 6, 3)
#
# Question 2.iii
#
# In[37]:
sommets = [k for k in range(12)]
aretes = [(0, 1), (1, 5), (4, 5), (4, 8), (8, 9), (9, 10), (2, 6), (6, 7), (6, 10), (3, 7), (7, 11)]
labyrinthe = [sommets, aretes]
laby = dict_adjacence_no(labyrinthe)
# On construit la matrice du chemin vers la sortie :
# In[38]:
def matrice(m, n, chemin, debut=None, sortie=None):
M = [[[255, 255, 255] for j in range(n)] for i in range(m)]
#chemin = sortir(G, debut, sortie)
for s in chemin:
i, j = coord(s, m, n)
if s == sortie:
M[i][j] = [255, 0, 0] # sortie en rouge
elif s == debut:
M[i][j] = [255, 255, 0] # debut en jaune
else:
M[i][j] = [255, 180, 0] # chemin en orange
return M
# In[39]:
m, n = 3, 4
debut = 5
sortie = 3
chemin = [sortie]
M = matrice(m, n, chemin, sortie, sortie) # le labyrinthe vide, la sortie est coloriée en rouge
dessin_laby(aretes, M)
# On trace le labyrinthe avec les murs et le chemin :
# In[40]:
chemin = sortir(laby, debut, sortie)
M = matrice(m, n, chemin, debut, sortie)
dessin_laby(aretes,M)
# On peut regarder un autre exemple :
# In[41]:
m, n = 5, 5
sommets = [k for k in range(m * n)]
aretes = [(0, 1), (0, 5), (1, 6), (2, 3), (3, 4), (3, 8), (4, 9), (5, 10),
(7, 8), (7, 12), (10, 11), (11, 16), (12, 17), (13, 14), (14, 19),
(15, 20), (16, 21), (17, 18), (17, 22), (18, 19), (18, 23), (20, 21),
(21, 22), (23, 24)]
labyrinthe = [sommets, aretes]
laby = dict_adjacence_no(labyrinthe)
# In[42]:
debut = 13
sortie = 0
chemin = [sortie]
M = matrice(m, n, chemin, sortie, sortie) # le labyrinthe vide, la sortie est coloriée en rouge
dessin_laby(aretes, M)
# In[43]:
chemin = sortir(laby, debut, sortie)
M = matrice(m, n, chemin, debut, sortie)
dessin_laby(aretes, M)
#
# Exercice 4 (parcours en largeur - BFS)
#
# In[44]:
import collections
def largeur(G, s0):
n = len(G)
visite = [False for _ in range(n)]
file = collections.deque()
file.append(s0)
chemin = []
while len(file) != 0:
x = file.popleft()
if not visite[x]:
visite[x] = True
chemin.append(x)
for y in G[x]:
file.append(y)
return chemin
# On la teste sur le labyrinthe précédent, en y ajoutant quelques murs :
# In[45]:
debut = 13
m, n = 5, 5
sommets = [k for k in range(m * n)]
aretes = [(0, 1), (1, 6), (2, 3), (3, 8), (4, 9), (5, 10),
(7, 8), (7, 12), (10, 11), (11, 16), (12, 17), (13, 14), (14, 19),
(15, 20), (16, 21), (17, 18), (17, 22), (18, 19), (18, 23), (20, 21),
(21, 22), (23, 24)]
labyrinthe = [sommets, aretes]
laby = dict_adjacence_no(labyrinthe)
chemin=[debut]
M = matrice(m, n, chemin, debut, debut) # le labyrinthe vide, le début est colorié
dessin_laby(aretes, M)
# In[46]:
chemin = largeur(laby, debut)
M = matrice(m, n, chemin, debut, debut)
dessin_laby(aretes, M)
# ## 3. Coloriage et découpage
#
# Exercice 5 (coloration d'un graphe)
#
#
# Question 1 (un exemple à la main)
#
# On suit l'algorithme à la main :
# - on classe les sommets par ordre décroissant de degré : ```[0, 2, 4, 6, 3, 1, 5]```
# - on colorie le premier sommet, ```0```, en rose, ainsi que le sommet ```3```
# - on colorie maintenant le sommet suivant, ```2```, en bleu, ainsi que le sommet ```4``` (```5``` est voisin de ```4```)
# - on colorie maintenant le sommet suivant, ```6```, en orange, ainsi que les sommets ```1``` et ```5```.
# 
#
# Question 2 (degré)
#
# In[47]:
def degre(G, k):
return len(G[k])
#
# Question 3 (tri selon le degré)
#
# On adapte n'importe quel tri raisonnable déjà étudié ; ici, on adapte le tri par insertion :
# In[48]:
def trier(G):
n = len(G)
sommets = [k for k in range(n)]
for k in range(1, n):
i = k
elt = sommets[k]
while i > 0 and degre(G, sommets[i - 1]) < degre(G, elt):
sommets[i] = sommets[i - 1]
i -= 1
sommets[i] = elt
return sommets
# On teste la fonction sur l'exemple précédent :
# In[49]:
G = [[1, 2, 4, 5, 6], [0, 2], [0, 1, 3, 6], [2, 4, 6], [0, 3, 5, 6], [0, 4], [0, 2, 3, 4]]
# In[50]:
trier(G)
#
# Question 4 (algorithme de Welsh-Powel)
#
# In[51]:
def colorer(G):
n = len(G)
sommets = trier(G)
couleurs = [None for k in range(n)]
c = 0
for k in sommets:
if couleurs[k] == None:
couleurs[k] = c
voisins = G[k]
for s in sommets:
if (couleurs[s] == None) and (s not in voisins):
couleurs[s] = c
voisins = voisins + G[s]
c += 1
return couleurs
# In[52]:
G = [[1, 2, 4, 5, 6], [0, 2], [0, 1, 3, 6], [2, 4, 6], [0, 3, 5, 6], [0, 4], [0, 2, 3, 4]]
# In[53]:
colorer(G)
# In[54]:
LG = list2graph(G)
# In[55]:
couleurs = ['violet','aqua','orange','lime','red','yellow','pink']
palette = [couleurs[k] for k in colorer(G)]
# In[56]:
RG = nx.Graph()
RG.add_nodes_from(LG[0])
RG.add_edges_from(LG[1])
nx.draw(RG, with_labels=True, node_color=palette)
plt.show()
# In[57]:
Lvilles = liste_adjacence_no(Villes_num)
palette = [couleurs[k] for k in colorer(Lvilles)]
# In[58]:
RV = nx.Graph()
RV.add_nodes_from(Villes[0])
RV.add_edges_from(Villes[1])
nx.draw(RV, with_labels=True, node_color=palette)
plt.title("Vive la géographie !")
plt.xlim(-1.2, 1.2) # pour ne pas couper les noms des villes
plt.show()
#
# Exercice 6 (coupe de graphe)
#
#
# Question 1
#
# In[59]:
import random as rd
# In[60]:
def karger(G):
n = len(G) # nombre de sommets
P = [[s] for s in range(n)] # initialisation de la partition en liste de singletons
A = [(i, j) for i in range(n) for j in G[i]] # liste des arêtes
while len(P) > 2: # tant que la partition possède plus de 2 sous-ensembles
a = rd.choice(A) # on tire une arête au hasard
s1, s2 = a # les extrémités de l'arête
for i in range(len(P)):
if s1 in P[i]:
ind1 = i # s1 est dans le sous-ensemble n°ind1
if s2 in P[i]:
ind2 = i # s2 est dans le sous-ensemble n°ind2
if ind1 != ind2:
# on réunit les sous-ensembles contenant les sommets de l'arête
P[ind1] += P[ind2]
# on supprime toutes les arêtes dont les deux extrémités sont dans le même sous-ensemble
for a in A:
if a[0] in P[ind1] and a[1] in P[ind1]:
A.remove(a)
del P[ind2] # on enleve P[ind2] de la partition
return P
# In[61]:
LV = liste_adjacence(Villes_num)
KV = karger(LV)
print(KV)
#
# Question 2
#
# In[62]:
def coupe(G,P):
n=len(G)
# on commence par créer une copie du graphe G
Gcopy = [[s for s in voisins] for voisins in G]
for s1 in range(n):
for s2 in Gcopy[s1]:
if (s1 in P[0] and s2 in P[1]) or (s1 in P[1] and s2 in P[0]):
Gcopy[s1].remove(s2)
Gcopy[s2].remove(s1)
return Gcopy
# In[63]:
RV = nx.Graph()
RV.add_nodes_from(Villes_num[0])
RV.add_edges_from(Villes_num[1])
nx.draw(RV, with_labels=True, node_color='cyan')
plt.show()
# In[64]:
LV = liste_adjacence_no(Villes_num)
KV = karger(LV)
VillesC = coupe(LV, KV)
GVC = list2graph(VillesC)
RV = nx.Graph()
RV.add_nodes_from(GVC[0])
RV.add_edges_from(GVC[1])
nx.draw(RV, with_labels=True, node_color='cyan')
plt.show()