Les graphes

Les corrections des exercices du précédent cours sont disponibles à la fin de la page en question.

Définition

Un graphe est un couple $G = (S, A)$ où :

• $S$ est l'ensemble des sommets ;
• $A$ est l'ensemble des arêtes (ou arcs).

Pour un graphe non orienté, une arête est un ensemble ou paire non ordonnée ${u, v}$.

Pour un graphe orienté, une arête est un couple ordonné $(u, v)$ appelé arc.

Vocabulaire

Graphes non orientés

• Degré d’un sommet : nombre d’arêtes incidentes à ce sommet.
• Chaîne : suite de sommets où chaque sommet est relié au suivant par une arête.
• Cycle : chaîne fermée (on revient au point de départ). Toutes les arrêtes sont distinctes.
• Composante connexe : sous-graphe dans lequel tous les sommets sont reliés entre eux.
• Connexité : un graphe est connexe s’il n’a qu’une seule composante connexe.

Graphes orientés

• Degré entrant d’un sommet : nombre d’arcs qui arrivent vers ce sommet.
• Degré sortant : nombre d’arcs qui partent de ce sommet.
• Chemin : suite de sommets liée par des arcs orientés dans le bon sens.
• Circuit : chemin fermé (on revient au sommet de départ). Toutes les arrêtes sont distinctes.
• Composante fortement connexe : ensemble de sommets tels que chaque sommet est atteignable depuis tous les autres.
• Connexité : un graphe orienté est fortement connexe si toutes ses composantes fortement connexes sont fusionnées en une seule.

Lorsqu'on ignore l'orientation des arcs, on parle de faible conexité.

Cycles et circuits hamiltoniens

Les arrêtes d'un cycle ou d'un circuit sont toutes distinctes. Ce n'est pas forcément le cas des sommets.

Cycle/circuit hamiltonien : Cycle/circuit dans lequel aucun sommet n'est répété 2 fois (à l'exception du premier sommet qui est également le dernier).

Mieux retenir

Représentation en python

Matrices d'adjacence

• Matrice d’adjacence (graphe orienté) : matrice $M$ où $M[i][j] = 1$ s’il existe un arc de $i$ vers $j$ , sinon $0$.
• Matrice d’adjacence (graphe non orienté) : matrice symétrique où $M[i][j] = 1$ s’il existe une arête entre $i$ et $j$ .

Listes des voisins

• Liste de listes des voisins : indexée par les sommets (numérotés $S = \{0,1,2,… , n-1\}$), chaque case contient la liste de ses voisins.
• Dictionnaire de listes des voisins : utile lorsque les sommets ne sont pas numériques (ex : noms de villes), chaque clé étant un sommet.

Le parcours de graphe

Le but d’un parcours est d’explorer l’ensemble des sommets accessibles depuis un sommet donné, souvent pour : vérifier la connexité, rechercher un élément, ou calculer des distances.

Algorithme général

def parcours(voisins, s0):
    visites = []
    attente = [s0]

    while attente != []:
        s = attente.pop()
        visites.append(s)

        for v in voisins[s]:
            if v not in visites:
                attente.append(v)

    return visites

Parcours en profondeur avec une pile

Utiliser une pile signifie que .pop() retire le dernier élément ajouté : comportement LIFO (Last In, First Out). Cela donne un parcours en profondeur.

Parcours en largeur avec une file

Utiliser une file signifie que .pop() est remplacé par popleft(), retirant le premier élément ajouté : comportement FIFO (First In, First Out). Cela donne un parcours en largeur.

Parcours récursif naturel = Profondeur

Pour le parcours en profondeur il existe une version récursive qui est plus efficace au niveau de la complexité spaciale :

def parcours(voisins, s, visites = None):
    if visites is None: # Initialisation automatique
        visites = []

    if s in visites:
        return visites

    visites.append(s)

    for v in voisins[s]:
        parcours(voisins, v, visites)

    return visites

Est-ce que tu comprends la notation dans la ligne def parcours(voisins, s, visites = None) ?