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]:

%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)

[[0, 1, 1, 1], [0, 0, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0]]

Pour afficher joliment une matrice :

In [28]:

def prettyprint(M):
    for ligne in M:
        print(ligne)
    return None

In [31]:

prettyprint(matrice_adjacence(G2))

[0, 1, 1, 1]
[0, 0, 1, 1]
[0, 0, 0, 1]
[0, 0, 0, 0]

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)

[[1], [2], [3], [0]]

In [15]:

L2=liste_adjacence(G2)
print(L2)

[[1, 2, 3], [2, 3], [3], []]

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)

Out[17]:

{0: [1], 1: [2], 2: [3], 3: [0]}

In [18]:

dict_adjacence(G2)

Out[18]:

{0: [1, 2, 3], 1: [2, 3], 2: [3], 3: []}

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)

Out[20]:

[[0, 1, 2, 3], [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]]

In [21]:

G2

Out[21]:

[[0, 1, 2, 3], [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]]

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)

Out[23]:

[[0, 1, 2, 3], [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]]

In [24]:

G2

Out[24]:

[[0, 1, 2, 3], [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]]

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)

Out[26]:

[[0, 1, 2, 3], [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]]

In [27]:

G1

Out[27]:

[[0, 1, 2, 3], [(0, 1), (1, 2), (2, 3), (3, 0)]]

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)

Out[36]:

[0, 1, 8, 9, 11, 10, 7, 6, 4, 5, 3, 2]

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)

Out[40]:

[3, 7, 6]

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)

Out[50]:

[0, 2, 4, 6, 3, 1, 5]

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)

Out[53]:

[0, 2, 1, 0, 1, 2, 2]

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)

[[3, 5], [4, 0, 2, 1, 6, 11, 10, 8, 9, 7]]

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()