TD8 : Graphes et Structures de données

Énoncé

Arbres de poids minimum

1.


Kruskal(G):
  1) L liste ordonnée par poids croissant des arêtes
  2) F = ∅
  3) Tant que |F|<n-1 :
      a = premier(L)
      Si F+e a un cycle :
        virer e
      Sinon:
        l'ajouter

Complexité :

\[O(m \log m) = O(m \log n)\]

car $m$ = nb d’arêtes, donc

\[m≤\frac{n(n-1)}{2} ≤ n^2\]

et

\[O(\log m) = O(\log n)\]

Le test difficile : Si F+e a un cycle

On utilise la structure d’union find :

  • Au début : chaque sommet est sa racine
  • Puis : on fait des unions sans faire de cycle

Que veut dire “faire un cycle”?

⟶ pour toute arête $e=xy$,

  • si $racine(x)=racine(y)$ : on est dans le cas où un cycle est crée
  • sinon : ok, pas de cycle créé.

Ce qu’a démontré Tarjan :

Si on a :

  digraph {
    rankdir=BT;
    x -> ⋯;
    ⋯ ->r_x;
  }

si on demande la racine de $x$ : dans le même temps (on ne multiplie le temps que par 2), on fait une compression de chemin :

  digraph {
    rankdir=BT;
    x -> r_x;
    ⋯ ->r_x;
  }

L’analyse amortie montre que la complexité amortie est en $𝛼_{m,n}$ : preuve géniale, dont l’intuition nous échappe (cela concerne les nombre d’arbres, fibonacci, etc…).

Donc avec cette astuce, le test Si F+e a un cycle est en temps constant : l’opération la plus coûteuse est alors le tri de L.

NB : L’union find est très utilisé : il y a une variante avec des couleurs.

Tri : il existe des algorithmes presque linéaires (en $n\log\log\log ⋯ \log n$) n’utilisant pas de comparaisons.

Ces algos dépendent du hardware : ils utilisent les mots machines, pour représenter les données (mais ça dépend de la machine sur laquelle on l’exécute).

L’idée étant de rapprocher du tri radix par des méthodes de compression des données pour trier de manière plus efficace, puis décompresser.

⟶ Comment améliorer Kruskal ? : avec un algo de tri “linéaire”. __

Tri(L):
  1) F=∅, A={x_0}
  2) Tant que |A|≠n:
        choisir l'arête xy la plus petite du cocycle 𝜔(A)
        x∈A
        y∉A
        A = A+y

Maintenir un cocycle d’un ensemble :

graph {


		subgraph cluster_1 {
			label="Cocyle A";
			x; e;
		}

		y -- e;
		y -- x;
		b -- x;
		b -- e;
		c -- x;
		c -- e;
	}

⇓

graph {


		subgraph cluster_1 {
			label="Cocyle A";
			x; e; y;
		}

		y -- e;
		y -- x;
		b -- x;
		b -- e;
		c -- x;
		c -- e;
	}

On utilise un tas pour trier les arêtes :

complexité en \(O(m\log m) = O(m \log n)\)

En pratique : plus efficace que Kruskal.

2.

Pseudo-arbres-$k$ : quasiment des arbres, si $k$ petit.

⟶ mieux vaut “virer des arêtes, que les ajouter une à une” :

on reprend “à l’envers” les algos de Kruskal et Prim, en enlevant les arêtes de poids max.

4.

Poids max, poids min : c’est pareil, en remplaçant min par max et vice-versa.

5.

On prend le max au lieu du min.

6.

Condition suffisante : Si tous les poids sont distincts, l’arbre couvrant de poids min est unique.

Mais cette condition est trop forte :

  digraph {
    rankdir=TB;
    A -> B[label="4"];
    B -> C[label="2"];
    C -> A[label="2"];
  }

Les arêtes ne sont pas distinctes, mais il y a unicité.

7.

Première idée:

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

graph {
		a -- b -- d -- c -- f[color=red,penwidth=3.0];
		b -- c;
		d -- e;
    f--e[color=red,style=dashed];
		a -- d;
	}

⇓

graph {
		a -- b -- d -- c -- f[color=red,penwidth=3.0];
		b -- c;
		d -- e[color=blue,penwidth=3.0];
    f--e[color=red,style=dashed];
		a -- d;
	}

⇓

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

Si $(d,e) ≝ f((a,b))$ est l’arête minimisant

\[\lbrace 𝛥_{(f,e),(𝛼,𝛽)} \rbrace_{𝛼,𝛽∈V}\]

Et on calcule tous les $f((𝛼’,𝛽’))$, pour $(𝛼’, 𝛽’)$ une arête de l’arbre couvrant de départ, dont on note le minimum $(𝛼_{min}, 𝛽_{min})$.

Sans perte de généralité, si

\[(𝛼_{min}, 𝛽_{min}) = (d,e)\]

alors

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

est l’arbre couvrant de deuxième poids minimal.

Cet algo est valide si on passer de l’arbre couvrant de poids min à l’arbre couvrant de deuxième poids min en changeant un seule arête.

C’est le cas ! Démonstration en deux lignes avec les matroïdes.

8.

Leurs arêtes de plus poids sont identiques, car ils les suites des poids triés de leurs arêtes sont égales (elles sont minimales pour l’ordre lexicographique).

9.

Vérifier qu’un arbre couvrant donné est de poids min

NB : La classe des problèmes NP est celle des problèmes tels qu’il existe un certificat pour vérifier si une instance donnée est positive ou non.

Ex:

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

Comment vérifier que l’arbre rouge est de poids min ?

On peut tester en $O(n^2)$ de manière naïve, mais Tarjan a un algo en temps linéaire.

11.

Il existe des solutions ayant des diamètres différents :

  digraph {
    rankdir=TB;
    A -> B;
    B -> C;
    C -> D;
    C -> E;
  }

Diamètre : 3

  digraph {
    rankdir=TB;
    A -> B;
    B -> C;
    B -> D;
    B -> E;
  }

Diamètre : 2

Cas typique, où on veut minimiser un deuxième paramètre (le diamètre), en plus du premier paramètre (le poids).

12.

Arbre de Steiner : on veut déterminer l’arbre couvrant de poids min d’un sous-graphe du graphe de départ ⟶ NP-complet.

Les algos gloutons ne marchent plus (Prim échoue, par ex).

MAIS : ce problème est approximable !

Comment attaquer le problème ?

⟶ On considère la clique des sommets du sous-graphe, et on calcule l’arbre de poids min pour ces sommets ⟹ on n’est pas très loin (à un borne près) de la solution.

Leave a comment