Généralités sur les graphes

7. Généralités sur les graphes#

7.1. Définitions#

Definition 7.1 (Graphe)

  • Un graphe orienté est la donnée d’un ensemble de sommets \(S\) et d’arcs \(A\) sous la forme de couples \((s_i, s_j)\), où \(s_k\) est élément de \(S\).

  • Si, pour toute arcs \((s_i, s_j)\), \(A\) contient aussi l’arc \((s_j, s_i)\), on dit que le graphe est non orienté. On parle alors d’arêtes et on les notes sous forme d’ensemble.

  • Si l’ensemble des arcs contient des triplets de la forme \((s_i, s_j, p)\), avec \(s_k \in S\) et \(p \in ]0 ; +\infty[\), on dit que le graphe est pondéré.

Example 7.1

graph LR A((A)) --> B((B)) A --> C((C)) B --> D((D)) C --> D D --> A D --> C

En Python, on note un tel graphe sous la forme d’un dictionnaire, dont les clefs sont les sommets et les valeurs sont la liste des voisins.

Example 7.2 

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

7.2. Représentation avec les matrices#

Definition 7.2 (Matrice)

En mathématiques, une matrice est objet algébrique se ramenant à un tableau à \(n\) lignes et \(p\) colonnes. Si \( n = p\), on dit que la matrice est carrée.

Definition 7.3 (Matrice d’adjacence)

La matrice d’adjacence du graphe \(G = (\{s_1,...,s_n\}, \{(s_i, s_j), ..., (s_k, s_l)\})\) est un tableau de booléens (ou de nombres pour les graphes pondérés), contenant True dans la cellule \((i,j)\) si \((s_i,s_j)\) dans le graphe et False sinon.

Example 7.3 (Matrice d’ajacence de l’exemple)

M = [
  [False, True, True, False],
  [False, False, False, True],
  [False, False, False, True],
  [True, False, True, False]
]

Remark 7.1 (Coût de stockage)

Comme la matrice d’adjaence d’un graphe à \(n\) sommets est carrée de taille \(n^2\), le coût de stockage peut vite devenir important.

Contenu