TD9 : Parcours

Énoncé

III.

On fait un parcours de graphe.

On ajoute $S$ aux ouverts.

Ouverts ⟵ S
Tant que Ouverts ≠ ∅
  x ⟵ choix(Ouverts)
  degré(père(x)) = degré(père(x))-1
  Si degré(père(x))=0
    alors ajouter père(x) à Ouverts
  virer(x, ouverts)

Arrêt :

vérifier qu’il existe un sommet unique racine de l’arborescence $A(S)$.

Liste des sommets dont on a modifié le degré et non visités : il ne doit en rester qu’un.

1. Couplage graphe biparti

1.

Algorithme glouton naïf.

2.

Non.

graph {
  a -- b[color=red,penwidth=3.0];
  b -- c[color=blue,penwidth=3.0];
  c -- d[color=red,penwidth=3.0];

}

3.

Seule la réciproque est non triviale.

Si $C$ n’est pas maximum, alors il existe un chemin $C$-augmentant.

Considérer la différence symétrique $C𝛥C_m$, où $C_m$ est maximum : il y a le même nombre, pair, d’arêtes appartenant à $C$, et appartenant à $C_m$.