3-01. Les graphes
- Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs.
- Passer d’une représentation à une autre.
Les graphes font partie des objets fondamentaux en algorithmique. En effet, leur structure relationnelle intrinsèque leur permettent de modéliser naturellement de très nombreux problèmes dans des domaines variés comme, par exemple :
- les réseaux de communications,
- les réseaux routiers,
- les optimisations de chemins,
- la gestion des ressources mémoires d’un ordinateur,
- les réseaux sociaux,
- le traitement automatique des langues,
- et bien d’autres choses…
Dans tout ce chapitre, on ne va travailler que sur des graphes simples (au sens mathématique), c’est-à-dire pas d’arêtes multiples entre deux sommets et pas de boucles (arrête reliant un sommet à lui-même).
Généralités et vocabulaire
De manière simplifiée, un graphe est un ensemble de sommets reliés entre eux par des arêtes (graphe non orienté) ou des arcs (graphe orienté). Deux sommets peuvent être reliés par plusieurs arrêtes.
Vocabulaire
| Terme | Définition |
|---|---|
| ordre du graphe | nombre de sommets |
| taille du graphe | nombre d’arêtes ou d’arcs |
| boucle | arête ou arc reliant un sommet à lui-même |
| graphe non connexe | graphe pour lequel il existe au moins une paire de sommets entre lesquels aucun chemin n’existe. |
Exemples de graphes
Un graphe est défini par ses sommets et ses arrêtes ou arcs. Vous avez donc une infinité de représentations graphiques possibles pour un même graphe.
Structure de graphes
Décrire la structure des deux graphes ci-dessous (orienté ou non, connexe ou non). Préciser leur ordre et leur taille.
Correction
Figure 4a : graphe orienté non connexe, d’ordre 6 et de taille 8.
Figure 4b : graphe simple non orienté, d’ordre 5 et de taille 7.
Graphes valués
Dans un graphe valué, orienté ou non, chaque arête ou arc est associé à une valeur (un nombre réel).
Le mot connexion désigne indistinctement une arête ou un arc. Je m’en servirai dans la suite de mon cours pour simplifier l’écriture lorsque c’est nécessaire.
Exemples de graphes valués
Voisins et degré
Dans un graphe non orienté, si les sommets A et B sont reliés par une arête, alors on dit qu’ils sont adjacent ou voisins.
Dans un graphe orienté, si un arc relie A et B dans le sens A→B, on dit que A est un prédécesseur (ou voisin entrant) de B et B est un successeur ou (voisin sortant) de A.
Le degré d’un sommet est le nombre de connexions qui lui sont reliées.
Dans le cas d’un graphe orienté, on peut distinguer le degré entrant et le degré sortant d’un sommet.
Le degré maximal d’un graphe est le degré du sommet ayant le plus grand degré, et réciproquement pour le degré minimal.
Voisins & degrés
1. Donner les voisins des sommets A et E dans les deux graphes, en distinguant précédesseurs et successeurs le cas échéant.
2. Déterminer le degré de tous les sommets du graphe de à la figure 2a
3. Quels sont les degrés minimal et maximal de ce graphe ?
Correction
1.
Figure 1.a : voisins de A → B et E ; voisins de E → A, C et F
Figure 2.a : prédécesseurs de A → B, E, F ; successeurs de A → B et C ; prédécesseurs de E : E et F ; successeurs de E : A, E
2. degrés entrants en bleu, degrés sortants en rouge, degrés en noir.
3. degré maximal entrant : 3 ; degré maximal sortant : 2 ; degré maximal : 5
degré minimal entrant : 1 ; degré minimal sortant : 1 ; degré minimal : 3
Voisins & degrés (bis)
Soit les deux graphes représentés ci-dessous.
Graphe de la figure 4a
1.a. Quels sont les voisins des sommets 3 et 5 ? On précisera ses prédécesseurs et ses successeurs.
1.b. Quels sont les degrés entrant et sortant du sommet 4 ? Quel est son degré ?
Graphe de la figure 4b
2.a. Quels sont les sommets adjacents au sommet 3 et au sommet 4 ?
2.b. Quel est le degré du sommet 1 ?
2.c. Quel est le degré minimal du graphe ? le degré maximal ?
Correction
1.a. Sommet 5 → 2 (prédécesseur) et 4 (prédécesseur et successeur) ; Sommet 3 → 6 (prédécesseur)
1.b. Degrés entrant et sortant du sommet 4 → 2 et 2. Degré total → 4
2.a. Sommets adjacents au sommet 3 → {1, 2} et au sommet 4 → {1, 2, 5}
2.b. Degré du sommet 1 → 4
2.c. Degré minimal du graphe → 2, degré maximal → 4
Chemins
Un chemin entre deux sommets A et B d’un graphe est une suite de connexions consécutives permettant de passer de A à B.
Bien évidemment, on doit respecter le sens des arcs dans le cas d’un graphe orienté.
Vocabulaire
| Terme | Définition |
|---|---|
| chemin simple | chemin constitué de connexions toutes distinctes (on ne repasse pas plusieurs fois par la même connexion) |
| chemin fermé | chemin dont le sommet de départ et le sommet d’arrivé sont identiques |
| cycle | chemin simple fermé |
| longueur d’un chemin | nombre de connexions qui le composent |
| distance entre A et B | longueur du plus court chemin Allant de A vers B |
| diamètre d’un graphe | plus grande distance entre deux sommets quelconques |
Chemins, distance et diamètre
Soit les deux graphes représentés ci-dessous.
1. Graphe de la figure 1
- Existe-t-il toujours un chemin entre deux sommets donnés ? Si non, quels sous-graphes vérifient cette propriété ?
- Donner un chemin de longueur 4 partant du sommet 1 et arrivant au sommet 5.
- Donner un cycle de longueur 5 partant du sommet 2.
- Dans le sous-graphe formé par les sommets 1, 2, 4 et 5, existe-t-il un chemin contenant une et une seule fois tous les sommets ?
- Quelle est la distance entre les sommets 1 et 5 ? entre les sommets 1 et 3 ?
- En déduire le diamètre du graphe.
2. Graphe de la figure 2
- Existe-t-il toujours un chemin entre deux sommets ? Si non, quels sous-graphes vérifient cette propriété ?
- Existe-t-il un chemin de longueur 3 entre les sommets 1 et 3 ?
- Le graphe est-il acyclique ?
- Existe-t-il un chemin contenant une et une seule fois toutes les arêtes ?
- Quelle est la distance entre les sommets 1 et 5 ? entre les sommets 3 et 5 ?
- Quel est le diamètre du graphe ?
Correction
Graphe 1
- Non, le sous-graphe {3,6} est isolé du sous-graphe {1, 2, 4, 5}. Mais le sous-graphe {1, 2, 4, 5} possède un chemin pour chaque paire de sommets.
- {1, 2, 2, 4, 5}
- {2, 2, 5, 4, 1, 2}
- Oui : {1, 2, 5, 4} ou encore {1, 2, 4, 5}
- distance entre les sommets 1 et 5 → 2, entre les sommets 1 et 3 → infinie
- Diamètre infini
Graphe 2
- Oui
- {1, 4, 2, 3}
- Non, il existe plusieurs cycles (ex. {1, 5, 4, 1})
- Oui, par exemple {1, 5, 4, 2, 3}
- distance entre les sommets 1 et 5 → 1, entre les sommets 3 et 5 → 2
- Diamètre 2
Matrice d’adjacence
Une matrice d’adjacence est un tableau à deux dimensions de taille $*n \times n*$, où $*n*$ est le nombre de sommets du graphe. Chaque case $*M[i][j]*$ de la matrice porte une information sur l’éventuelle connexion de $*i*$ vers $*j*$.
Cas des graphes non-valués
Pour un graphe non-valué, on utilise généralement :
- $*M[i][j]*$ = 1 s’il existe une connexion de $*i*$ vers $*j*$
- $*M[i][j]*$ = 0 sinon
Dans le cas d’un graphe non orienté, la matrice est symétrique : $*M[i][j] = M[j][i]*$.
Exemple de matrice d’adjacence d’un graphe non-orienté
| A | B | C | E | F | |
|---|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 | 0 |
| B | 1 | 0 | 1 | 0 | 0 |
| C | 0 | 1 | 0 | 1 | 0 |
| E | 1 | 0 | 1 | 0 | 1 |
| F | 0 | 0 | 0 | 1 | 0 |
M = [ [0, 1, 0, 1, 0],
[1, 0, 1, 0, 0],
[0, 1, 0, 1, 0],
[1, 0, 1, 0, 1],
[0, 0, 0, 1, 0] ]
Implémentation Python
Matrice d’adjacence d’un graphe orienté
Donner l’implementation Python de la matrice d’adjacence du graphe ci-dessous.
Correction
M = [
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 0],
[0, 0, 0, 0, 1],
[1, 0, 0, 1, 0],
[1, 0, 0, 1, 0]
]
Cas des graphes valués
Pour les graphes valués, la matrice d’adjacence fonctionne de la même manière, sauf qu’au lieu d’attribuer la valeur 1 à une connexion entre deux sommets, on lui attribue sa propre valeur. Si deux sommets ne sont pas connectés, la valeur de la « connexion » est conventionnelle. On peut lui attribuer la valeur 0, infinie (float('inf') en Python) ou encore NULL (None en Python).
Matrice d’adjacence d’un graphe valué
Donner la matrice d’adjacence pour le graphe ci-dessous.
Correction
M = [
[.7, .2, .1],
[.6, .4, None],
[.15, None, .85]
]
Avantages et inconvénients
La représentation d’un graphe à l’aide d’une matrice d’adjacence a de nombreux avantages :
- on a un accès rapide à une connexion donnée et aux voisins d’un sommet donné ;
- il est facile de connaître le nombre de chemin de longueur $*p*$ partant du sommet $*i*$ et arrivant au sommet $*j*$ (on y reviendra plus tard).
Le principal inconvénient de la représentation d’un graphe par matrice d’adjacence est la taille mémoire puisqu’il faut gérer $*n^2*$ cases mémoires pour représenter un graphe à $*n*$ sommets.
Ce mode de représentation est en général utilisé uniquement pour les graphes de petite taille ou les graphes denses, c’est-à-dire lorsque chaque sommet est connecté à la plupart des autres sommets, ou quand on veut savoir rapidement s’il existe une connexion entre deux sommets donnés.
Exploiter une matrice d’adjacence
Soit le graphe ci-dessous :
graphe = [ [0, 1, 1, 0, 0],
[1, 0, 1, 0, 0],
[0, 0, 0, 0, 1],
[1, 0, 0, 1, 0],
[1, 0, 0, 1, 0], ]
1. Écrire un script qui donne l’ordre de ce graphe.
2. Écrire un script qui donne la taille de ce graphe.
3. Écrire une fonction qui permet de vérifier si un nœud $*i*$ est connecté à un nœud $*j*$ ?
Correction
# ordre du graphe
ordre = len(graphe)
# taille du graphe
taille = 0
for line in graphe:
taille += sum(line)
# connexion entre sommets
def sont_connectes(graphe, si, sj):
return graphe[si][sj] == 1
Liste d’adjacence
Définition et exemples
Une liste d’adjacence est une autre structure de données utilisée pour représenter un graphe. Pour chaque sommet du graphe, on associe une liste contenant tous les sommets adjacents.
| Sommet | Liste d’adjacence |
|---|---|
| A | B, E |
| B | A, C |
| C | B, E |
| E | A, C, F |
| F | E |
L = { "A": ["B", "E"],
"B": ["A", "C"],
"C": ["B", "E"],
"E": ["A", "C", "F"],
"F": ["E"] }
Implémentation en Python
Liste d’adjacence d’un graphe orienté
Donner la liste d’adjacence pour le graphe ci-dessous, implémentée en Python.
Correction
graphe = {
"A" : ["B", "C"],
"B" : ["A", "C"],
"C" : ["F"],
"E" : ["A", "E"],
"F" : ["A", "E"],
}
Avantages et inconvénients
La représentation des graphes à l’aide de listes d’adjacences a de nombreux avantages :
- elle permet de parcourir rapidement les voisins d’un sommet donné ;
- elle est compacte : on code uniquement les connexions présentes dans le graphe ;
- elle est robuste : on peut facilement modifier/ajouter des attributs pour prendre en charge les différents types de graphe.
Toutefois, elle a plusieurs inconvénients potentiels. Par exemple, pour déterminer si une connexion donnée $*p_{i,j}*$ est présent(e) dans le graphe, il n’existe pas de moyen plus rapide que de rechercher $*j*$ dans la liste d’adjacence du sommet $*i*$.
Par conséquent, ce mode de représentation est en général utilisé pour les graphes peu denses, c’est-à-dire lorsque chaque sommet est connecté à un petit nombre d’autres sommets.
Liste d’adjacence en Python
Soit le graphe ci-dessous :
graphe = { "A" : ["B", "C"],
"B" : ["A", "C"],
"C" : ["F"],
"E" : ["A", "E"],
"F" : ["A", "E"] }
1. Écrire un script pour déterminer l’ordre de ce graphe ?
2. Écrire un script pour déterminer la taille de ce graphe ?
3. Écrire une fonction qui vérifie si un nœud $*i*$ est connecté à un nœud $*j*$ ?
Correction
# ordre
ordre = len(graphe)
# taille
taille = 0
for liste in graphe.values():
taille += len(liste)
def sont_connectes(graphe, si, sj):
return sj in graphe[si]
Révision & entraînement
Représentations
Pour chacun des graphes ci-dessous, donner la représentation à l’aide d’une matrice d’adjacence et une représentation à l’aide de listes d’adjacences.
Correction
graphe1_matrice = [
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0],
]
graphe1_adjacences = {
1: [2],
2: [2, 4, 5],
3: [],
4: [1, 5],
5: [4],
6: [3],
}
graphe2_matrice = [
[0, 1, 1, 1, 1],
[1, 0, 1, 1, 0],
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 1],
[1, 0, 0, 1, 0],
]
graphe2_adjacences = {
1: [2, 3, 4, 5],
2: [1, 3, 4],
3: [1, 2],
4: [1, 2, 5],
5: [1, 4],
}
Matrice d’adjacence
On considère un graphe G dont la matrice d’adjacence est :
graphe = [
[0,1,1,1,0,0],
[1,0,1,0,1,1],
[1,1,0,1,1,0],
[1,0,1,0,1,1],
[0,1,1,1,0,1],
[0,1,0,1,1,0],
]
1. Le graphe $*G*$ est-il orienté ou non orienté ?
2. Quels sont l’ordre et la taille de $*G*$ ?
3. Donner une représentation du graphe $*G*$ sous forme de listes d’adjacences, puis sous forme graphique.
Correction
1. La matrice est symétrique, donc il s’agit d’un graphe non orienté.
2. Il s’agit d’une matrice 6×6, donc l’ordre du graphe est de 6.On compte 22 fois le nombre 1 dans la matrice. Mais comme il s’agit d’un graphe non orienté, chaque arête est comptée deux fois (une fois dans un sens, une fois dans l’autre). Il y a donc 11 arêtes.
3. Liste d’ajacence :
graphe = {
1: [2, 3, 4],
2: [1, 3, 5, 6],
3: [1, 2, 4, 5],
4: [1, 3, 5, 6],
5: [2, 3, 4, 6],
6: [2, 4, 5],
}
Liste d’adjacence
On considère un graphe G représenté par les listes d’adjacences suivantes :
G = {
1: [3, 4, 5],
2: [3, 5],
3: [1, 2, 4],
4: [1, 2],
5: [2]
}
1. Le graphe $*G*$ est-il orienté ou non orienté ?
2. Quels sont l’ordre et la taille de $*G*$ ?
3. Le sommet 2 peut-il être atteint à partir du sommet 1 ?
4. Donner une représentation du graphe $*G*$ sous la forme d’une matrice d’adjacence, puis sous forme graphique.
Correction
1. Il est orienté, car la connexion 1→5 existe mais pas la connexion 5→1.
2. Ordre : 5, taille : 11
3. Oui, par le chemin 1→3→2.
4. Matrice d’adjacence et graphique
G_matrice = [
[0, 0, 1, 1, 1],
[0, 0, 1, 0, 1],
[1, 1, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 0] ]
Graphes non orientés
Dans tout cet exercice, on considère un graphe simple non orienté.
Partie 1 – Matrice d’adjacence
On suppose dans cette partie que le graphe est représenté par sa matrice d'adjacence $*M*$ implémentée sous forme de liste de listes. On suppose également pour simplifier que les sommets du graphe sont les nombres entiers de 0 à $*n*$−1, où $*n*$ est le nombre de sommets du graphe.
1. La fonction get_liste_voisins ci-dessous prend en paramètre la matrice M et un sommet, et renvoie la liste des voisins de sommet. Compléter cette fonction.
def get_liste_voisins(M, sommet):
liste_voisins = []
for s in range(...):
if M[sommet][s] == ...:
liste_voisins.append(...)
return liste_voisins
2. Compléter la fonction sont_voisins ci-dessous qui prend en paramètre la matrice M et deux sommets du graphe, et renvoie un booléen.
def sont_voisins(M, sommet1, sommet2):
return ...
3. Compléter la fonction est_isole ci-dessous afin qu'elle réponde à sa documentation.
def est_isole(M, sommet):
'''
M = matrice d'adjacence d'un graphe simple non orienté
à n sommets numérotés de 0 à n-1
sommet = un sommet du graphe
Renvoie True si sommet est un sommet isolé, False sinon
'''
for s in range(...):
if M[...][...] != 0:
return ...
return ...
4. La fonction existe_chemin_longueur_2 ci-dessous prend en paramètre la matrice M et deux sommets du graphe, et renvoie un booléen. Compléter cette fonction.
def existe_chemin_longueur_2(M, sommet1, sommet2):
voisins_sommet1 = get_liste_voisins(...)
for sommet in voisins_sommet1:
if M[...][...] == 1:
return ...
return ...
5. Application. On considère le graphe suivant :
Implémenter la matrice d’adjacence et vérifier que les assertions ci-dessous ne provoquent aucune erreur.
# implémenter la matrice d’adjacence de ce graphe
M = ...
# Aucun des tests ci-dessous ne doit provoquer une AssertionError
assert get_liste_voisins(M, 4) == [1, 2, 3, 5]
assert sont_voisins(M, 1, 4)
assert not sont_voisins(M, 1, 5)
assert est_isole(M, 0)
assert not est_isole(M, 1)
assert existe_chemin_longueur_2(M, 1, 2)
assert not existe_chemin_longueur_2(M, 3, 6)
Partie 2 – Liste d’adjacence
On suppose à présent que le graphe est représenté par sa liste d'adjacence implémentées sous forme de dictionnaire, les clés étant les noms des sommets du graphe et les valeurs associées les sommets adjacents correspondants.
1. Réécrire les fonctions get_liste_voisins, sont_voisins, est_isole et existe_chemin_longueur_2 pour qu’elles utilisent une liste d’adjacence plutôt qu’une matrice d’adjacence.
2. Pour le graphe de la partie 1, écrire sa liste d’adjacence, puis exécuter les mêmes assertions pour tester vos fonctions.
Correction
Partie 1
def get_liste_voisins(M, sommet):
neighbor_list = []
for s in range(len(M)):
if M[sommet][s] == 1:
neighbor_list.append(s)
return neighbor_list
def sont_voisins(M, sommet1, sommet2):
return sommet2 in get_liste_voisins(M,sommet1)
def est_isole(M, sommet):
'''
M = matrice d'adjacence d'un graphe simple non orienté
à n sommets numérotés de 0 à n-1
sommet = un sommet du graphe
Renvoie True si sommet est un sommet isolé, False sinon
'''
for s in range(len(M)):
if M[sommet][s] != 0:
return False
return True
def existe_chemin_longueur_2(M, sommet1, sommet2):
voisins_sommet1 = get_liste_voisins(M, sommet1)
for sommet in voisins_sommet1:
if M[sommet2][sommet] == 1:
return True
return False
M = [
[ 0, 0, 0, 0, 0, 0, 0, 0 ], #0
[ 0, 0, 1, 0, 1, 0, 1, 1 ], #1
[ 0, 1, 0, 1, 1, 0, 0, 0 ], #2
[ 0, 0, 1, 0, 1, 0, 0, 0 ], #3
[ 0, 1, 1, 1, 0, 1, 0, 0 ], #4
[ 0, 0, 0, 0, 1, 0, 0, 1 ], #5
[ 0, 1, 0, 0, 0, 0, 0, 0 ], #6
[ 0, 1, 0, 0, 0, 1, 0, 0 ], #7
]
Graphes orientés
Dans tout cet exercice, on considère un graphe simple orienté.
Partie 1
On suppose dans cette partie que le graphe est représenté par sa matrice d'adjacence $*M*$ implémentée sous forme de liste de listes. On suppose également pour simplifier que les sommets du graphe sont les nombres entiers de 0 à $*n*$−1, où $*n*$ est le nombre de sommets du graphe.
1. La fonction successeurs ci-dessous prend en paramètre la matrice M et un sommet, et renvoie la liste des successeurs de ce sommet. Compléter cette fonction.
def get_successeurs(M, sommet):
liste_successeurs = []
for s in range(...):
if M[...][...] == 1:
liste_successeurs.append(...)
return liste_successeurs
2. Compléter la fonction prédécesseurs ci-dessous qui prend en paramètre la matrice M et un sommet, et renvoie la liste des prédécesseurs de sommet.
def get_predecesseurs(M, sommet):
liste_predecesseurs = []
for s in range(...):
if M[...][...] == 1:
liste_predecesseurs.append(...)
return liste_predecesseurs
3. Compléter la fonction est_isolé ci-dessous afin qu'elle réponde à sa documentation.
def est_isole(M, sommet):
'''
M est la matrice d'adjacence d'un graphe simple orienté
à n sommets numérotés de 0 à n-1
sommet est un sommet du graphe
Renvoie True si sommet est un sommet isolé du graphe, False sinon
'''
liste_predecesseurs = ...
liste_successeurs = ...
return ...
4. La fonction get_degres ci-dessous prend en paramètre la matrice M et un sommet, et renvoie un tuple contenant le degré entrant, le degré sortant et le degré du sommet. Compléter cette fonction.
def degres(M, sommet):
liste_predecesseurs = ...
liste_successeurs = ...
degre_entrant = ...
degre_sortant = ...
degre = ...
return degre_entrant, degre_sortant, degre
5. Applications. On considère le graphe suivant :
Implémenter la matrice d’adjacence et vérifier que les assertions ci-dessous ne provoquent aucune erreur.
# implémenter la matrice d’adjacence de ce graphe
M = ...
# Aucun des tests ci-dessous ne doit provoquer une AssertionError
assert get_successeurs(M, 1) == [2, 4, 6]
assert get_successeurs(M, 2) == []
assert get_predecesseurs(M, 1) == [4, 7]
assert get_predecesseurs(M, 2) == [1, 3, 4]
assert get_predecesseurs(M, 0) == []
assert est_isole(M, 0)
assert not est_isole(M, 5)
assert degres(M, 0) == (0, 0, 0)
assert degres(M, 1) == (2, 3, 5)
assert degres(M, 2) == (3, 0, 3)
assert degres(M, 6) == (1, 0, 1)
Partie 2
On suppose à présent que le graphe est représenté par ses listes d'adjacence implémentées sous forme de dictionnaire, les clés étant les noms des sommets du graphe et les valeurs associées les sommets adjacents correspondants.
1. Réécrire les quatre fonctions précédentes (get_successeurs, get_predecesseurs, est_isole, degres) de manière à ce qu’elles acceptent des listes d’adjacences plutôt qu’un matrice d’adjacences.
2. Implémenter les listes d'adjacence du graphe précédent, puis exécuter les mêmes assertions pour tester vos fonctions.
Correction
Partie 1
def get_successeurs(M, sommet):
liste_successeurs = []
for s in range(len(M)):
if M[sommet][s] == 1:
liste_successeurs.append(s)
return liste_successeurs
def get_predecesseurs(M, sommet):
liste_predecesseurs = []
for s in range(len(M)):
if M[s][sommet] == 1:
liste_predecesseurs.append(s)
return liste_predecesseurs
def est_isole(M, sommet):
liste_predecesseurs = get_predecesseurs(M, sommet)
liste_successeurs = get_successeurs(M, sommet)
return liste_predecesseurs == [] and liste_successeurs == []
def degres(M, sommet):
liste_predecesseurs = get_predecesseurs(M, sommet)
liste_successeurs = get_successeurs(M, sommet)
degre_entrant = len(liste_predecesseurs)
degre_sortant = len(liste_successeurs)
degre = degre_entrant + degre_sortant
return degre_entrant, degre_sortant, degre
M = [
[ 0, 0, 0, 0, 0, 0, 0, 0 ], #0
[ 0, 0, 1, 0, 1, 0, 1, 0 ], #1
[ 0, 0, 0, 0, 0, 0, 0, 0 ], #2
[ 0, 0, 1, 0, 1, 0, 0, 0 ], #3
[ 0, 1, 1, 1, 0, 1, 0, 0 ], #4
[ 0, 0, 0, 0, 0, 0, 0, 1 ], #5
[ 0, 0, 0, 0, 0, 0, 0, 0 ], #6
[ 0, 1, 0, 0, 0, 0, 0, 0 ], #7
]
Partie 2
def get_successeurs2(L, sommet):
return L[sommet]
def get_predecesseurs2(L, sommet):
liste_predecesseurs = []
for index, liste in enumerate(L):
if sommet in liste:
liste_predecesseurs.append(index)
return liste_predecesseurs
def est_isole2(L, sommet):
liste_predecesseurs = get_predecesseurs2(L, sommet)
liste_successeurs = get_successeurs2(L, sommet)
return liste_predecesseurs == [] and liste_successeurs == []
def degres2(L, sommet):
liste_predecesseurs = get_predecesseurs2(L, sommet)
liste_successeurs = get_successeurs2(L, sommet)
degre_entrant = len(liste_predecesseurs)
degre_sortant = len(liste_successeurs)
degre = degre_entrant + degre_sortant
return degre_entrant, degre_sortant, degre
# –––– Listes d’adjacences
L = [
[], #0
[2, 4, 6], #1
[], #2
[2, 4], #3
[1, 2, 3, 5], #4
[7], #5
[], #6
[1], #7
]