Remarque : nous aurons besoin d'importer graph, numpy, et certaines fonctions de votre TP1.
import numpy as np
from graph import *
# soit le graphe g0 suivant :
g0 = Graph()
g0.successors = {0:{2,3},
1:{1},
2:{1,3},
3:{0}}
g0.display(title="G0")
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.
# soit M0 la matrice du graphe g1 précédent
M0 = np.array([[0,0,1,1],
[0,1,0,0],
[0,1,0,1],
[1,0,0,0]])
print(M0)
[[0 0 1 1] [0 1 0 0] [0 1 0 1] [1 0 0 0]]
graphe_vers_matrice(g) qui retourne la matrice d'adjacence d'un graphe g (orienté ou non) donné.Exemple :
graphe_vers_matrice(g0)
array([[0., 0., 1., 1.],
[0., 1., 0., 0.],
[0., 1., 0., 1.],
[1., 0., 0., 0.]])
matrice_vers_graphe(M,orientation) qui retourne le graphe (orienté si le paramètre orientation vaut True, non orienté sinon) d'une matrice d'adjacence M.Exemple :
test = matrice_vers_graphe(M0, True)
test.successors
{0: {2, 3}, 1: {1}, 2: {1, 3}, 3: {0}}
M1 = np.array([[1,1,0],[1,1,0],[0,0,1]])
M2 = np.array([[1,1,1],[1,0,0],[0,0,1]])
M3 = np.array([[1,1,1],[0,1,1],[0,0,1]])
M4 = np.array([[1,0,1],[0,0,0],[0,0,0]])
print(M1)
[[1 1 0] [1 1 0] [0 0 1]]
print(M2)
[[1 1 1] [1 0 0] [0 0 1]]
print(M3)
[[1 1 1] [0 1 1] [0 0 1]]
print(M4)
[[1 0 1] [0 0 0] [0 0 0]]
Créer une fonction reflexive(M) qui, pour une matrice booléene donnée $M$, renvoie Truesi la relation binaire associée est réflexive, False sinon.
Tester votre fonction sur les matrices $M_i$ précédemment construites.
Exemple :
print(reflexive(M1),reflexive(M2),reflexive(M3),reflexive(M4))
True False True False
symetrique(M) et antisymetrique(M).Exemple :
print(symetrique(M1),symetrique(M2),symetrique(M3),symetrique(M4))
True False False False
print(antisymetrique(M1),antisymetrique(M2),antisymetrique(M3),antisymetrique(M4))
False False True True
Rappel :
Un graphe orienté $G$ est dit transitif si la propriété suivante est vérifiée :
$$\forall {i,j,k}, \quad G_{i,j}=1 \text{ et } G_{j,k}=1 \quad \Rightarrow \quad G_{i,k}=1$$
g1 = matrice_vers_graphe(M1, True)
g1.display(title="G1")
g2 = matrice_vers_graphe(M2, True)
g2.display(title="G2")
g3 = matrice_vers_graphe(M3, True)
g3.display(title="G3")
g4 = matrice_vers_graphe(M4, True)
g4.display(title="G4")
Créer une fonction transitive(g) en utilisant la définition de la transitivité.
Exemple :
print(transitive(g1),transitive(g2),transitive(g3),transitive(g4))
True False True True
On rappelle qu'une relation binaire est transitive ssi sa matrice $M$ vérifie : $M = M+M^2$
transitive2(M), qui utilise la propriété précédente, et tester la sur les matrices $M_i$. Attention aux opérations avec des matrices booléennes !
Une possibilté est de faire les opérations matricielles classiques puis de revenir à du booléen, en remplaçant tous les coefficients strictement positifs par 1.
Exemple :
print(transitive(M1),transitive(M2),transitive(M3),transitive(M4))
True False True True
print(equivalence(M1),equivalence(M2),equivalence(M3))
True False False
ordre(M) qui, pour une matrice booléene donnée $M$, renvoie Truesi la relation binaire associée est une relation d'ordre, False sinon.Exemple :
print(ordre(M1),ordre(M2),ordre(M3))
False False True
Le diagramme de Hasse d'une relation d'ordre est obtenu en retirant toutes les boucles issues de la réflexivité, ainsi que tous les raccourcis issus de la transitivité. C'est en quelque sorte une version plus lisible de la structure ordonnée.
hasse(M) qui, pour une matrice booléene donnée $M$ d'une relation d'ordre, renvoie la matrice du diagramme de Hasse associé à $M$.Exemple :
M4=np.zeros((4,4))
M4[0,0]=M4[0,2]=M4[0,3]=1
M4[1,0]=M4[1,1]=M4[1,2]=M4[1,3]=1
M4[2,2]=M4[2,3]=1
M4[3,3]=1
print(M4, ordre(M4))
[[1. 0. 1. 1.] [1. 1. 1. 1.] [0. 0. 1. 1.] [0. 0. 0. 1.]] True
g4 = matrice_vers_graphe(M4,True)
g4.display(title='G4')
g4Hasse = matrice_vers_graphe(hasse(M4),True)
g4Hasse.display(title='G4Hasse')
matdiv(n) retournant la matrice d'adjacence de la relation "divise" sur les nombres entiers 1, 2, ..., n.On aura donc $M_{i,j}$ = 1 ssi (i+1) divise (j+1).
Exemple :
matdiv(8)
array([[1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 0, 1, 0, 1],
[0, 0, 1, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1]])
g5 = matrice_vers_graphe(hasse(matdiv(8)),True)
g5.display(label=[1,2,3,4,5,6,7,8], title="matdiv(8)")
s.display(title="S")
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é, 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) qui calcule $A^p$)