Représentations (Bac 🎯)⚓︎

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
le cours de Gilles Lassus
le cours de Cédric Gouygou en particulier pour cette partie.

🔖 Synthèse de ce qu'il faut retenir pour le bac

Différentes représentations d'un graphe⚓︎

Pour implémenter l'interface de la classe Graphe présentée précédemment, il nous faut une représentation interne d'un graphe. On présente les représentations les plus classiques.

Représentation par matrice d'adjacence⚓︎

Point de cours 4 : représentation par matrice d'adjacence

On étiquette les sommets de 0 à \(n-1\).
On représente chaque arc dans une matrice d'adjacence, c'est-à-dire un tableau à deux dimensions où on inscrit un 1 en ligne i et colonne j si l'arc i -> j est dans le graphe.

Matrice d'adjacence en Python

En Python, on peut représenter une matrice d'adjacences d'un graphe à \(n\) sommets par une liste de \(n\) listes de taille \(n\). Si cette matrice est référencée par une variable mat et si 0 <= i < n et 0 <= j < n alors :

mat[i][j] vaut 1 si l'arc i -> j est dans le graphe
mat[i][j] vaut 0 si l'arc i -> j n'est pas dans le graphe

💡 Pour un graphe non orienté, on ne distingue pas les arcs i -> j et j -> i donc s'il y a un 1 en ligne i et colonne j alors il y a un 1 en ligne j et colonne i. On dit que la matrice d'adjacence est symétrique.

💡 Pour un graphe pondéré on peut remplacer le 1 marquant la présence d'un arc par le poids de l'arc.

Exemple avec un graphe non orienté

Source : exemple de Cédric Gouygou

alt

Le graphe non orienté ci-dessus peut être représenté par la matrice d'adjacence ci-dessous. La matrice est symétrique.

matrice d'adjacencearc entre deux sommetsreprésentation en Python

alt

🐍 Script Python

[[0, 1, 1, 0, 0],
 [1, 0, 1, 1, 0],
 [1, 1, 0, 1, 1],
 [0, 1, 1, 0, 1],
 [0, 0, 1, 1, 0]            
]

Exemple avec un graphe orienté

alt

Le graphe orienté ci-dessus peut être représenté par la matrice d'adjacence ci-dessous représentée en Python. La matrice n'est pas symétrique.

🐍 Script Python

[[0, 0, 0, 0, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 1],
 [0, 0, 0, 0, 1],
 [1, 0, 0, 0, 0]]

Exemple avec un graphe pondéré

Un exemple de graphe pondéré représenté par une matrice d'adjacence.

alt

Représentation en Python :

🐍 Script Python

[[0, 7, 12, 0, 0],
 [7, 0, 4, 8, 0],
 [12, 4, 0, 13, 5],
 [0, 8, 13, 0, 6],
 [0, 0, 5, 6, 0]]

Exercice 4

Source : exercice de Gilles Lassus

Soit un ensemble d'amis connectés sur un réseau social quelconque. Voici les interactions qu'on a recensées :

André est ami avec Béa, Charles, Estelle et Fabrice,
Béa est amie avec André, Charles, Denise et Héloïse,
Charles est ami avec André, Béa, Denise, Estelle, Fabrice et Gilbert,
Denise est amie avec Béa, Charles et Estelle,
Estelle est amie avec André, Charles et Denise,
Fabrice est ami avec André, Charles et Gilbert,
Gilbert est ami avec Charles et Fabrice,
Héloïse est amie avec Béa.

Question 1

énoncésolution

Représenter le graphe des relations dans ce réseau social (on désignera chaque individu par l'entier représentant le rang dans l'alphabet de l'initiale de son prénom, en commençant à 0). Il est possible de faire en sorte que les arêtes ne se croisent pas !

Un graphe qu'on peut représenter sans croiser les arcs est un graphe planaire.

alt

Question 2

énoncésolution

Donner la matrice d'adjacence de ce graphe non orienté

\(\pmatrix{0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\}\)

Exercice 5

Source : exercice de Gilles Lassus

Construire les graphes correspondants aux matrices d'adjacence suivantes:

Question 1

énoncésolution

Matrice d'adjacence d'un graphe non orienté :

\(M_1 =\pmatrix{ 0&1&1&1&1\\ 1&0&1&0&0\\ 1&1&0&1&0\\ 1&0&1&0&1\\ 1&0&0&1&0\\ }\)

Question 2

énoncésolution

Matrice d'adjacence d'un graphe orienté :

\(M_2=\pmatrix{ 0&1&1&0&1\\ 0&0&1&0&0\\ 0&0&0&1&0\\ 1&0&0&0&1\\ 0&0&0&0&0\\ }\)

Question 3

énoncésolution

Matrice d'adjacence d'un graphe pondéré non orienté :

\(M_3=\pmatrix{ 0&5&10&50&12\\ 5&0&10&0&0\\ 10&10&0&8&0\\ 50&0&8&0&100\\ 12&0&0&100&0\\ }\)

Exercice 6

On considère un graphe orienté de \(n\) sommets et on suppose que tous les sommets sont étiquetés par des entiers de \(0\) à \(n-1\).

On représente le graphe par sa matrice d'adjacence qu'on implémente en Python par une liste de listes référencée par une variable mat.

On rappelle que si la matrice d'adjacence est référencée par une variable mat, si 0 <= i < n et 0 <= j < n, alors la valeur de mat[i][j] est 1 si l'arc i -> j appartient au graphe et 0 sinon.

Question 1

énoncésolution

Par rapport au nombre \(n\) de sommets, la complexité spatiale (coût de l'espace occupé en mémoire) du stockage de la matrice d'adjacence est-elle constante (en \(O(1)\)) ? linéaire (en \(O(n)\)) ? quadratique (en \(O(n^{2})\)) ?

La matrice d'adjacence est une liste de listes Python de dimensions \(n \times n\), donc il faut stocker \(n^{2}\) valeurs de même type. En Python, ces valeurs seront des entiers, même s'il suffirait de stocker 1 bit (valeur 0 ou 1). L'espace mémoire utilisé est donc égal à \(n^{2}\) fois une constante, il s'agit d'une complexité spatiale quadratique.

Question 2

énoncésolution

Quel code Python permet de tester si l'arc i -> j existe ?

Par rapport au nombre \(n\) de sommets du graphe, la complexité de cette opération est-elle constante (en \(O(1)\)) ? linéaire (en \(O(n)\)) ? quadratique (en \(O(n^{2})\)) ?

Tester si l'arc i -> j existe équivaut à tester si m[i][j] est égal à 1.

L'accès à un élément dans une liste de listes étant constant (tableau à deux dimesions), la complexité temporelle de cette opération correspond à un coût constant en \(O(1)\).

🐍 Script Python

m[i][j] == 1

Question 3

énoncésolution

Quel code Python permet de récupérer la liste des voisins du sommet i ?

Par rapport au nombre \(n\) de sommets du graphe, la complexité de cette opération est-elle constante (en \(O(1)\)) ? linéaire (en \(O(n)\)) ? quadratique (en \(O(n^{2})\)) ?

🐍 Script Python

voisins = []
for j in range(len(mat[i])):
    if mat[i][j] == 1:
        voisins.append(j)

Il faut parcourir toute la ligne d'index i de la matrice d'adjacence pour récupérer tous les voisins du sommet i, la complexité temporelle de cette opération est donc linéaire, de l'ordre du nombre de sommets \(n\) du graphe.

Une version plus élégante avec une liste en compréhension :

🐍 Script Python

voisins = [j for j in range(len(mat[i])) if mat[i][j] == 1]

Représentation par tableau de listes d'adjacence⚓︎

Point de cours 5 : représentation par tableau de listes d'adjacence

On étiquette les sommets de 0 à \(n-1\).
On crée un tableau de taille \(n\) dont l'élément d'indice i contient la liste des sommets j adjacents au sommet i , c'est-à-dire tels que l'arc i -> j existe. Cette liste d'adjacence du sommet i contient donc :
- tous les voisins de i dans un graphe non orienté
- tous les successeurs de i dans un graphe orienté

Listes d'adjacence en Python

En Python, on peut représenter un tableau de listes d'adjacences par une liste de \(n\) listes de tailles variables (contrairement à une matrice d'adjacence où toutes les listes sont de taille \(n\)). Si cette liste est référencée par une variable adj et si 0 <= i < n et 0 <= j < n alors :

len(adj) vaut \(n\) car le graphe a \(n\) sommets
adj[i] contient la liste de tous les sommets j tels que l'arc i -> j existe
len(adj[i]) est donc le nombre de voisins (graphe non orienté) ou successeurs (graphe orienté) du sommet i

Exemple avec un graphe non orienté

Source : exemple de Cédric Gouygou

alt

Le graphe non orienté ci-dessus peut être représenté en Python par listes d'adjacences comme ci-dessous.

🐍 Script Python

adj = [[1, 2],
       [0, 2, 3],
       [0, 1, 3, 4],
       [1, 2, 4],
       [2, 3]       
      ]

La valeur de adj[0] est la liste [1, 2] car les voisins du sommet 0 sont les sommets 1 et 2.

Il faut noter que par symétrie, comme le graphe est non orienté, 0 appartient aux listes d'adjacence adj[1] et à adj[2].

Exemple avec un graphe orienté

alt

Le graphe orienté ci-dessus peut être représenté en Python par listes d'adjacences comme ci-dessous.

🐍 Script Python

adj = [[],
       [2, 4],
       [3, 4],
       [4],
       [0]
      ]

Il faut noter que la liste d'adjacence adj[0] est vide car le sommet 0 n'a pas de successeurs.

Exemple avec un graphe pondéré

Pour un graphe pondéré, il n'est pas possible de conserver la même structure en stockant le poids à la place de la valeur 1 ou 0 comme dans une matrice d'adjacence. Il faut enrichir la structure en stockant par exemple dans la liste d'adjacence non pas l'étiquette du sommet extrémité de l'arc mais un couple avec ce sommet et le poids de l'arc.

alt

Par exemple, une représentation en Python par listes d'adjacence du graphe pondéré ci-dessus pourrait être :

🐍 Script Python

adj = [[(1, 7), (2, 12)],
       [(0,7), (2,4), (3,8)],
       [(0,12), (1,4), (3, 13), (4, 5)],
       [(1, 8), (2, 13), (4, 6)],
       [(2, 5), (3, 6)]
       ]

Exercice 7

Question 1

énoncésolution

Donner une représentation en Python par listes d'adjacence du graphe non orienté ci-dessous.

🐍 Script Python

adj = [[1,2,5,6], [0], [0], [4, 5], [3, 5, 6], 
       [0, 3, 4], [0, 4], [8], [7],
       [10, 11, 12], [9], [9, 12], [9, 11]]

Question 2

énoncésolution

Représenter le graphe non orienté dont les sommets sont étiquetés de 0 à 8 et dont on donne une représentation par listes d'adjacence en Python ci-dessous :

🐍 Script Python

adj = [[1, 2, 6], [0, 3 , 5, 6], [0, 3],  
       [1, 2, 4], [3, 5, 8],
       [1, 4, 7], [0, 1], [5, 8], [4, 7]]

Question 3

énoncésolution

Donner la représentation sous forme de tableau de listes d'adjacence du graphe orienté dont les sommets sont étiquetés par les entiers successifs à partir de 0 et dont on donne la matrice d'adjacence ci-dessous :

\(M_2=\pmatrix{ 0&1&1&0&1\\ 0&0&1&0&0\\ 0&0&0&1&0\\ 1&0&0&0&1\\ 0&0&0&0&0\\ }\)

On donne une représentation en Python :

🐍 Script Python

adj = [[1, 2, 4], [2], [3], [0, 4], []]

Exercice 8

On considère un graphe orienté de \(n\) sommets et on suppose que tous les sommets sont étiquetés par des entiers de \(0\) à \(n-1\).

On note \(n\) le nombre de sommets et \(m\) le nombre d'arcs.

On représente le graphe par listes d'adjacence qu'on implémente en Python par une liste de listes référencée par une variable \(adj\).

Question 1

énoncésolution

La complexité spatiale (coût de l'espace occupé en mémoire) du stockage des listes d'adjacence dans un tableau est-il en \(O(1)\) ? en \(O(n)\) ? en \(O(n^{2})\) ? en \(O(n \times m)\) ? en \(O(n + m)\) ?

On a besoin d'un tableau de taille \(n\) dans lequel on stocke les listes d'adjacence. Le nombre total d'éléments stockés dans les listes d'adjacence est égal au nombre d'arcs donc c'est \(m\). Ainsi la complexité spatiale du stockage dans des listes d'adjacence est en \(O(n + m)\).

Question 2

énoncésolution

Quel code Python permet de tester si l'arc i -> j existe ?

Par rapport au nombre \(n\) de sommets du graphe, la complexité de cette opération, dans le pire des cas, est-elle constante (en \(O(1)\)) ? linéaire (en \(O(n)\)) ? quadratique (en \(O(n^{2})\)) ?

Tester si l'arc i -> j existe équivaut à rechercher dans la liste d'adjacence adj[i] la présence du sommet j.

Le code Python est donc :

🐍 Script Python

k = 0
while k < len(adj[i]) and adj[i][k] != j:
    k = k + 1
presence = (k < len(adj[i]))

Dans le pire des cas, si j n'est pas dans adj[i], on doit parcourir toute la liste d'adjacence et effectuer len(adj[i]) comparaisons. len(adj[i]) est le nombre de voisins/successeurs du sommet i qui est majoré par \(n\) le nombre de sommets. Donc, dans le pire des cas, cette recherche est de complexité linéaire par rapport au nombre de sommets, en \(O(n)\).

Une autre version, plus simple à écrire, mais il faut être conscient de la boucle cachée :

🐍 Script Python

j in adj[i]

Question 3

énoncésolution

Quel code Python permet de récupérer la liste des voisins du sommet i ?

Par rapport au nombre \(n\) de sommets du graphe, la complexité de cette opération est-elle constante (en \(O(1)\)) ? linéaire (en \(O(n)\)) ? quadratique (en \(O(n^{2})\)) ?

On obtient directement cette liste de voisins/successeurs avec adj[i]. C'est le principe du stockage par liste d'adjacences ! La complexité correspond donc à un coût constant, en \(O(1)\).

Représentation par dictionnaire de listes d'adjacence⚓︎

Point de cours 6 : représentation par dictionnaire de listes d'adjacence

On considère un graphe de \(n\) sommets étiquetés par des noms (type 'str'). On peut reprendre le modèle de représentation par un tableau de listes d'adjacences en remplaçant le tableau par un dictionnaire dont les clefs sont les étiquettes des sommets.

Voici un exemple de graphe avec sommets étiquetés, représenté par un dictionnaire de listes d'adjacences en Python.

🐍 Script Python

adj_tgv = {"Lyon": ["Paris", "Marseille"],
          "Lille": ["Paris"],
          "Marseille": ["Lyon"],
          "Paris": ["Lille", "Lyon", "Strasbourg"],
          "Strasbourg": ["Paris"]}

Exercice 9

Source : exercice de Gilles Lassus

Question 1

énoncésolution

Représenter le graphe non orienté correspondant à la représentation par dictionnaire de listes d'adjacences ci-dessous.

🐍 Script Python

adj1 = {
'A': ['B', 'C'],
'B': ['A', 'C', 'E', 'F'],
'C': ['A', 'B', 'D'],
'D': ['C', 'E'],
'E': ['B', 'D', 'F'],
'F': ['B', 'E']
    }

Question 2

énoncésolution

Représenter le graphe orienté correspondant à la représentation par dictionnaire de listes d'adjacences ci-dessous.

🐍 Script Python

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

Comparaison des représentations⚓︎

Comparaison des représentations

Complexité spatiale⚓︎

Soit un graphe avec un ensemble V de sommets et un ensemble E d'arcs.

Notons \(n\) =|V| le nombre de sommets et \(m\)= |E| le nombre d'arcs.

Représentation	Complexité spatiale
Matrice d'adjacence	quadratique par rapport au nombre de sommets \(O(n^{2})\)
Listes d'adjacence	\(O(n+m)\)

On rappelle l'inégalité \(n - 1 \leqslant m < n^{2}\).

À l'exception des graphes denses dont le nombre d'arcs est de complexité quadratique par rapport au nombre de sommets, la complexité spatiale d'un tableau de listes d'adjacences est bien meilleure que celle d'une matrice d'adjacence.

Complexité temporelle⚓︎

Les deux opérations de base sur une représentation de graphe sont :

le test d'adjacence : l'arc i->j existe-t-il ?
la liste des voisins (graphe non orienté) ou successeurs (graphe orienté)

Ces opérations ont une complexité par rapport au nombre de sommets \(n\), différente selon les représentations. On donne juste la complexité dans le pire des cas.

Représentation	Tester si l'arc `i->j` existe	Complexité
Matrice d'adjacence	`mat[i][j] == 1`	constante \(O(1)\)
Listes d'adjacence	`j in adj[i]`	linéaire \(O(n)\)

Représentation	Lister les voisins/successeurs	Complexité
Matrice d'adjacence	`[j for j in range(n) if mat[i][j] == 1]`	linéaire \(O(n)\)
Listes d'adjacence	`adj[i]`	constante \(O(1)\)

En pratique, les algorithmes de parcours de graphe au programme utilisent surtout l'opération de liste des voisins/successeurs, donc les listes d'adjacences seront la représentation privilégiée.

💡 Les performances d'un dictionnaire de listes d'adjacences sont comparables à celles d'un tableau de listes d'adjacences. Il serait possible d'améliorer le test d'existence d'un arc, de linéaire à constant, si on utilisait une table de hachage à la place d'une liste d'adjacences, par exemple un ensemble de type set en Python.

Exercice 10

Source : "Algorithmes Illuminated Part 2" de Tim Roughgarden.

Il n'existe pas de carte exhaustive du World Wide Web mais si on le modélise par un graphe orienté dont les sommets sont les pages Web et les arcs les liens hypertextes, on peut estimer qu'il y a environ \(10^{10}\) sommets et \(100\) arcs sortants par sommet.

Question 1

énoncésolution

Comparer les complexités spatiales du stockage d'une représentation du graphe du Web dans une matrice d'adjacence et dans un tableau de listes d'adjacences.

Les paramètres de taille du graphe sont ici \(n=10^{10}\) sommets et \(m=n \times 100 = 10^{12}\) arcs.

Un stockage dans une matrice d'adjacence aurait une complexité spatiale quadratique en \(O(n^{2})\) donc de l'ordre de \((10^{10})^{2} = 10^{20}\) ce qui est inatteignable même pour les ordinateurs massivement parallèles des centres de données.

Un stockage dans un tableau de listes d'adjacence aurait une complexité spatiale en \(O(n+m)=O(m)\) car ici \(n << m\), de l'ordre de \(10^{12}\) ce qui est à la portée des ordinateurs massivement parallèles des centres de données.

Implémentation de l'interface de la classe `Graphe`⚓︎

Exercice 11

💻 Saisir ses réponses sur Capytale

Question 1

énoncésolution

Compléter l'interface de la classe Graphe ci-dessous pour représenter un graphe non orienté, en utilisant comme représentation interne du graphe un dictionnaire de liste d'adjacences qui est référencé par l'attribut self.adjacents.

🐍 Script Python

class Graphe:

    def __init__(self, liste_sommets):
        """
        Crée une représentation de  graphe non orienté à partir d'une liste de sommets
        """
        self.liste_sommets = liste_sommets
        self.adjacents = {sommet : [] for sommet in liste_sommets}
        
    def sommets(self):
        """
        Renvoie une liste des sommets
        """
        return self.liste_sommets
    
    def ajoute_arc(self, sommetA, sommetB):
        """
        Ajoute dans la représentation de graphe l'arc sommetA - sommetB
        """
        assert (sommetA in self.liste_sommets), "sommet A pas dans le graphe"
        assert (sommetB in self.liste_sommets), "sommet B pas dans le graphe"
        self.adjacents[sommetA].append(sommetB)
        self.adjacents[sommetB].append(sommetA)

    def voisins(self, sommet):
        """
        Renvoie une liste des voisins du sommet dans la représentation du graphe
        """
        assert sommet in self.liste_sommets, "sommet pas dans le graphe"
        return self.adjacents[sommet]

    def est_arc(self, sommetA, sommetB):
        """
        Renvoie un booléen indiquant si l'arc sommetA - sommetB appartient au graphe
        """
        assert sommetA in self.liste_sommets, "sommetA pas dans le graphe"
        return sommetB in self.adjacents[sommetA]
    

def test_graphe():
    """
    Tests unitaires pour la classe Graphe
    """
    g1 = Graphe([0, 1, 2, 3, 4])
    g1.ajoute_arc(1, 2)
    g1.ajoute_arc(1, 4)
    g1.ajoute_arc(2, 3)
    g1.ajoute_arc(2, 4)
    g1.ajoute_arc(3, 4)
    g1.ajoute_arc(4, 0)
    assert g1.est_arc(1, 2) == True, "échec sur g1.est_voisin(1, 2)"
    assert g1.est_arc(2, 1) == True, "échec sur g1.est_voisin(2, 1)"
    assert g1.sommets() == [0, 1, 2, 3, 4], "échec sur g1.sommets()"
    assert g1.voisins(2) == [1, 3, 4], "échec sur g1.voisins(2)"
    assert g1.voisins(1) == [2, 4], "échec sur g1.voisins(1)"
    print("Tests réussis")

Question 2

énoncésolution

Compléter l'interface de la classe Graphe_oriente ci-dessous pour représenter un graphe orienté, en utilisant comme représentation interne du graphe un dictionnaire de liste d'adjacences qui est référencé par l'attribut self.adjacents.

Par rapport à la classe Graphe pour graphe non orienté, l'interface a été étendue avec deux autres méthodes à compléter : degre_entrant et degre_sortant.

🐍 Script Python

class Graphe_oriente:

    def __init__(self, liste_sommets):
        """
        Crée une représentation de  graphe  orienté à partir d'une liste de sommets.
        Représentation par dictionnaire d'adjacences
        """
        self.liste_sommets = liste_sommets
        self.adjacents = {sommet : [] for sommet in liste_sommets}
        
    def sommets(self):
        """
        Renvoie une liste des sommets
        """
        return self.liste_sommets

    def ajoute_arc(self, sommetA, sommetB):
        """
        Ajoute dans la représentation de graphe l'arc sommetA -> sommetB
        """
        assert (sommetA in self.liste_sommets), "sommet A pas dans le graphe"
        assert (sommetB in self.liste_sommets), "sommet B pas dans le graphe"
        self.adjacents[sommetA].append(sommetB)


    def voisins(self, sommet):
        """
        Renvoie une liste des voisins du sommet dans la représentation du graphe
        """
        assert sommet in self.liste_sommets, "sommet pas dans le graphe"
        return self.adjacents[sommet]

    def est_arc(self, sommetA, sommetB):
        """
        Renvoie un booléen indiquant si l'arc sommetA -> sommetB appartient au graphe
        """
        assert sommetA in self.liste_sommets, "sommetA pas dans le graphe"
        return sommetB in self.adjacents[sommetA]
    
    def degre_entrant(self, sommet):
        """
        Renvoie le degré entrant d'un sommet du graphe orienté
        """
        d = 0
        for s in self.sommets():
            if sommet in self.voisins(s):
                d = d + 1
        return d
    
    def degre_sortant(self, sommet):
        """
        Renvoie le degré sortant d'un sommet du graphe orienté
        """
        d = 0
        for s in self.voisins(sommet):
            d = d + 1
        return d
    
    

def test_graphe_oriente():
    """
    Tests unitaires pour la classe Graphe_oriente
    """
    g1 = Graphe_oriente([0, 1, 2, 3, 4])
    g1.ajoute_arc(1, 2)
    g1.ajoute_arc(1, 4)
    g1.ajoute_arc(2, 3)
    g1.ajoute_arc(2, 4)
    g1.ajoute_arc(3, 4)
    g1.ajoute_arc(4, 0)
    assert g1.est_arc(1, 2) == True, "échec sur g1.est_arc(1, 2)"
    assert g1.est_arc(2, 1) == False, "échec sur g1.est_arc(2, 1)"
    assert g1.sommets() == [0, 1, 2, 3, 4], "échec sur g1.sommets()"
    assert g1.voisins(2) == [3, 4], "échec sur g1.voisins(2)"
    assert g1.voisins(1) == [2, 4], "échec sur g1.voisins(1)"
    assert g1.degre_sortant(2) == 2, "échec sur self.degre_sortant(2)"
    assert g1.degre_entrant(2) == 1, "échec sur self.degre_entrant(2)"
    print("Tests réussis")

Exercice 12

💻 Saisir ses réponses sur Capytale

Question 1

énoncésolution

Compléter l'interface de la classe Graphe_matrice ci-dessous pour représenter un graphe non orienté, en utilisant comme représentation interne du graphe une matrice d'adjacences qui est référencée par l'attribut self.matrice. On suppose que les sommets du graphe sont des entiers numérotés de 0 à \(n-1\).

Par rapport à l'exercice précédent, l'interface a été étendue avec une autre méthode à compléter : export_listes qui renvoie une représentation du graphe cette fois sous forme de listes d'adjacences.

🐍 Script Python

class Graphe_matrice:
    
    def __init__(self, liste_sommets):
        """
        Crée une représentation de  graphe non orienté à partir d'une liste de sommets  numérotés de 0 à n - 1. Représentation par matrice d'adjacences
        """
        self.liste_sommets = liste_sommets
        self.n = len(self.liste_sommets)
        self.matrice = [[0 for j in range(self.n)] for i in range(self.n)]
        
    def sommets(self):
        """
        Renvoie une liste des sommets
        """
        return self.liste_sommets
    
    def ajoute_arc(self, sommetA, sommetB):
        """
        Ajoute dans la représentation de graphe l'arc sommetA - sommetB
        """
        assert (sommetA in self.liste_sommets), "sommet A pas dans le graphe"
        assert (sommetB in self.liste_sommets), "sommet B pas dans le graphe"
        self.matrice[sommetA][sommetB] = 1
        self.matrice[sommetB][sommetA] = 1
    
    def voisins(self, sommet):
        """
        Renvoie une liste des voisins du sommet dans la représentation du graphe
        """
        assert sommet in self.liste_sommets, "sommet pas dans le graphe"
        return [j for j in range(self.n) if self.matrice[sommet][j] == 1]

    def est_arc(self, sommetA, sommetB):
        """
        Renvoie un booléen indiquant si l'arc sommetA - sommetB appartient au graphe
        """
        assert sommetA in self.liste_sommets, "sommetA pas dans le graphe"
        return self.matrice[sommetA][sommetB] == 1
    
    def export_listes(self):
        """
        Renvoie une représentation du graphe sous forme de tableau de listes d'adjacences
        """
        tab = []
        for s in self.sommets():
            tab.append(self.voisins(s))
        return tab
    

def test_graphe_matrice():
    """
    Tests unitaires pour la classe Graphe_matrice
    """
    g1 = Graphe_matrice([0, 1, 2, 3, 4])
    g1.ajoute_arc(1, 2)
    g1.ajoute_arc(1, 4)
    g1.ajoute_arc(2, 3)
    g1.ajoute_arc(2, 4)
    g1.ajoute_arc(3, 4)
    g1.ajoute_arc(4, 0)
    assert g1.est_arc(1, 2) == True, "échec sur g1.est_voisin(1, 2)"
    assert g1.est_arc(2, 1) == True, "échec sur g1.est_voisin(2, 1)"
    assert g1.sommets() == [0, 1, 2, 3, 4], "échec sur g1.sommets()"
    assert g1.voisins(2) == [1, 3, 4], "échec sur g1.voisins(2)"
    assert g1.voisins(1) == [2, 4], "échec sur g1.voisins(1)"
    assert g1.export_listes() == [[4], [2, 4], [1, 3, 4], [2, 4], [0, 1, 2, 3]], "échec sur g1.export_listes()"
    print("Tests réussis")
    
test_graphe_matrice()

Question 2

énoncésolution

Compléter l'interface de la classe Graphe_listes_ ci-dessous pour représenter un graphe non orienté, en utilisant comme représentation interne du graphe un tableau de listes d'adjacences qui est référencé par l'attribut self.adjacents. On suppose que les sommets du graphe sont des entiers numérotés de 0 à \(n-1\).

Par rapport à l'exercice précédent, l'interface a été étendue avec une autre méthode à compléter : export_matrice qui renvoie une représentation du graphe cette fois sous forme de matrice d'adjacence.

🐍 Script Python

class Graphe_liste:
    
    def __init__(self, liste_sommets):
        """
        Crée une représentation de  graphe non orienté à partir d'une liste de sommets
        numérotés de 0 à n - 1
        """
        self.liste_sommets = liste_sommets
        self.n = len(self.liste_sommets)
        self.adjacents = [[] for i in range(self.n)]
        
    def sommets(self):
        """
        Renvoie une liste des sommets
        """
        return self.liste_sommets
    
    def ajoute_arc(self, sommetA, sommetB):
        """
        Ajoute dans la représentation de graphe l'arc sommetA - sommetB
        """
        assert (sommetA in self.liste_sommets), "sommet A pas dans le graphe"
        assert (sommetB in self.liste_sommets), "sommet B pas dans le graphe"
        self.adjacents[sommetA].append(sommetB)
        self.adjacents[sommetB].append(sommetA)
    
    def voisins(self, sommet):
        """
        Renvoie une liste des voisins du sommet dans la représentation du graphe
        """
        assert sommet in self.liste_sommets, "sommet pas dans le graphe"
        return self.adjacents[sommet]

    def est_arc(self, sommetA, sommetB):
        """
        Renvoie un booléen indiquant si l'arc sommetA - sommetB appartient au graphe
        """
        assert sommetA in self.liste_sommets, "sommetA pas dans le graphe"
        k = 0
        while k < len(self.adjacents[sommetA]) and self.adjacents[sommetA][k] != sommetB:
            k += 1
        return k < len(self.adjacents[sommetA])
    
    def export_matrice(self):
        """
        Renvoie une représentation du graphe sous forme de matrice  d'adjacence
        """
        mat = []
        for i in range(self.n):
            ligne = []
            for j in range(self.n):
                if self.est_arc(i, j):
                    ligne.append(1)
                else:
                    ligne.append(0)
            mat.append(ligne)                
        return mat
        
    

def test_graphe_liste():
    """
    Tests unitaires pour la classe Graphe_matrice
    """
    g1 = Graphe_liste([0, 1, 2, 3, 4])
    g1.ajoute_arc(1, 2)
    g1.ajoute_arc(1, 4)
    g1.ajoute_arc(2, 3)
    g1.ajoute_arc(2, 4)
    g1.ajoute_arc(3, 4)
    g1.ajoute_arc(4, 0)
    assert g1.est_arc(1, 2) == True, "échec sur g1.est_voisin(1, 2)"
    assert g1.est_arc(2, 1) == True, "échec sur g1.est_voisin(2, 1)"
    assert g1.sommets() == [0, 1, 2, 3, 4], "échec sur g1.sommets()"
    assert g1.voisins(2) == [1, 3, 4], "échec sur g1.voisins(2)"
    assert g1.voisins(1) == [2, 4], "échec sur g1.voisins(1)"
    assert g1.export_matrice() == [[0, 0, 0, 0, 1], [0, 0, 1, 0, 1], 
                                [0, 1, 0, 1, 1], [0, 0, 1, 0, 1],
                                [1, 1, 1, 1, 0]], "échec sur g1.export_matrice()"
    print("Tests réussis")

Représentations (Bac 🎯)⚓︎

Différentes représentations d'un graphe⚓︎

Représentation par matrice d'adjacence⚓︎

Représentation par tableau de listes d'adjacence⚓︎

Représentation par dictionnaire de listes d'adjacence⚓︎

Comparaison des représentations⚓︎

Complexité spatiale⚓︎

Complexité temporelle⚓︎

Implémentation de l'interface de la classe Graphe⚓︎

Implémentation de l'interface de la classe `Graphe`⚓︎