Algorithmique : Graphes

Théorème d’Euler

Th d’Euler : un graphe connexe admet un pseudo-cycle eulérien (i.e un cycle qui passe par toutes les arêtes) ssi tous les degrés de ses sommets sont pairs.

(Fleury 1882) __

Tout graphe non orienté a un nombre pair de sommets de deg impair.

Dém considérer mod 2 l’égalité :

\[\sum_{x∈V(G), d(x) \text{ pair }} d(x) + \sum_{x∈V(G), d(x) \text{ impair }} d(x) = \sum_{x∈V(G)} d(x) = 2 \vert E(G) \vert\]

---

cf. le livre “Proof of the book” : en hommage à Erdös.

---

digraph {
    	  i -> c;
		    j -> {d, a};
        f -> {i,j};
        a -> c;
        c -> {g, f};
        b -> {d, e, h};
        e -> h;
        h -> b;
	}

---

Chemin :

passe une seule fois par un sommet

Marche :

peut passer plusieurs fois par un sommet.

---

Exercice : $G$ un graphe, $𝜎$ une numérotation.

Ordonner les listes d’ajacence selon $𝜎$ en temps linéaire.

---

Attention :

Quand on a une fonction croissante $r$ dans l’ensemble des parties qui vérifie la propriété de submodularité :

\[r(A∪B) + r(A∩B) ≤ r(A) + r(B)\]

il y a très probablement un algo polynomial derrière !

Matroïde de partitions :

$E$ une partition de ${\cal E}$.

• $E = (E_1, ⋯, E_k)$
• $d=(d_1, ⋯, d_k)$ entier
• $d_i ≤ \vert E_i \vert$

$M=(E, {\cal F})$

$F∈{\cal F}$

$∀i; 1≤i≤k :$

\[\vert F ∩ E_i \vert ≤ d_i\]

---

Antimatroïdes

Pareil que les matroïdes, mais stables par union.

Axiome d’anti-échange :

\[x∈Conv(S∪\lbrace y \rbrace ) ⟹ y \not∈ Conv(S∪\lbrace x \rbrace )\]

Antimatroïde :

pareil qu’un matroïde, mais stable par union plutôt que stable par intersection.

Ensembles convexes : leurs complémentaires = un antimatroïde.

---

Intersection de matroïdes

Couplage :

Ensemble d’arêtes 2 à 2 non adjacentes.

Un couplage correspond à l’intersection de deux matroïdes : les matroïdes de partition :

• $ℳ_1$ : Partition $\lbrace E_1, ⋯, E_n \rbrace$

  • $d_1 = ⋯ = d_n = 1$
  • $E_i$ : arêtes partant de $x_i$

• $ℳ_2$ : Partition $\lbrace E’_1, ⋯, E’_n \rbrace$

  • $d’_1 = ⋯ = d’_n = 1$
  • $E’_i$ : arêtes arrivant en $y_i$

mais cette intersection n’est pas, a priori, un matroïde !

Problème NP-complets les plus difficiles : les problèmes de pavage du plan.

---

Th d’Arora : pour certains problèmes, il n’y a pas de $c$ approximation pour un $c$ trop petit.

\[opt(I) ≤ opt_A(I) ≤ c opt(I)\]

Steiner Tree : approximable.

On aimerait avoir :

\[opt(I) ≤ opt_A(I) ≤ opt(I) + cste\]

mais ça n’arrive pas en pratique.

Ex :

$G$ planaire ⟹ 4 colorable.

$opt=1$, mais c’est un exercice de style.

Flots

Un graphe orienté où chaque arc est muni d’une capacité.