import numpy as np
Tous les graphes manipulés dans ce TP et les suivants seront, sauf mention du contraire, des 1-graphes.
La matrice d'adjacence M d'un graphe orienté G est définie par :
$M_{i,j}=1$ si il y a un arc allant du sommet i vers le sommet j
$M_{i,j}=0$ sinon
Pour un graphe non orienté, la définition est similaire (on remarque donc que la matricie d'adjacence d'un graphe non-orienté est symétrique).
Exemple :
Une matrice d'adjacence M sera un objet array du package numpy.
M = np.array([[0,0,1,1],
[0,1,0,0],
[0,1,0,1],
[1,0,0,0]])
print(M)
[[0 0 1 1] [0 1 0 0] [0 1 0 1] [1 0 0 0]]
Nous avons écrit une fonction d'affichage d'un graphe à l'usage des étudiants. Cette fonction display() fait partie du fichier dirmaths.py, que vous pouvez charger directement à l'aide de la commande :
from dirmaths import *
Exemple :
Voici le graphe G, graphe orienté dont la matrice d'adjacence est la matrice M précédente.
display(M,directed=True,title='G')
Par défaut, l'argument directed vaut True.
Plusieurs dispositions de sommets peuvent être utilisées, vous pouvez les trouver ici .
Par défaut, la disposition choisie est neato.
Exemple :
display(M,title='Gdot',dispo='dot')
display(M,title='Gcirco',dispo='circo')
display(M,title='Gneato',dispo='neato')
display(M2,title="G2")
Différentes méthodes peuvent être utilisées :
# A partir de la matrice nulle :
M2 = np.zeros((5,5))
M2[0,0]=M2[0,1]=M2[0,2]=M2[1,3]=M2[1,4]=M2[2,1]=M2[2,4]=M2[3,2]=M2[3,4]=M2[3,3]=1
#
# En construisant la matrice :
M2bis = np.array([[1,1,1,0,0],[0,0,0,1,1],[0,1,0,0,1],[0,0,1,1,1],[0,0,0,0,0]])
mat_graphe_sans_boucle(M) qui renvoie la matrice du graphe orienté de matrice M sans ses boucles.Exemple :
M3 = mat_graphe_sans_boucle(M2)
display(M3,title='G3')
mat_graphe_ajoute_arcs(M,L) qui renvoie la matrice du graphe orienté de matrice M avec des arcs supplémentaires donnés par la liste de couples L.Exemple :
M4 = mat_graphe_ajoute_arcs(M3,[(1,2),(2,2),(4,3)])
display(M4,title='G4')
M5 = mat_graphe_oriente([(0,1),(0,2),(1,2),(1,3),(3,1),(3,2),(3,3)],4)
M5
array([[0, 1, 1, 0],
[0, 0, 1, 1],
[0, 0, 0, 0],
[0, 1, 1, 1]])
display(M5,title="G5")
Construire une fonction successeurs(M,x) qui retourne une liste contenant les successeurs du sommet x dans le graphe orienté de matrice M.
Construire une fonction predecesseurs(M,x) sur le même modèle que la fonction précédente.
Construire les fonctions degre_sortant(M,x) et degre_entrant(M,x) qui retournent le degré entrant/sortant du sommet x.
Exemple :
Reprenons le graphe G5, de matrice M5.
display(M5,title="G5")
successeurs(M5,1)
[2, 3]
predecesseurs(M5,1)
[0, 3]
print(degre_sortant(M5,3), degre_entrant(M5,3))
3 2
mat_graphe_non_oriente(L,n) qui retourne la matrice d'un graphe non orienté à n sommets, à partir des arêtes de la liste L.Exemple :
Soit un graphe non orienté G6, dont la liste des arêtes est L = [(0,1),(0,2),(1,2),(1,3),(3,2),(3,3)].
Attention, l'arête (0,1) correspond aux deux arcs (0,1) et (1,0). La matrice obtenue doit donc être symétrique !
M6 = mat_graphe_non_oriente([(0,1),(0,2),(1,2),(1,3),(3,2),(3,3)],4)
M6
array([[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 1]])
display(M6,title="G6",directed=False)
Construire une fonction voisins(M,x) qui retourne une liste contenant les voisins du sommet x dans le graphe non orienté de matrice M.
Construire une fonction degre(M,x) qui retourne le degré du sommet x.
Exemple :
voisins(M6,3)
[1, 2, 3]
degre(M6,2)
3
# Attention aux boucles !
degre(M6,3)
4
display(A1,title="A1")
racine(arbre) qui trouve la racine d'un arbre enraciné donné sous forme matricielle.Exemple :
racine(A1)
3
definition de largeur(Arbre) Visite = liste initialisée à vide Racine = racine de l'arbre File = liste des sommets à traiter, initialisée à Racine tant que File non vide sortir le premier sommet s de File mettre s dans Visite mettre tous les successeurs de s à la fin de la File fin tant que retourner Visite
definition de profondeur(Arbre) Visite = liste initialisée à vide Racine = racine de l'arbre Pile = liste des sommets à traiter, initialisée à Racine tant que Pile non vide sortir le premier sommet s de Pile mettre s dans Visite mettre tous les successeurs de s au début de Pile fin tant que retourner Visite
largeur(A) donnant le parcours en largeur d'un arbre enraciné A, donné sous forme matricielle.profondeur(A).Exemple :
largeur(A1)
[3, 0, 1, 2, 5, 6, 4, 7]
profondeur(A1)
[3, 0, 5, 7, 6, 1, 4, 2]
mat_arbre_depuis_pred(L) qui retourne la matrice d'un graphe enraciné, à partir de la liste L du prédecesseur de chacun des sommets (la racine aura par convention le prédécesseur -1).Exemple :
mat_arbre_depuis_pred([2,2,4,1,-1])
array([[0., 0., 0., 0., 0.],
[0., 0., 0., 1., 0.],
[1., 1., 0., 0., 0.],
[0., 0., 0., 0., 0.],
[0., 0., 1., 0., 0.]])
T = mat_arbre_depuis_pred([2,2,4,1,-1])
display(T,title='T')
Soit un mini-site intranet S composé de 5 pages, liées entre elles de la façon suivante :
display(S,title="S",dispo="dot")
Supposons un surfeur aléatoire se trouvant au sommet 0, et se déplaçant un certain nombre de fois sur ce site de manière équiprobable. On cherche alors à déterminer les probabilités de se trouver sur chacune des pages.
Pour cela, notons $P_n$ la matrice ligne contenant les probabilités de se trouver à chaque sommet après n déplacements.
Par exemple, la matrice des probabilités initiales est donc $P_0$ = (1, 0, 0, 0,0). En effet, le surf aléatoire commence au sommet 0.
Après 1 déplacement aléatoire, la matrice des probabilités est $P_1$ = (0, 1/3, 0, 1/3, 1/3). En effet, il y a une chance sur 3 d'être en 1, en 3 ou en 4.
On définit de plus la matrice de transition $Mt$ par :$Mt_{i,j}$ = "probabilité de passer du sommet i au sommet j"
On pourrait alors montrer que les probabilités de se trouver aux différents sommets après $n$ déplacements sont données par la formule :
$P_n$ = $P_{0}\times(Mt)^n$
Construire le graphe S ci-dessus.
Construire une fonction transition(G) qui calcule, pour un graphe $G$ donné sous forme matricielle, sa matrice de transition $Mt$.
Exemple :
transition(S)
array([[0. , 0.33333333, 0. , 0.33333333, 0.33333333],
[0. , 0. , 0. , 1. , 0. ],
[0. , 0.5 , 0. , 0.5 , 0. ],
[0. , 0.33333333, 0.33333333, 0. , 0.33333333],
[1. , 0. , 0. , 0. , 0. ]])
S après 1 déplacement.puissance(A,p) codée au semestre 1)largeur_graphe(G,sommet) donnant le parcours en largeur d'un graphe orienté quelconque G donné sous forme matricielle. Le paramètre sommet sera le premier sommet à visiter.Remarque : Afin d'éviter qu'un même sommet ne soit visité plusieurs fois, on instaurera un système de marquage : un sommet sera ajouté à la File que s'il n'est par encore marqué.
Exemple :
display(S,title="S",dispo="dot")
largeur_graphe(S,0)
[0, 1, 3, 4, 2]
profondeur_graphe(G,sommet) donnant le parcours en largeur d'un graphe orienté quelconque G donné sous forme matricielle. Le paramètre sommet sera le premier sommet à visiter.Exemple :
profondeur_graphe(S,0)
[0, 1, 3, 2, 4]