---
lang: fr
tags: theorie des graphs, S6, ING1
title: Theorie des graphs 7
date: 26/03/2019
---

# Theorie des graphs 7

## ALgo d'edmonds pour la recherche de chemin améliorant un couplage M (Edmonds' blossoms algorithm)

def find_augmenting_path(G=(V, E), M):
# 1.    Etiqueter chaque sommet x libre libres (ne touchent pas M)
#       par [R, x, x]
# 2.    Tant qu'il existe un sommet x d'étiquette [R, r, p] avec
#       une arrête (x, y) non visitée:
#           a) Marqué (x, y) comme visitée
#           b) Si y n'a pas d'étiquette (alors y touche M)
#               soit (y, z) l'arete de M qui touche y
#               étiqueter y par [B, r, x]
#               étiqueter z par [R, r, y]
#           c) Si y est B, ne rien faire
#           d) si y a pour étiquette [R, r', p']
#               i) si r != r'
#                   Construire le chemin P de r à x
#                   construire le chemin P' de r' à y
#                   Retourner concat(P, reverse(P'))
#               ii) Si r == r' // on a trouvé un cycle de taille impair autour de y
#                   créer le graph G' dans leqel le cycle  de taille impair est compréssé en un seul sommet (un bourgeon)
#                   P' = find_augmenting_path(G', M)
#                   si P' = []: return []
#                   construire à partir de P' en transformant le bourgeau par un chemin de taille paire.
#                   Retourner P
#          Retourner []

Chaque sommet est étiqueté par un triplet et une couleur.