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é.

Leave a Comment