Home
About

Connectivité

Cours/Théorie des graphes/Connectivité

Utilisation des flots pour démontrer les résultats de Menger sur la $k$-connectivité d'un graphe. Le but de ce projet est de répondre à question suivante :

Question

Soient deux sommets $s$ et $p$ d'un graphe (orienté) $G = (V, E)$, combien de chemins deux à deux disjoints relient $s$ et $p$ ?

Les résultats de cette parties vont être obtenus en utilisant judicieusement des flots.

Graphe orienté

Commençons par étudier cette question avec des graphes orientés. On note :

Montrez que $P(s, p) \leq N(s, p)$

solution

Comme les chemins sont disjoints, il faut au moins supprimer $P(s, p)$ arcs pour les déconnecter.

On considère le réseau formé de $G$, de la source $s$ et du puits $p$ et dont toutes les capacités valent $1$.

Montrez que $\mbox{val}(f) \leq P(s, p)$.

solution

Soit $f$ un flot maximum pour le réseau.

Comme les capacités valent toutes 1, chaque flux est soit 0 soit 1. De là tous les arcs sortant de $s$ de flux 1 vont créer des chemins disjoints vers $p$.

En utilisant une coupe min du flot max :

Montrez que $N(s, p) \leq \mbox{val}(f)$

solution

Sur une coupe minimum $(S, \overline{S})$, toutes les arêtes allant de $S$ vers $\overline{S}$ sont à 1 et sont au nombre de $\mbox{val}(f)$. Or si on supprime toutes ces arcs, on déconnecte $s$ de $p$ : $N(s, p) \leq \mbox{val}(f)$.

En déduire que :

$P(s, p) = N(s, p) = \mbox{val}(f)$

solution

On a les 3 inégalités :

  • $P(s, p) \leq N(s, p)$
  • $\mbox{val}(f) \leq P(s, p)$
  • $N(s, p) \leq \mbox{val}(f)$

Donc : $P(s, p) = N(s, p) = \mbox{val}(f)$

Quelle est la complexité de la recherche de $P(s, p)$ si on utilise l'algorithme de Ford et Fulkerson ? Est-elle polynomiale ?

solution

On a estimé la complexité à $\mathcal{O}(C\vert E\vert)$ où $C$ est la capacité d'une coupe. Si on prend comme coupe l'ensemble $s$ on a une complexité de : $\mathcal{O}(\delta^+(s) \vert E\vert) = \mathcal{O}(\vert V\vert \cdot \vert E\vert)$, ce qui est polynomial.

On peut maintenant chercher à trouver la forte arc-connectivité de $G$, c'est à dire le nombre minimum d'arcs à supprimer de $G$ pour le rendre non fortement connexe (il existe alors deux sommet $a$ et $b$ tel qu'il n'existe pas de chemin entre $a$ et $b$).

Proposez un algorithme (naïf) basé sur le résultat précédent pour connaître $k$ pour un graphe donné

solution

On teste pour chaque paire. Donc $\vert V\vert^2$ flots max à trouver, ce qui donne une complexité totale de : $\mathcal{O}(\vert V\vert^3 \cdot \vert E\vert)$.

On peut aller plus rapidement en prouvant la proposition suivante :

Proposition

En supposant une numérotation de $0$ à $n-1$ de $V$ ($V = \{x_0, \dots, x_{n-1}\}$), la forte arc-connectivité de $G = (V, E)$ est le minimum de $N(x_i, x_{i+1})$ lorsque $i$ varie de $0$ à $n-1$ et avec $x_n = x_0$.

Démontrer par l'absurde la proposition précédente.

solution

On suppose par l'absurde que le minimum de $N(x_i, x_{i+1})$ soit strictement plus grand que la forte arc connectivité de $G$ que l'on note $k$. En supprimant $k$ arcs je déconnecte $x_i$ de $x_j$. On a deux cas :

  • si $i < j$ alors comme on peut toujours aller de $x_k$ à $x_{k+1}$ pour tous $i \leq k < j$, il existe un chemin entre $x_i$ et $x_j$ ce qui est impossible.
  • si $j < i$ alors comme on peut toujours aller de $x_k$ à $x_{k+1}$ pour tous $j \leq k < n - 1$ il existe un chemin entre $x_i$ et $x_0$, puis un raisonnement identique nous indique qu'on peut aller de $x_0$ à $x_j$. Il existe donc un chemin entre $x_i$ et $x_j$ ce qui est impossible.

Trouver la forte arc connectivité d'un graphe orienté se fait donc en procédant à $\vert V \vert$ calcul de flot maximum.

En déduire un algorithme plus efficace que la solution naive pour résoudre le problème de l'arc connectivité d'un graphe orienté.

solution

On a plus que $\vert V\vert$ flots max à trouver, ce qui donne une complexité de $\mathcal{O}(\vert V\vert^2 \cdot \vert E\vert)$

Graphe non orienté

Lorsque le graphe $G = (V, E)$ est non orienté, on considère le graphe orienté $G^\star = (V, E')$ avec $xy$ et $yx$ comme arcs de $G'$ si $xy$ est une arête de $G$. On assigne de plus une capacité de 1 à tous les arcs de $G^\star$ et on note $f$ un de ses flot maximum.

En notant :

On considère le graphe ci-après :

flot Menger

Quel est son arc connectivité ?

solution

Ce graphe s'appelle le graphe de Petersen) graphe est 3 et 2 pour le second (il suffit de supprimer les arêtes rouges)

Et lui ?

flot menger

solution

flot menger

On voit de ces exemples que le degré minimum n'est que majorant de l'arc connectivité d'un graphe.

Montrez que pour tout graphe : $N(s, P) = N^\star(s, P) = P(s, p) = P^\star(s, p) = \mbox{val}(f)$

solution

  1. On a clairement que $N(s, p) \geq P(s, p)$.

  2. $P(s, p) \geq P^\star(s, p)$ De plus, $P(a, b) \geq P^\star(s, p)$. Si les $P^\star(s, p)$ chemins ne partagent pas d'arcs issus du dédoublement des arêtes en arcs, on peut créer $P^\star(s, p)$ chemins disjoints entre $s$ et $p$ dans $G$.

    Si 2 chemins partagent une arête $xy$ l'un l'$xy$ et l'autre l'arc $yx$, on peut procéder comme dans la figure ci-dessous pour créer 2 chemins partageant strictement moins d'arêtes.

    flot Menger

    On peut alors itérativement construire $P^\star(s, p)$ chemins ne partageant pas d'arcs issus du dédoublement des arêtes en arcs.

  3. $N(s, P) \geq N^\star(s, P)$ En supprimant $N^\star(s, p)$ arcs de $G^\star$ on déconnecte $s$ de $p$. Si on supprime les arêtes de $G$ qui ont donné naissance à ces arcs, on déconnecte $s$ de $p$ dans $G$. En effet, s'il restait un chemin entre $s$ et $p$ dans $G$, il en resterait également un dans $G^\star$.

    On a donc $N^\star(s, p) \geq N(s, p)$.

On a les inégalités suivantes : $N^\star(s, p) \geq N(s, p) \geq P(s, p) \geq P^\star(s, p)$

Or $P^\star(s, p) = N^\star(s, p) = \mbox{val}(f)$ ce qui conclut la preuve d'égalité.