Théorie des graphes/Fondements

Leçons de niveau 16
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
Fondements
Icône de la faculté
Chapitre no 1
Leçon : Théorie des graphes
Retour auSommaire
Chap. suiv. :Propriétés
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des graphes : Fondements
Théorie des graphes/Fondements
 », n'a pu être restituée correctement ci-dessus.

Pour étudier les graphes et leurs utilisations, nous allons nous doter de définitions formelles, lister les représentations mémoire possibles et nous doter d’un modèle de graphe comme structure de données abstraite.

Graphes non orientés[modifier | modifier le wikicode]



Début de l'exemple
Fin de l'exemple


Graphes orientés[modifier | modifier le wikicode]



Début de l'exemple
Fin de l'exemple


Structure de données concrète[modifier | modifier le wikicode]

Selon les définitions précédentes, un graphe peut se représenter comme un couple d'ensembles : on pourrait simplement stocker deux ensembles. Cependant, cela entraîne un problème d'efficacité :

  • L'accès aux arêtes (ou arcs) incidents à un sommet (ou nœud) demande une recherche
  • L'accès aux sommets (ou nœuds) adjacents à un sommet (ou nœud) demande une recherche

Dans un graphe, ce sont les relations d'incidence et d'adjacence qui sont importantes : on va utiliser des structures de données concrètes qui les intègrent.

Matrice d'adjacence[modifier | modifier le wikicode]

Un graphe G=(S,A) à |S|=n sommets est représenté par une matrice M de booléens de taille n*n où :

  • Les indices des lignes et des colonnes représentent des sommets
  • M[i, j] = vrai si et seulement si l'arête (i, j) ∈ A

Notes :

  • Occupation mémoire : O(n²)
  • Pour les graphes orientés, on oriente la matrice
  • Ne permet pas de représenter tous les graphes : les arêtes multiples ne peuvent être représentées


Graphe non orienté Graphe orienté
Début de l'exemple
Fin de l'exemple
Début de l'exemple
Fin de l'exemple


Note pour l'exemple sur les graphes orientés :

  • ligne = nœuds de départ
  • colonne = nœuds d'arrivée

Listes d'adjacence[modifier | modifier le wikicode]

Un graphe G=(S, A) où |S|=n et |A|=m est représenté par une table T (ou une liste dont l'élément a deux champs suivant) de taille n où :

  • chaque case représente un sommet et pointe sur un autre sommet (premier champ suivant)
  • chaque case T[i] pointe sur la liste des sommets adjacents à i (deuxième champ suivant)
  • la liste T[i] (deuxième champ suivant) est vide si i est isolé

Note :

  • Occupation mémoire : O(n+m)
  • Pour les graphes orientés, on ne liste que les arcs sortants (voir exemple ci-dessous)
  • Permet de représenter tous les graphes


Graphe non orienté Graphe orienté
Début de l'exemple
Fin de l'exemple
Début de l'exemple
Fin de l'exemple

Matrice d'incidence[modifier | modifier le wikicode]

Un graphe G=(S, A) où |S|=n et |A|=m est représenté par une matrice M de booléens de taille n*m où :

  • les indices des lignes représentent des sommets
  • les indices des colonnes représentent des arêtes
  • M[i, j] = vrai si et seulement si l'arête j lie le sommet i

Notes :

  • Occupation mémoire : O(n*m)
  • Pour les graphes orientés, on utilise trois valeurs au lieu de booléens (départ, arrivée, et boucle)


Graphe non orienté Graphe orienté
Début de l'exemple
Fin de l'exemple
Début de l'exemple
Fin de l'exemple

Listes d'incidence[modifier | modifier le wikicode]

Un graphe G=(S, A) où |S|=n et |A|=m est représenté par une table T (ou une liste) de taille n où :

  • chaque case T[i] pointe sur la liste des arêtes incidentes à i
  • la liste T[i] est vide si i est isolé

Notes :

  • Occupation mémoire : O(n+m)
  • Pour les graphes orientés, on ne liste que les arcs sortants


Graphe non orienté Graphe orienté
Début de l'exemple
Fin de l'exemple
Début de l'exemple
Fin de l'exemple

Opérations supportées[modifier | modifier le wikicode]

Type d'opération Matrice d'adjacence Liste d'adjacence Matrice d'incidence Liste d'incidence
Créer un graphe vide O(1)* O(1) O(1)* O(1)
Supprimer O(1) O(n+m) O(1) O(n+m)
Ajouter un sommet / nœud O(1)* O(1) O(1)* O(1)
Supprimer un sommet / nœud O(1)* O(m) O(1)* O(m)
Ajouter une arête / un arc O(1)* O(1) O(1)* O(1)
Supprimer une arête / un arc O(1)* O(1) O(1)* O(1)
Lister les voisins / successeurs d'un sommet / nœud O(n) O(1) O(m) O(m)
Lister les prédécesseurs d'un nœud O(n) O(m) O(n*m) O(n)
Lister les arêtes / arcs issus d'un sommet / nœud O(n) O(n) O(m) O(m)
Lister les arcs entrant en un nœud O(n) O(m) O(n*m) O(n)
Nombre de sommets / nœuds / arêtes / arcs O(1) O(1) O(1) O(1)

* si les tableaux sont statiques, ils sont supposés préalloués à une taille suffisante. Si les tableaux sont dynamiques, il faut ajouter le coût de la réallocation.