Les Graphes

1. Qu’est-ce qu’un graphe ?

Un graphe est une structure mathématique utilisée pour modéliser des relations entre des objets appelés sommets (ou nœuds). Ces sommets sont reliés entre eux par des arêtes (ou arcs).

• Un graphe est donc un ensemble de sommets et un ensemble de arêtes qui relient ces sommets.

• Chaque arête connecte deux sommets, qui peuvent être les mêmes (boucle) ou différents.

1.1 Types de graphes

• Graphe non orienté : les arêtes n’ont pas de direction. Si un sommet A est relié à un sommet B, on peut aller de A vers B et de B vers A.

• Graphe orienté (ou digraphe) : les arêtes ont une direction. Une arête va d’un sommet A vers un sommet B, mais pas forcément dans l’autre sens.

• Graphe pondéré : chaque arête a un poids (exemple : distance, coût).

• Graphe simple : sans boucle ni arêtes multiples entre deux sommets.

• Graphe complet : chaque paire de sommets est reliée par une arête.

2. Représentations d’un graphe

Il existe plusieurs façons de représenter un graphe dans un programme informatique. Les plus courantes sont :

2.1 Liste d’adjacence (recommandée)

• Pour chaque sommet, on stocke la liste des sommets voisins (ceux auxquels il est connecté par une arête).

• Très efficace en mémoire, surtout si le graphe est creux (peu d’arêtes).

Exemple (graphe non orienté) :

graphe = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}

Ici, le sommet 0 est relié à 1 et 2, le sommet 1 est relié à 0 et 3, etc.

2.2 Matrice d’adjacence

• On crée une matrice carrée (taille = nombre de sommets),

• L’entrée [i][j] vaut 1 si une arête existe de i vers j, sinon 0,

• Utile pour les graphes denses (beaucoup d’arêtes) mais coûteux en mémoire.

Exemple (graphe non orienté, 4 sommets) :

matrice = [
	[0, 1, 1, 0],
	[1, 0, 0, 1],
	[1, 0, 0, 0],
	[0, 1, 0, 0]
]

3. Parcours de graphes

Traverser un graphe signifie visiter ses sommets dans un ordre spécifique. C’est une étape clé dans beaucoup d’algorithmes.

On distingue deux parcours classiques :

3.1 Parcours en profondeur (DFS - Depth First Search)

• Idée : on explore un chemin aussi loin que possible avant de revenir en arrière (backtracking),

• C’est une approche récursive ou basée sur une pile (stack),

• Utilisée pour détecter les cycles, trouver des composantes connexes, etc.

Principe de fonctionnement :

1. On commence par un sommet donné,

2. On marque ce sommet comme visité,

3. On explore récursivement chaque voisin non visité,

4. Quand on a fini tous les voisins, on revient en arrière.

Exemple en Python (avec liste d’adjacence) :

def dfs(graphe, sommet, visites=None):
    if visites is None:
        visites = set()  # ensemble des sommets visités
    visites.add(sommet)
    print(sommet)  # traiter ou afficher le sommet
    for voisin in graphe[sommet]:
        if voisin not in visites:
            dfs(graphe, voisin, visites)

3.2 Parcours en largeur (BFS - Breadth First Search)

• Idée : on visite tous les voisins d’un sommet avant de passer à leurs voisins,

• C’est une approche itérative basée sur une file (queue),

• Utilisée pour trouver le chemin le plus court dans un graphe non pondéré, etc.

Principe de fonctionnement :

1. On commence par un sommet initial,

2. On place ce sommet dans une file d’attente,

3. Tant que la file n’est pas vide :
   • On retire le sommet en tête,
   • On visite ce sommet,
   • On ajoute tous ses voisins non visités à la file.

Exemple en Python :

def bfs(graphe, sommet):
    visites = set()
    file = [sommet]  # la "file" est une liste ordinaire
    visites.add(sommet)

    while file:
        current = file.pop(0)  # retirer le premier élément (tête de file)
        print(current)  # traiter ou afficher le sommet
        for voisin in graphe[current]:
            if voisin not in visites:
                visites.add(voisin)
                file.append(voisin)  # ajouter à la fin (queue)

4. Applications classiques des graphes

• Réseaux sociaux : chaque personne est un sommet, les relations sont des arêtes,

• Itinéraires et transports : villes connectées par des routes,

• Systèmes informatiques : réseau d’ordinateurs ou dépendances entre logiciels,

• Jeux : déplacements possibles dans une grille ou un labyrinthe,

• Analyse linguistique : liens entre mots ou concepts.

5. Concepts supplémentaires utiles

5.1 Connexité

• Un graphe est connexe si on peut aller d’un sommet à n’importe quel autre via une chaîne d’arêtes,

• Sinon, il est constitué de plusieurs composantes connexes,

• Le DFS ou BFS peut aider à détecter et compter ces composantes.

5.2 Cycle

• Un cycle est un chemin qui commence et finit sur le même sommet,

• DFS peut détecter la présence de cycles,

• Utile pour déterminer si un graphe est un arbre (graphe connexe sans cycle).

5.3 Graphe pondéré et algorithmes

• Pour les graphes avec poids, des algorithmes comme Dijkstra ou Bellman-Ford permettent de trouver les plus courts chemins,

• Ces notions sont plus avancées mais importantes dans la suite des études.

6. Résumé