# Fonctions pour les tests
# Graphe g0
g0 = [[True,True,True,False],
[False,False,False,True],
[True,True,True,True],
[False,False,False,True]]
# couplage c0
c0= [0,-1,3,-1]
# Graphe g1
g1 = [[True,True,False,False,False,False],
[True,True,False,False,False,False],
[True,True,True,False,False,False],
[False,False,True,True,False,False],
[False,False,False,True,True,True],
[False,False,False,True,True,True]]
Partie 1. Généralités¶
Q.1.¶
Il existe dans $G_{0}$ un couplage de cardinal 3, par exemple $\left\{0_{A}, 1_{B}\right\},\left\{1_{A}, 3_{B}\right\}$ et $\left\{2_{A}, 0_{B}\right\}$.
En revanche, il n'existe pas de couplage de cardinal 4 ; en effet, si un tel couplage existait les sommets $1_{\mathrm{A}}$ et $3_{\mathrm{A}}$ seraient tous deux couplés à $3_{\mathrm{B}}$ et les deux arêtes correspondantes seraient incidentes.
Q.2.¶
Pour chaque nouveau couplage rencontré il faut vérifier si l'arête correspondante existe dans le graphe et si elle n'est pas incidente à une arête déjà rencontrée.
Pour cela on utilise une liste dejaVu qui marque les sommets de $B$ dès lors qu'ils sont couplés à un sommet de $A$.
def verifie(g, c):
n = len(c)
dejaVu = [False] * n
for i,ci in enumerate(c):
if ci != -1:
if not g[i][ci] or dejaVu[ci]:
return False
else:
dejaVu[ci] = True
return True
verifie(g0,c0)
True
def cardinal(c):
s = 0
for x in c:
if x != -1:
s += 1
return s
cardinal(c0)
2
Q.5.¶
La complexité de cette fonction est bien évidemment en $\mathcal{O}(n)$.
Partie 2. Un algorithme pour déterminer un couplage maximal¶
Q.6.¶
Dans le graphe initial toutes les arêtes ont une somme des degrés des extrémités comprises entre 4 et 7.
Seules deux ont une somme égale à 4 : les arêtes $\left\{1_{\mathrm{A}}, 3_{\mathrm{B}}\right\}$ et $\left\{3_{\mathrm{A}}, 3_{\mathrm{B}}\right\}$. On choisit donc l'arête $\left\{1_{\mathrm{A}}, 3_{\mathrm{B}}\right\}$.
Une fois les arêtes incidentes éliminées, il ne reste que des arêtes de somme 5 ; on choisit l'arête $\left\{0_{\mathrm{A}}, 0_{\mathrm{B}}\right\}$ qu'on retire ainsi que les arêtes incidentes.
Il ne reste alors que deux arêtes : $\left\{2_{A}, 1_{B}\right\}$ et $\left\{2_{A}, 2_{B}\right\}$; on choisit la première et les deux arêtes restantes sont alors éliminées : l'algorithme se termine en renvoyant le couplage $\boxed{\left[\left\{1_{\mathrm{A}}, 3_{\mathrm{B}}\right\},\left\{0_{\mathrm{A}}, 0_{\mathrm{B}}\right\},\left\{2_{\mathrm{A}}, 1_{\mathrm{B}}\right\}\right]}$.
Les trois étapes d'élimination sont reproduites ci-dessous.
Q.7.¶
Dans $G_{1}$ toutes les arêtes ont une somme des degrés des extrémités égale à 4,5 ou 6 . Une seule a une somme égale à 4 : l'arête $a_{1}=\left\{3_{\mathrm{A}}, 2_{\mathrm{B}}\right\}$. Une fois celle-ci éliminée ainsi que les arêtes incidentes il reste le graphe :
On constate que le graphe obtenu n'est plus connexe; chacune de ses deux composantes peut posséder en son sein au plus deux couplages (c'est effectivement le cas ici) donc l'algorithme retournera un couplage de cardinal égal à 5. Or il existe un couplage de cardinal 6:$\left\{\left\{0_{A}, 0_{B}\right\},\left\{1_{A}, 1_{B}\right\},\left\{2_{A}, 2_{B}\right\},\left\{3_{A}, 3_{B}\right\},\left\{4_{A}, 4_{B}\right\},\left\{5_{A}, 5_{B}\right\}\right\}$; l'algorithme ne garantit donc pas d'obtenir un couplage de cardinal maximal.
Q.8.¶
On commence par rédiger une fonction qui calcule les degrés des sommets de A et des sommets de B :
def calculeDegres(g:list[list])->(list,list):
n = len(g)
degA = [0] * n
degB = [0] * n
for i in range(n):
for j in range(n):
if g[i][j]:
degA[i] += 1
degB[j] += 1
return degA, degB
calculeDegres(g1)
([2, 2, 3, 2, 3, 3], [3, 3, 2, 3, 2, 2])
Cette première fonction est bien évidemment de complexité quadratique.
Il reste ensuite à partir à la recherche de l'arête minimale. Pour cela on commence par déterminer les degrés de tous les sommets du graphe. Le parcours des boucles imbriquées permet, si les sommets sont reliés, de trouver et sauvegarder le minimum des sommes des degrés. Si `maxi est resté initialisé à sa valeur de définition (la somme des degrés des extrémités d'une arête ne peut excéder $2n$,), c'est qu'aucune arête ne relie les sommets du graphe.
def areteMin(g):
n = len(g)
degA, degB = calculeDegres(g)
maxi = 2 * n + 1
for i in range(n):
for j in range(n):
if g[i][j] and degA[i] + degB[j] < maxi:
maxi = degA[i] + degB[j]
a = (i, j)
if maxi == 2 * n + 1:
return False, None
return True, a
areteMin(g1)
(True, (3, 2))
def supprimer(g, a):
i, j = a
for k in range(len(g)):
g[i][k] = False
g[k][j] = False
Q.11.¶
Cette fonction est de complexité linéaire.
Q.12.¶
On définit enfin la fonction principale de l'algorithme algo_approche. On commence par copier la liste g (en n'oubliant pas le caractère mutable des listes). La liste des couplages est initialisée comme étant vide, puis on applique strictement l'algorithme proposé à l'aide des fonctions précédentes.
def algoApproche(g):
n = len(g)
c =[-1]*n
gg = [[g[i][j] for j in range(n)] for i in range(n)]
b, a = areteMin(gg)
while b:
c[a[0]]=a[1]
supprimer(gg, a)
b, a = areteMin(gg)
return c
algoApproche(g0)
[0, 3, 1, -1]
Q.13.¶
Sachant que la complexité de la fonction arete_min est en $\mathcal{O}\left(n^{2}\right)$ et qu'un couplage maximal comporte au maximun $n$ couplages, la complexité totale de cette fonction est en $\mathcal{O}\left(n^{3}\right)$.
Partie 3. Recherche exhaustive d'un couplage de cardinal maximum¶
Q.14.¶
Il suffit ici de parcourir toute la matrice et de retourner la première arête que l'on rencontre.
def uneArete(g):
n = len(g)
for i in range(n):
for j in range(n):
if g[i][j]:
return (True, (i, j))
return (False, None)
Q.15.¶
Si le graphe courant ne contient aucune arête, le cardinal maximum d’un couplage est 0 et aucun sommet n’est couplé. Dans le cas contraire, l’algorithme considère une arête quelconque a du graphe courant et recherche successivement :
- un couplage de cardinal maximal parmi les couplages du graphe courant ne contenant pas a ;
- un couplage de cardinal maximal parmi les couplages du graphes contenant a.
Lorsque le graphe $G$ contient au moins une arête $a$, on réalise deux copies $G_{1}$ et $G_{2}$ de $G$ telles que :
- $G_1$ ne contient pas l'arête $a$ ;
- $G_2$ ne contient ni l'arête $a$ ni aucune des arêtes incidentes.
Tout couplage $C_{1}$ de $G_{1}$ est un couplage de $G$ ne contenant pas l'arête $a$ ; tout couplage $C_{2}$ de $G_{2}$ à qui on ajoute $a$ est un couplage de $G$ contenant l'arête $a$. Ceci conduit à l'algorithme suivant :
def meilleurCouplage(g):
n = len(g)
b, a = uneArete(g)
if not b:
return [-1] * n
g1 = [[g[i][j] for j in range(n)] for i in range(n)]
g1[a[0]][a[1]] = False
g2 = [[g[i][j] for j in range(n)] for i in range(n)]
supprimer(g2, a)
c1 = meilleurCouplage(g1)
c2 = meilleurCouplage(g2)
c2[a[0]] = a[1]
if cardinal(c1) > cardinal(c2):
return c1
else:
return c2
meilleurCouplage(g1)
[0, 1, 2, 3, 4, 5]