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

# Theorie des graphs 6

## Couplages (matching)

++Def++: Dans un G = (V,E) non orienté, un couplage M $\subseteq$ E est un sous-ensemble des aêtes tel que M ne contient pas 2 arêtes adj.

Un couplage M est ==maximal== s'il n'existe pas de couplage M' tel que M Non Inclue dans M'.

Un couplage M est ==maximum== s'il n'existe pas de couplage M' tel que |M'| $>$ |M|

graph G {
rankdir=LR
a -- b -- c -- d -- e -- f -- a
}

E = {a,b,c,d,e,f}
{a,d} est un couplage maximal
{a,c,d} n'est pas un couplage
{a,c,e} est un couplage maximum

++Def++: Un couplage M si |M| = |V|/2

Exemple 1:

:::info
Voir photo du 25/03/2019
:::

Exemple 2:

- Armée multinationnale:
- On a des conducteurs de tanks qui parlent chacun 1 ou plusieurs lagues
- Pour un conduire un tank, il faut 2 conducteur qui parlent la même langue
- Coomment apparier les conducteurs pour maximiser le nombre de tanks ?

:::info
Voir 2eme photo du 25/03/2019
:::

Du coup, quel algo pour trouver un couplage maximAL ?

1. Choisir une arrête (x,y) de E, et l'ajouter à M
2. Retirer les sommets x et y du graph
3. Répeter les étapes tant E $\neq$ $\emptyset$

++Def:++ Un chemin améliorant est un chemin qui relie deux sommets non touché par M (sommets "isolés") en alternant des arêtes de E\M avec avec des arêtes de M

Si P est un chemin améliorant, alors M' = M $\bigoplus$ P (XOR, c-a-d les arêtes qui sont dans M ou P, mais pas dans les 2) est un couplage tel que |M'| > |M|. Parce que P contient x arêtes dans M et x+1 arêtes dans E\M

:::info
3eme photo du 25/03/2019
:::

Mais est-ce qu'il toujours un chemin améliorant ?

==Théorème==: Il existe un chemin améliorant ssi M n'est pas maximUM.
($\Leftrightarrow$) Evident, si P est améliorant, alors |M $\bigoplus$ P| > |M|, donc M pas maximum.

($\Leftarrow$) Supposons M non maximum. Alors il existe un couplage M' tel que |M| < |M'|
On considère le graphe G' = (V, M $\bigoplus$ M')

:::info
4eme photo du 25/03/2019
:::

Nécessairement:

1. M $\bigoplus$ M' contient plus d'arêtes de M'
2. Chaque sommet de G' touche au plus une arête de M et au plus une arête de M'

==> Les sommets de G' qui ne sont pas isolés sont sur des chemins améliorant de G.

Algo pour trouver un couplage maximum:

- Partir d'un couplage quelconque (Par ex M = $\emptyset$)
- Répêter
- Tant qu'il existe un chemin améliorant P, faire: M <- M $\bigoplus$ P