Un graphe est une structure de données composée de nœuds (ou sommets) et d'arêtes qui décrivent les relations entre ces nœuds. Les graphes sont utilisés pour modéliser des réseaux, des relations sociales, des itinéraires, etc.

1. Introduction aux graphes

• Un graphe est une structure de données utilisée pour représenter des relations entre des objets.
• Il se compose de sommets (ou nœuds) reliés entre eux par des arêtes (ou arcs).
• Les graphes peuvent être orientés (les arêtes ont une direction) ou non orientés.
• Les graphes peuvent être pondérés (les arêtes ont un poids) ou non pondérés.

2. Représentation des graphes en Python

• Liste d'adjacence :
  • Chaque sommet est représenté par un dictionnaire.
  • La clé du dictionnaire est le sommet lui-même, et la valeur est une liste des sommets adjacents.
  • Exemple de code Python : 

  graph = {
      'A': ['B', 'C'],
      'B': ['A', 'C', 'D'],
      'C': ['A', 'B', 'D'],
      'D': ['B', 'C']
  }

• Matrice d'adjacence :
  • Utilise une matrice pour représenter le graphe.
  • Les lignes et les colonnes représentent les sommets.
  • La valeur à l'intersection de la ligne i et de la colonne j représente s'il y a une arête entre les sommets i et j.
  • Exemple de code Python :

  graph = [
      [0, 1, 1, 0],
      [1, 0, 1, 1],
      [1, 1, 0, 1],
      [0, 1, 1, 0]
  ]

3. Parcours de graphe en Python

• Parcours en profondeur (Depth-First Search - DFS) :
  • Visite un sommet, explore ensuite tous ses voisins avant de passer au sommet suivant.
  • Utilise une pile pour gérer les sommets à explorer.
  • Exemple de code Python :

  def dfs(graph, start):
      visited = set()
      stack = [start]
      while stack:
          vertex = stack.pop()
          if vertex not in visited:
              visited.add(vertex)
              stack.extend(set(graph[vertex]) - visited)
      return visited
          

• Parcours en largeur (Breadth-First Search - BFS) :
  • Visite un sommet, explore ensuite tous ses voisins avant de passer aux sommets voisins des voisins.
  • Utilise une file d'attente pour gérer les sommets à explorer.
  • Exemple de code Python :

  def bfs(graph, start):
      visited = set()
      queue = [start]
      while queue:
          vertex = queue.pop(0)
          if vertex not in visited:
              visited.add(vertex)
              queue.extend(set(graph[vertex]) - visited)
      return visited
          

4. Exemples d'utilisation des graphes

• Recherche de chemin le plus court : Utilisation de l'algorithme de Dijkstra ou de l'algorithme A.
• Recherche de cycle dans un graphe : Utilisation de l'algorithme de détection de cycle (par exemple, l'algorithme de détection de cycle basé sur DFS).
• Flux maximal dans un graphe : Utilisation de l'algorithme de Ford-Fulkerson ou de l'algorithme d'Edmonds-Karp.

Exercices - corrigés: les graphes

Exercice 1: ★ ☆ ☆ ☆ ☆

Considérez le graphe suivant :

a) Les sommets adjacents au sommet A sont B,C et D.
b) Les sommets adjacents au sommet D sont A, E et G.
c) Les sommets voisins du sommet F sont B, E et G.
d) Le plus court chemin entre les sommets A et F est A - B - F, donc sa longueur est 2.
e) Les sommets qui sont à une distance de 2 par rapport au sommet A sont E,F et G.

Exercice 2: ★ ☆ ☆ ☆ ☆

Considérez le graphe suivant :

a) Les sommets adjacents au sommet C sont A, D et F.
b) Les sommets adjacents au sommet E sont B, D et G.
c) Les sommets voisins du sommet B sont A, D et E.
d) Le plus court chemin entre les sommets A et G est A - D - G, donc sa longueur est 2.

Exercice 3: ★ ☆ ☆ ☆ ☆

Considérez le graphe suivant :

a) Les sommets adjacents au sommet B sont A, C, F et G.
b) Les sommets adjacents au sommet F sont B et G.
c) Les sommets voisins du sommet G sont B et H.
d) Le nombre de chemins de longueur 2 entre les sommets A et I est 2 (A - B - C et A - B - G).
e) Le chemin le plus court entre les sommets D et G est D - E - F - G, donc sa longueur est 3.

Exercice 4: ★ ☆ ☆ ☆ ☆

Considérez le graphe suivant :

a) Les sommets adjacents au sommet E sont A, B, H et I.
b) Les sommets adjacents au sommet I sont E, F, H et J.
c) Les sommets voisins du sommet F sont B, C, E, G et I.
d) Le nombre de chemins de longueur 3 entre les sommets A et G est 4 (A - B - C - G, A - B - F - G, A - D - E - F - G et A - D - H - I - J).
e) Le chemin le plus court entre les sommets D et J est D - H - I - J, donc sa longueur est 3. 

def nombre_de_sommets(graphe):
    return len(graphe)
    
# Exemple d'utilisation
graphe = [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
print(nombre_de_sommets(graphe))  # Résultat : 4

Exercice 6: ★ ★ ☆ ☆ ☆

Écrivez une fonction Python qui prend en entrée un graphe non orienté sous forme de liste d'adjacence et qui renvoie le degré d'un sommet donné.

def degre_sommet(graphe, sommet):
    return len(graphe[sommet])

# Exemple d'utilisation
graphe = [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
sommet = 1
print(degre_sommet(graphe, sommet))  # Résultat : 3

Exercice 7: ★ ★ ★ ☆ ☆

Écrivez une fonction Python qui prend en entrée un graphe non orienté sous forme de liste d'adjacence et qui renvoie tous les voisins d'un sommet donné.

def voisins_sommet(graphe, sommet):
    return graphe[sommet]

# Exemple d'utilisation
graphe = [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
sommet = 2
print(voisins_sommet(graphe, sommet))  # Résultat : [0, 1, 3]

Exercice 8: ★ ★ ★ ☆ ☆

Écrivez une fonction Python qui prend en entrée un graphe non orienté sous forme de liste d'adjacence et qui renvoie True si deux sommets donnés sont adjacents, sinon False.

def sont_adjacents(graphe, sommet1, sommet2):
    return sommet2 in graphe[sommet1]

# Exemple d'utilisation
graphe = [[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
sommet1 = 0
sommet2 = 2
print(sont_adjacents(graphe, sommet1, sommet2))  # Résultat : True