Aller au contenu

Correction interrogation 30 avril 2025

Composantes fortement connexes d'un graphe⚓︎

Un graphe orienté est dit fortement connexe s’il existe un chemin entre chaque paire de sommets dans les deux sens.

Cela signifie que pour tout couple de sommets \( u \) et \( v \), il existe un chemin de \( u \) vers \( v \) et un chemin de \( v \) vers \( u \).

Une composante fortement connexe (CFC) d’un graphe est alors un sous-ensemble maximal

de sommets tels que chaque sommet est accessible Ă  partir de tous les autres du sous-ensemble.

Implémentatation pour déterminer la forte connexité d'un graphe.⚓︎

Nous allons utiliser deux fonctions (codes à compléter).

Fonction chemin (avec matrice d'adjacence)⚓︎

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def chemin(adj: list[list[int]], depart: int, dest: int) -> bool:
    """
    Entrées:    adj: la matrice d'adjacence du graphe
        depart: l'indice du sommet de depart
        dest: indice du sommet de destination
    Sortie : True si il existe un chemin entre depart et dest

    La fonction utilise une fonction annexe (Ă©crite ci dessous) dfs qui est celle du parcours en profondeur (depth first search)
    """

    n = len(adj)
    visite = [False] * n # Initialise une liste qui sert Ă  indiquer tous les sommets accessibles depuis depart

    def dfs(u):
        visite[u] = True
        for v in range(n):
            if adj[u][v] and not visite[v]:
                dfs(v)

    dfs(depart)
    return visite[dest]

fonction est_fortement_connexe⚓︎

Fonction qui indique si un graphe (orienté) est fortement connexe.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def est_fortement_connexe(adj: list[list[int]]) -> bool:
    n = len(adj)
    for u in range(n):
        for v in range(n):
            if u != v:
                # existe-il un chemin entre u et v ?:
                if not (chemin(adj,u,v)):  # en utilisant la fonction chemin 
            return False 

    # Tous les chemins ont été trouvés.
    return True