Matrice d’adjacence d’un graphe
On dispose du graphe non-orienté suivant :
- Donner la matrice d’adjacence de ce graphe.
G = [ [0, 0, 1, 0, 1],
[0, 0, 1, 0, 1],
[1, 1, 0, 1, 1],
[0, 0, 1, 0, 0],
[1, 1, 1, 0, 0]]
- Écrire une fonction qui indique s’il existe une arête entre les sommets s1 et s2. Le prototype est le suivant :
pres_arete(G : list, v1 : int, v2 : int) -> bool
- G -- matrice d’adjacence
- v1 -- n° sommet 1
- v2 -- n° sommet 2
- la fonction retourne True si une arête existe entre v1 et v2, False sinon et None en cas d'erreur
def pres_arete(G : list, v1 : int, v2 : int) -> bool:
"""
indique si une arête existe entre 2 sommets
Arguments:
G -- matrice d'adjacence
v1 -- n° sommet 1
v2 -- n° sommet 2
Retour:
True si une arrête existe entre v1 et v2, False sinon
None en cas d'erreur
"""
if 0 <= v1 <= len(G) and 0 <= v2 <= len(G):
if G[v1][v2]==1:
return True
else:
return False
else:
return None
- Valider les tests unitaires suivants :
- pres_arete(G, 0, 2) == True
- pres_arete(G, 2, 0) == True
- pres_arete(G, 1, 3) == False
- pres_arete(G, 3, 1) == False
- Écrire une fonction qui retourne la liste des voisins d’un sommet s. Le prototype est le suivant :
voisin(G : list, v : int) -> list
- G -- matrice d'ajacence
- v -- n° sommet
- la fonction retourne la liste des voisins de v
def voisin(G : list, v : int) -> list:
"""
recherche les voisins d'un sommet dans un graphe non orienté
Arguments:
G -- matrice d'adjacence
v -- n° sommet
Retour:
liste des voisins de v
"""
voisin = []
for i in range(len(G)):
if pres_arete(G, v, i):
voisin.append(i)
return voisin
- Valider les tests unitaires suivants :
- voisin(G, 0) == [2, 4]
- voisin(G, 2) == [0, 1, 3, 4]
En théorie des graphes, le degré (ou valence) d'un sommet d'un graphe est le nombre d’arêtes reliant ce sommet (les boucles comptées deux fois).
- Écrire une fonction qui renvoie le degré d’un sommet s. On donne le prototype :
degre(G : list, v : int) -> int
- G -- matrice d'adjacence
- v -- n° sommet
- la fonction retourne le degré du sommet dans G
def degre(G : list, v : int) -> int:
"""
calcul le degrée (ou valence) d'un sommet
ie: nombre d’arêtes reliant ce sommet (les boucles comptées deux fois).
Arguments:
G -- matrice d'adjacence
v -- n° sommet
Retour:
degrée du sommet dans G
"""
return len(voisin(G, v)) + G[v][v]
- Valider les tests unitaires suivants :
- degre(G, 0) == 2
- degre(G, 2) == 4
- Écrire une fonction qui renvoie le degré maximum de tous les sommets du graphe. On donne le prototype :
max_degre(G : list) -> int
- G -- matrice d'adjacence
- la fonction retourne le degré maximum de G
- Valider le test unitaire suivant :
- max_degre(G) == 4
def max_degre(G : list) -> int:
"""
calcul le degrée maximum d'un graphe
ie: nombre d’arêtes reliant ce sommet (les boucles comptées deux fois).
Arguments:
G -- matrice d'adjacence
Retour:
degrée maximum de G
"""
degres = []
for i in range(len(G)):
degres.append(degre(G, i))
return max(degres)
- Écrire une fonction qui renvoie le nombre d’arêtes du graphe. On donne le prototype :
arete(G : list) -> int
- G -- matrice d'adjacence
- la fonction retourne le nombre d'arêtes de G
def arete(G : list) -> int:
"""
calcul le nombre d'arêtes dans un graphe
Arguments:
G -- matrice d'adjacence
Retour:
nombre d'arêtes de G
"""
count = 0
for i in range(len(G)):
for j in range(len(G)):
count += G[i][j]
return count // 2
- Valider le test unitaire suivant :
- arete(G) == 6
- Écrire une fonction afficher(G) qui affiche la matrice d’adjacence G.
def afficher(G : list) -> str:
""" affiche la matrice d'adjacence """
matrice = ""
for i in range(len(G)):
for j in range(len(G)):
matrice += str(G[i][j]) + " "
matrice += "\n"
return matrice