Aller au contenu

TNSI : Représentations des Graphes en Python⚓︎

On peut représenter les graphes de plusieurs manières:

  • Matrices d'adjacences
  • Listes d'adjacences:
  • listes des voisins (graphes non orientés)
  • listes des successeurs, ou des prédécesseurs (graphes orientés)

Matrice d'Adjacence⚓︎

Def

Une matrice est un tableau de nombres. elle peut être représentée en Python facilement :

  • par une liste de listes en Python (par défaut)
  • un dictionnaire En notant \(A\) une certaine matrice, Alors A[i][j] désigne l'élément situé à la ligne i et à la colonne j

Matrice d'Adjacence d'un graphe NON pondéré⚓︎

Matrice d'Adjacence d'un graphe NON pondéré

Un graphe (orienté, ou pas) peut être représenté par une matrice d'adjacence :

  • tout lien depuis le sommet i vers le sommet j, est représenté par A[i][j] = 1
  • Une absence de lien du sommet i vers le sommet j, est représenté par A[i][j] = 0

Exp

G000->0110->11->1221->2331->32:e->2:s3->2

Graphe 1

G00110--1220--21--2331--3441--42--33--4

Graphe 2
\(M_1=\begin{pmatrix} 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0\\ \end{pmatrix} \)
Matrice d'adjacence Graphe 1
Matrice NON Symétrique
\(M_2=\begin{pmatrix} 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 0\\ \end{pmatrix} \)
Matrice d'adjacence Graphe 2
Matrice Symétrique
# Matrice Adjacence en Liste de Listes :
M1 = [[1, 1, 0, 0],
      [0, 1, 1, 1],
      [0, 0, 1, 0],
      [0, 0, 1, 0]]

# Matrice Adjacence en Liste de Listes :
M2 = [[0, 1, 1, 0, 0],
      [1, 0, 1, 1, 1],
      [1, 1, 0, 1, 0],
      [0, 1, 1, 0, 1],
      [0, 1, 0, 1, 0]]

# Matrice Adjacence en Dictionnaire (Graphes Étiquetés) :
M1 = {0 : [1, 1, 0, 0],
      1 : [0, 1, 1, 1],
      2 : [0, 0, 1, 0],
      3 : [0, 0, 1, 0]}

# Matrice Adjacence en Dictionnaire (Graphes Étiquetés) :
M2 = {0 : [0, 1, 1, 0, 0],
      1 : [1, 0, 1, 1, 1],
      2 : [1, 1, 0, 1, 0],
      3 : [0, 1, 1, 0, 1],
      4 : [0, 1, 0, 1, 0]}

Matrice Symétrique

Notons \(A=(a_{ij})\) la matrice d'adjacence.
On dit que la matrice d'adjacence est symétrique \(\Leftrightarrow\) \(a_{ij}=a_{ji}\) pour tous les \(i,j\)

Matrice d'Adjacence d'un graphe Pondéré⚓︎

Matrice d'Adjacence d'un graphe pondéré

Un graphe pondéré (orienté, ou pas) peut être représenté par une matrice d'adjacence :

  • tout lien depuis le sommet i vers le sommet j, est représenté par \(A[i][j] = a_{ij}\) où \(a_{ij}\) désigne le poids du lien du sommet i vers le sommet j
  • Une absence de lien du sommet i vers le sommet j, est représenté par A[i][j] = 0

Exp

G000->03110->121->14221->20.5331->30.22:e->2:s0.63->25

Graphe 3 Orienté

G00110--14220--251--20.1331--30.3441--40.22--30.83--40.9

Graphe 4 Non Orienté
\(M_3=\begin{pmatrix} 3 & 2 & 0 & 0\\ 0 & 4 & 0.5 & 0.2\\ 0 & 0 & 0.6 & 0\\ 0 & 0 & 5 & 0\\ \end{pmatrix} \)
Matrice d'adjacence Graphe 3
Matrice NON Symétrique
\(M_4=\begin{pmatrix} 0 & 4 & 5 & 0 & 0\\ 4 & 0 & 0.1 & 0.3 & 0.2\\ 5 & 0.1 & 0 & 0.8 & 0\\ 0 & 0.3 & 0.8 & 0 & 0.9\\ 0 & 0.2 & 0 & 0.9 & 0\\ \end{pmatrix} \)
Matrice d'adjacence Graphe 4
Matrice Symétrique
# Matrice Adjacence en Liste de Listes :
M3 = [[3, 2, 0, 0],
      [0, 4, 0.5, 0.2],
      [0, 0, 0.6, 0],
      [0, 0, 5, 0]]

# Matrice Adjacence en Liste de Listes :
M4 = [[0, 4, 5, 0, 0],
      [4, 0, 0.1, 0.3, 0.2],
      [5, 0.1, 0, 0.8, 0],
      [0, 0.3, 0.8, 0, 0.9],
      [0, 0.2, 0, 0.9, 0]]

# Matrice Adjacence en Dictionnaire (graphes Étiquetés) :
M3 = {0 : [3, 2, 0, 0],
      1 : [0, 4, 0.5, 0.2],
      2 : [0, 0, 0.6, 0],
      3 : [0, 0, 5, 0]}

# Matrice Adjacence en Dictionnaire (graphes Étiquetés) :
M4 = {0 : [0, 4, 5, 0, 0],
      1 : [4, 0, 0.1, 0.3, 0.2],
      2 : [5, 0.1, 0, 0.8, 0],
      3 : [0, 0.3, 0.8, 0, 0.9],
      4 : [0, 0.2, 0, 0.9, 0]}

Symétrie de la matrice d'Adjacence⚓︎

Matrice Symétrique

Notons \(A=(a_{ij})\) la matrice d'adjacence.
On dit que la matrice d'adjacence est symétrique \(\Leftrightarrow\) \(a_{ij}=a_{ji}\) pour tous les \(i,j\)
Cela revient à ce que les coefficients \(a_{ij}\) soient symétriques par rapport à la diagonale principale

Matrice d'Adjacence Symétrique? ou pas?

  • Un graphe non orienté admet une matrice d'adjacence symétrique
  • Un graphe orienté admet, en général, une matrice d'adjacence non symétrique

Liste d'Adjacence⚓︎

  • Pour représenter un graphe, on peut également, pour chacun de ses sommets, donner la liste des sommets auxquels il est relié.
  • Lorsque le graphe est non orienté, la liste d'adjacence est une liste de voisins

  • Lorsque le graphe est orienté, la liste d'adjacence peut être représentée par :

    • la liste de ses successeurs, ou bien
    • la liste de ses prédécesseurs, lorsque les problèmes étudiés s'y prêtent mieux (ça arrive)

  • Implémentation:

    • Pour un graphe d'ordre \(n\), on numérotera les sommets de \(0\) à \(n-1\)
    • Graphes non étiquetés : Les listes de voisins et/ou de successeurs se représentent usuellement par des listes de listes en Python.
    • Graphes étiquetés : Les listes de voisins et/ou de successeurs se représentent usuellement par des dictionnaires en Python.

Exp

G000->0110->11->1221->2331->32:e->2:s3->2

Graphe 1 Orienté

G00110--1220--21--2331--3441--42--33--4

Graphe 2 Non Orienté
# Liste de Successeurs en Liste de Listes :
S1 = [[0,1],
      [1, 2, 3],
      [2],
      [2]]

# Liste de Voisins en Liste de Listes :
V2 = [[1, 2],
      [0, 2, 3, 4],
      [0, 1, 3],
      [1, 2, 4],
      [1, 3]]

# Liste de Successeurs en Dictionnaire (Graphes Étiquetés) :
S1 = {0 : [0, 1],
      1 : [1, 2, 3],
      2 : [2],
      3 : [2]}

# Liste de Voisins en Dictionnaire (Graphes Étiquetés) :
V2 = {0 : [1, 2],
      1 : [0, 2, 3, 4],
      2 : [0, 1, 3],
      3 : [1, 2, 4],
      4 : [1, 3]}

G000->03110->121->14221->20.5331->30.22:e->2:s0.63->25

Graphe 3 Orienté Pondéré

G00110--14220--251--20.1331--30.3441--40.22--30.83--40.9

Graphe 4 Non Orienté Pondéré
# Liste de Successeurs Pondéré en Liste de Listes :
S3 = [[[0,3],[1,2]],
      [[1,4], [2,0.5], [3,0.2]],
      [2,0.6],
      [2,5]]

# Liste de Voisins Pondéré en Liste de Listes :
V4 = [[[1,4], [2,5]],
      [[0,4], [2,0.1], [3,0.3], [4,0.2]],
      [[0,5], [1,0.1], [3,0.8]],
      [[1,0.3], [2,0.8], [4,0.9]],
      [[1,0.2], [3,0.9]]]

# Liste de Successeurs Pondéré en Dictionnaire (Graphes Étiquetés) :
S3 = {0 : [[0,3],[1,2]],
      1 : [[1,4], [2,0.5], [3,0.2]],
      2 : [2,0.6],
      3 : [2,5]}

# Liste de Voisins Pondéré en Dictionnaire (G.Étiquetés):
V4 = {0 : [[1,4], [2,5]],
      1 : [[0,4], [2,0.1], [3,0.3], [4,0.2]],
      2 : [[0,5], [1,0.1], [3,0.8]],
      3 : [[1,0.3], [2,0.8], [4,0.9]],
      4 : [[1,0.2], [3,0.9]]}