Home
About

Chemins, cycles et connexité

Auteur :
  • François Brucker
Cours/Théorie des graphes/Chemins, cycles et connexité

Chemins, cycle et connexité dans les graphes : définitions et premières propriétés.

Un graphe $G=(V, E)$ rend compte d'une relation (les arêtes) entre des objets (les sommets). Une grande part des applications des graphes viennent du fait que l'on cherche à décrire ou parcourir objets en suivant localement les relations. Cette courte partie vise à poser les diverses définitions relatives à ces notions et à exhiber quelques propriétés soit utiles, soit belles à démontrer, soit les deux.

Chemin, cycles et circuits

Définition

Soit $G = (V, E)$ un (multi-)graphe (non) orienté. Un chemin allant de $v_0$ à $v_{k}$ est une suite finie :

$$C = v_0v_1\dots v_i \dots v_{k}$$

de sommets du graphe telle que :

  1. $v_iv_{i+1}$ soit une arête (resp. arc) du graphe quelque soit $0 \leq i < k$
  2. les arcs (resp. arêtes) sont deux à deux distinctes.

Le chemin $C$ à une longueur de $k$ (c'est le nombre d'arêtes). Un chemin de longueur $0$ est le chemin contenant un unique sommet, sans arc (resp. arête).

On peut affaiblir la notion de chemin pour les graphes orienté :

Définition

Soit $G = (V, E)$ un (multi-)graphe orienté. Une chaîne est une suite :

$$C = v_0v_1\dots v_i \dots v_{k}$$

de sommets du graphe telle que :

  1. soit $v_iv_{i+1}$ soit $v_{i+1}v_i$ est un arc du graphe pour tout $0 \leq i < k$
  2. les arcs sont deux à deux distincts.

La chaîne $C$ à une longueur de $k$ (c'est le nombre d'arcs).

Un chemin nous permet de définir un cycle pour les graphes non-orientés :

Définition

Soit $G = (V, E)$ un (multi-)graphe non orienté. Un cycle est un chemin

$$C = v_0v_1\dots v_i \dots v_k$$

tel que $v_0 = v_k$

La cycle $C$ à une longueur de $k$ (c'est le nombre d'arêtes).

Pour les graphes orientés, ça se complique un peu car on a coutume de différentier cycle (le sens de l'arc est indifférent) de circuit (on peut parcourir le cycle dans l'ordre) :

Définition

Soit $G = (V, E)$ un (multi-)graphe orienté. Un cycle est une suite finie :

$$C = v_0v_1\dots v_i \dots v_k$$

de sommets du graphe telle que :

  1. soit $v_iv_{i+1}$ soit $v_{i+1}v_i$ est un arc du graphe quelque soit $0 \leq i < k$
  2. les arcs sont deux à deux distinctes.
  3. $v_0 = v_k$

Définition

Soit $G = (V, E)$ un (multi-)graphe orienté. Un circuit est un cycle :

$$C = v_0v_1\dots v_i \dots v_k$$

de sommets du graphe telle que $v_iv_{i+1}$ est un arc du graphe quelque soit $0 \leq i < k$

Terminons cette partie par un petit exercice :

Montrer qu'un tournoi $G = (V, E)$ n'admet pas de cycle si et seulement si la relation $xRy \Leftrightarrow xy \in E$ est transitive.

solution

Si la relation n'est pas transitive il existe $x$, $y$ et $z$ tels que $xy$ et $yz$ mais pas $xz$, ce qui implique que $xyzx$ est un cycle.

Réciproquement, s'il existe un cycle, prenons en un de longueur minimum : $c_0c_1c_2 \dots c_k$. Comme le cycle est de longueur minimum, $c_0c_2$ n'est pas une arête : le tournoi n'est pas transitif.

Chemins et cycles élémentaires

Les définitions de chemins et cycles supposent que les arêtes ou arcs n'apparaissent pas deux fois. Si cette précaution permet d'éviter les chemin de taille infini, certains problèmes nécessitent de pouvoir passer plusieurs fois par les mêmes arêtes ou au contraire de ne passer qu'une seule fois par chaque sommet :

Définition

Soit $G = (V, E)$ un graphe orienté. Un pseudo-chemin est une suite finie $C = v_0v_1\dots v_i \dots v_{k}$ une suite de sommets du graphe telle que $v_iv_{i+1}$ est un arc du graphe quelque soit $0 \leq i < k$.

Définition

Soit $G = (V, E)$ un graphe orienté. Un chemin élémentaire (resp. cycle ou circuit élémentaire) est un chemin (resp. cycle ou circuit) $C = v_0v_1\dots v_i \dots v_{k}$ tel que $v_i \neq v_j$ quelque soit $i \neq j$.

Notez qu'un pseudo-chemin/pseudo-cycle/pseudo-circuit où chaque sommet n'apparaît qu'une seule fois est forcément un chemin/cycle/circuit élémentaire !

Ces notions sont bien sûr liées comme le montre les deux propositions ci-dessous :

Proposition

  • De tout pseudo-chemin, pseudo-chaîne, pseudo-cycle ou pseudo-circuit allant de $x$ à $y$ on peut extraire un chemin, chaîne, cycle ou circuit allant de $x$ à $y$.
  • De tout chemin, chaîne, cycle ou circuit allant de $x$ à $y$, on peut extraire un chemin, chaîne, cycle ou circuit élémentaire allant de $x$ à $y$.

Preuve

Nous n'allons faire la preuve que pour les chemins. Les autres preuves sont équivalentes.

Soit $G=(V, E)$ un graphe et $c=v_0 \dots v_p$ un de ses pseudo-chemins qui n'est pas un chemin. Il existe donc $i < j$ tel que $v_iv_{i+1} = v_jv_{j+1}$ et $c'= v_0\dots v_iv_{j+1}\dots v_k$ est un autre pseudo-chemin allant de $v_0$ à $v_k$ ayant strictement moins de répétition d'arêtes que $c$ : on peut itérativement supprimer les répétitions d'arêtes d'un pseudo-chemin pour obtenir un chemin.

De là même manière, si $c=v_0 \dots v_p$ est un chemins non élémentaire, il existe $i < j$ tel que $v_i = v_j$ : le chemin $c' = v_0 \dots v_iv_{j+1}\dots v_k$ est un autre chemin allant de $v_0$ à $v_k$ ayant strictement moins de répétition de sommets que $c$ : on peut itérativement supprimer les répétitions de sommets d'un chemin pour obtenir un chemin élémentaire.

La réduction d'un pseudo-cycles (ou pseudo-circuit) peut engendrer un cycle (ou circuit) de longueur nulle ! Ce n'est pas le cas pour tous les autres cas.

Connexité

Définition

Un graphe est dit connexe si pour toute paire de sommets $x$ et $y$ il existe un chemin allant de $x$ à $y$ dans $G$.

Si le graphe est orienté :

  • il est connexe si pour toute paire de sommets $x$ et $y$ il existe un chemin allant de $x$ à $y$ ou un chemin allant de $y$ à $x$ dans $G$.
  • il est dit fortement connexe s'il existe pour toute paire $x$ et $y$ de sommet un chemin allant de $x$ à $y$ et un chemin allant de $y$ à $x$.

La connexité est une notion très importante en théorie des graphes. Elle permet de relier deux sommets entre eux par des relations. D'un point de vue pratique on aime bien les graphes connexes, pensez à google maps où l'on aime bien pouvoir faire des aller-retours.

Définition

Soit $G=(V, E)$ un graphe orienté ou non.

  • Un ensemble connexe $Y \subseteq V$ de $G$ est tel que quelque soit $x \neq y \in Y$ il existe un chemin entre $x$ et $y$ ou entre $y$ et $x$.
  • Un ensemble fortement connexe $Y \subseteq V$ de $G$ est tel que quelque soit $x \neq y \in Y$ il existe un chemin entre $x$ et $y$ et entre $y$ et $x$.
  • Une composante (fortement) connexe $Y \subseteq V$ de $G$ est un ensemble (fortement) connexe maximal pour l'inclusion.

Les composantes connexes d'un graphe $G$ forment ainsi un Souvent (toujours) si un graphe n'est pas connexe on le partitionnera en ses composantes connexes qui peuvent être vues en vertu de la proposition suivante comme des graphes distincts que l'on peut analyser séparément.

Proposition

Si $G=(V, E)$ est un graphe, l'ensemble $\mathcal{C} = { V_1, \dots, V_p }$ de ses composantes connexe est une partition :

  • $V_i \cap V_j = \varnothing$ si $i \neq j$
  • quelque soit $x \in V_i$ et $y\in V_j$ avec $i \neq j$, $xy \notin E$
  • $ \sum_i V_i = V$

Si le le graphe est orienté, on a le même résultat en considérant l'ensemble de des composantes fortement connexes.

preuve

L'union de deux ensemble fortement connexes non disjointes est encore un ensemble fortement connexe : deux composantes fortement connexes sont forcément disjointes.

Les composantes connexes d'un graphe orienté ne sont pas forcément disjointes, comme le montre l'exemple ci-après :

g carré g solution

Enfin, Du point de vue de la connexité, certains sommet ou arêtes sont plus important que d'autres :

Définition

Soit $G$ un graphe connexe.

  • Un isthme est une arête qui déconnecte le graphe si on la supprime
  • Un nœud d'articulation est un sommet qui déconnecte le graphe si on le supprime

Par exemple, dans des réseau routiers, les isthme et les nœuds n'articulations vont créer des bouchons s'ils sont saturés (le tunnel sous Fourvière par exemple).

Finissons par définir la $k$-connexité :

Définition

Un graphe est dit $k$-connexe si la suppression de $k-1$ sommet de déconnecte pas $G$.

Il est clair qu'un graphe est connexe si et seulement si il est $1$-connexe. Les graphes 2-connexes vont avoir une certaine importance plus tard (lorsque l'on parlera de colorabilité et de planarité des graphes). Ils permettent d'avoir des graphes connexes qui résistent à la suppression d'un sommet. Les cycles sont un exemple canoniques de graphes 2-connexes :

Soit $G$ un graphe 2-connexe. Montrez que quelques soient $u \neq v$ deux de ses sommets, il existe un cycle dans $G$ passant par $u$ et $v$.

corrigé

TBD

Propriétés fondamentales d'existence

On le verra plus précisément lorsque l'on parlera d'arbres, mais les notions de connexités, de chemins et de cycles (notions globales) sont très liés aux degrés des différents sommets (conditions locales). Les propositions fondamentales d'existence ci après le montrent. Bien qu'elles soient très simples, elles se révèlent souvent utile, soit par les propriétés elles-mêmes soit par leurs schémas de preuves qui s'appliquent très souvent.

Commençons par donner des condition d'existence de chemins et cycles de longueur donnée :

Proposition

Soit $G = (V, E)$ un graphe. S'il existe un entier $k > 1$ tel que $\delta(x) \geq k$ pour tout $x \in V$, alors :

  • pour tout $x \in V$ il existe un chemin élémentaire de longueur $k$ partant de $x$ ,
  • il existe un cycle élémentaire de longueur au moins $k+1$,

Preuve

Soit $c = v_0\dots v_i$ un chemin de longueur $i < k$ partant de $x = v_0$ (pour $i = 0< k$, ce chemin est réduit au seul point $x$).

Comme $\delta(v_i) = k > i$ il existe un voisin $y$ de $v_i$ qui n'est pas un élément du chemin. On peut donc nommer $v_{i+1} = y$ et étendre $c$ d'un élément à $c= v_0\dots v_iv_{i+1}$. Ceci montre que l'on peut étendre $c$ à un chemin de longueur $k$.

Une fois que $c = v_0\dots v_i$ a atteint la longueur $k$, on peut continuer cette procédure en cherchant à agrandir $c$ par un sommet $v_{i+1}$ tel que :

  • $v_iv_{i+1}$ est une arête du graphe
  • n'ayant aucun sommet $v_j$ avec $i+1 - k < j < i+1$ comme voisin (il y en a $k-1$)

De deux choses l'une :

  1. soit $v_{i+1}$ n'a aucun voisin dans $c$, on peut agrandir $c$ et recommencer
  2. soit $v_{i+1}$ a un voisin dans $c$ et on a trouvé un cycle de longueur au moins $k+1$

Par finitude du graphe il arrivera forcément un moment où l'on atteindra le cas 2 ce qui conclut la preuve.

Deux petits exercices pour montrer que la proposition précédente s'étend aux graphes orientés :

Soit $G = (V, E)$ un graphe orienté. S'il existe un entier $k \geq 1$ tel que $\delta^+(x) \geq k$ pour tout $x \in V$, alors :

  • pour tout $x \in V$ il existe un chemin élémentaire de longueur $k$ partant de $x$ ,
  • il existe un circuit élémentaire de longueur au moins $k+1$,

corrigé

La preuve est identique à la proposition précédente puisqu'on ne fait que considérer les arêtes sortantes dans la preuve.

Soit $G = (V, E)$ un graphe orienté. S'il existe un entier $k \geq 1$ tel que $\delta^-(x) \geq k$ pour tout $x \in V$, alors :

  • pour tout $x \in V$ il existe un chemin élémentaire de longueur $k$ finissant en $x$ ,
  • il existe un circuit élémentaire de longueur au moins $k+1$,

corrigé

La preuve est identique à l'exercice précédent en allant à reculons dans la création du cycle.

De même pour garantir la connexité d'un graphe :

Proposition

Un graphe $G=(V, E)$ tel que (avec $\vert V \vert = n$ et $\vert E \vert = m$) :

$$ m > \frac{(n-1)(n-2)}{2} $$

est connexe.

Preuve

On montre la preuve par récurrence. Si $n=2$, il faut évidemment avoir $m > 0$ pour que le graphe soit connexe. On suppose la propriété vraie pour $\vert V \vert = n-1$ et on se place à $\vert V \vert = n \geq 2$.

Si le graphe est complet on a $m = \frac{n(n-1)}{2} > \frac{(n-1)(n-2)}{2}$ et le graphe est trivialement connexe. Il existe donc un sommet $x$ de degré $\delta(x) < n-1$. De plus, s'il existait un sommet sans voisin, le nombre d'arêtes serait strictement plus petit $\frac{(n-1)(n-2)}{2}$ ce qui est impossible. On a donc également $\delta(x) \geq 1$.

Le nombre d'arêtes $m'$ du sous-graphe $G'$ induit par la suppression de $x$ dans $G$ vaut :

$$ \begin{array}{ccl} m' & = & m - \delta(x) \\ &\geq &m - (n-2) \\ &> &\frac{(n-1)(n-2)}{2} - (n-2)\\ &> &\frac{(n-2)(n-3)}{2}\\ \end{array} $$

Le graphe $G'$ est donc connexe par hypothèse de récurrence, donc $G$ l'est aussi puisque $\delta(x) > 0$ (la composante connexe contenant $x$ intersecte $V \backslash { x}$ qui est un ensemble connexe de $G$).

Notez bien que ces propositions ne sont que des implications. Si l'on prend le graphe $G=(\{v_1, \dots, v_n\}, E)$ avec $E = \{ v_iv_{i+1} \mid 1 \leq i \leq n \} \cup \{ v_1v_n \}$ il :

Algorithmes

On utilisera le graphe suivant pour nos algorithmes :

G = {
    "a": {"b", "c"},
    "b": {"a", "c"},
    "c": {"a", "b"},
    "d": set()
}

L'encodage par défaut des graphes sera toujours celui par dictionnaires.

Algorithme de recherche de composante connexe

def composante_connexe(G, origine):
    composante = {origine}
    suivant = [origine]

    while suivant:
        x = suivant.pop()

        for y in G[x]:
            if y not in composante:
                composante.add(y)
                suivant.append(y)

    return composante

On utilise :

Complexité

L'algorithme précédent utilise un ensemble pour stocker la composante connexe car :

Pour une liste :

La complexité de l'algorithme va ainsi dépendre :

Pour notre encodage, Toutes les opérations élémentaires de l'algorithme sont donc en $\mathcal{O}(1)$ opérations au maximum sauf le test de la ligne 9 et l'ajout à la composante de la ligne 10 qui est en $\mathcal{O}(1)$ opérations en moyenne.

Enfin, comme chaque sommet ne peut-être ajouté à suivant que s'il n'est pas encore dans la composante, chaque sommet ne peut y être ajouté qu'une fois : il y a au pire $\vert V \vert$ itérations de la boucle while de la ligne 5 et chaque sommet ne peut être choisi qu'au pire 1 fois comme élément x de la ligne 6. Et pour chaque élément la complexité de la boucle while sera de l'ordre de $\mathcal{O}(\delta(x))$ opérations en moyenne (le nombre de fois où l'on rentre dans la la boucle for)

On en conclut :

La complexité de l'algorithme composante_connexe est pour un graphe encodé par dictionnaire de $\mathcal{O}(\vert E\vert)$ opérations en moyenne.

Il est donc linéaire en moyenne par rapport à la taille du graphe en entrée.

Dans le cas où l'encodage du graphe est une liste d'adjacence, on peut changer la structure de composante pour que sa complexité (maximale) soit en $\mathcal{O}(\vert E \vert)$ opérations.

Quelle est cette structure ?

solution

Dans le codage par liste d'adjacence, les sommets sont des entiers entre $0$ et $n-1$. On peut alors utiliser une liste de $n$ booléens pour composante. On place composante[i] à True lorsque l'on place le sommet $i$ dans la composante.

Toutes les opérations sur composante effectuée par l'algorithme sont en $\mathcal{O}(1)$ opérations au maximum.

Preuve

L'algorithme va progresser de voisinage en voisinage et ajouter petit à petit les éléments qu'il n'a pas encore vu. S'il existe un chemin entre $x$ et $y$, $y$ chaque élément de ce chemin va être petit à petit intégré à la composante.

Toutes les composantes

Utilisez l'algorithme composante_connexe(G, origine) pour créer un algorithme qui rend toutes les composantes connexe d'un graphe.

solution

 
def les_composantes(G):
    composantes = []

    dans_une_composante = set()

    for x in G:
        if x in dans_une_composante:
            continue

        composantes.append(composante_connexe(G, x))
        dans_une_composante.update(composantes[-1])

    return composantes

Pour s'assurer de ne pas refaire plusieurs fois la même composante connexe, on stocke dans un ensemble les sommets déjà vu. On utilise pour cela le mot clé continue.

Algorithme de recherche de composante fortement connexe

TBD lien

Notez qu'il existe un autre algorithme utilisant le parcours en profondeur et que nous verrons plus tard qui permet de faire la même chose avec une complexité linéaire (c'est à dire la taille du graphe): $\mathcal{O}(\vert E \vert)$.

Trouver un chemin

L'algorithme suivant, nommé chemin, prend un graphe et deux sommets $a$ et $b$ en paramètres. Il rend soit un chemin entre $a$ et $b$ s'il existe soit le chemin vide si $a$ et $b$ sont dans deux composantes connexes différentes.

def chemin(G, a, b):
    examinés = {a}
    chemin = [a]

    x = a
    while x != b:
        suivants = G[x] - examinés
        if suivants:
            y = suivants.pop()
            examinés.add(y)
            chemin.append(y)
        else:
            chemin.pop()

        if chemin:
            x = chemin[-1]
        else:
            break

    return chemin

On utilise :

Complexité

La complexité de chaque itération while de la ligne 6 et de l'ordre de $\mathcal{O}(\delta(x))$ opérations car il faut trouver un voisin non encore examiné. Comme à chaque fois qu'un voisin est utilisé, il est examiné, un même sommet pourra être le x de la boucle while au maximum $\delta(x)$ fois. De là, la complexité globale de l'algorithme est de l'ordre de :

$$ C = \mathcal{O}(\sum_x (\delta(x))^2) \leq \mathcal{O}((\sum_x \delta(x))^2) = \mathcal{O}((2 \vert E \vert)^2) = \mathcal{O}(\vert E \vert^2) $$

TBD lien

Notez que cet algorithme recalcule plein de fois la même chose : tous les voisins de $x$.

La encore, Une version optimisée de cet algorithme peut être faite avec le parcours en profondeur et que nous verrons plus tard, permet de faire la même chose avec une complexité linéaire (c'est à dire la taille du graphe): $\mathcal{O}(\vert E \vert)$.

Preuve

Le preuve de l'algorithme repose sur la proposition suivante :

Proposition

Soit $G = (V, E)$ un graphe connexe et $a, b\in V$.

S'il existe un chemin allant de $a$ à $x$ :

  • ne passant pas par $b$
  • tel que tous les voisins de $x$ soient dans le chemin

Alors il existe un chemin allant de $a$ à $b$ ne passant pas par $x$.

Preuve

Soit $c= a\dots x = v_0\dots v_p$ le chemin allant de $a$ à $x$ et $c' = a \dots b = w_0\dots w_q$ un chemin allant de $a$ à $b$ passant par $x$.

On note $1 \leq i < q$ le plus grand indice tel qu'il existe $1\leq j < p$ avec $w_i = v_j$. Comme $x$ est sur $c'$ :

  • cet élément existe
  • il est placé après $x$ dans $c'$

Le chemin $v_0 \dots v_i w_{j+1} \dots w_q$ est un chemin allant de $a$ à $b$ ne passant pas pas $x$.

Trouver un circuit ou un cycle

Pour trouver un cycle, on se place dans le cadre de la proposition sur les degrés, en partant d'un sommet $a$ donné.

L'algorithme ne fonctionne que dans le cadre de la proposition.

def circuit(G, a):
    chemin = [a]

    x = a
    while not G[x].intersection(chemin):
        x = set(G[x]).pop()
        chemin.append(x)

    début = (G[x].intersection(chemin)).pop()
    i = chemin.index(début)

    return chemin[i:] + [début]

Il faut s'assurer que l'on n'utilise pas l'arête retour lorsque le graphe est non orienté :

def cycle_non_orienté(G, a):
    chemin = [a]

    x = a
    while not G[x].intersection(chemin[:-2]):
        x = (G[x] - set(chemin[-2:])).pop()
        chemin.append(x)

    début = (G[x].intersection(chemin[:-2])).pop()
    i = chemin.index(début)

    return chemin[i:] + [début]