Remarque : nous aurons besoin de numpy
, de dirmaths
et des fonctions du TP1. Pensez à les importer si besoin !
import numpy as np
from dirmaths import *
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 True
si la relation binaire associée est réflexive, False
sinon.
Tester votre fonction sur les matrices $M_i$ précédemment construites.
Exemples :
print(reflexive(M1),reflexive(M2),reflexive(M3),reflexive(M4))
True False True False
symetrique(M)
et antisymetrique(M)
.Exemples :
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
Un graphe $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$$
display(M1,title="M1",dispo="dot")
display(M2,title="M2",dispo="dot")
display(M3,title="M3", dispo="dot")
display(M4,title="M4", dispo="dot")
transitive(M)
en utilisant la définition de la transitivité.Exemples :
print(transitive(M1),transitive(M2),transitive(M3),transitive(M4))
True False True True
On rappelle qu'une matrice $M$ est transitive ssi : $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.
Exemples :
print(transitive2(M1),transitive2(M2),transitive2(M3),transitive2(M4))
True False True True
Faire la fermeture transitive d'un graphe, c'est rajouter les arcs manquants pour rendre le graphe transitif.
Si le graphe $G$, de matrice d'adjacence $M$ contient $n$ sommets, la fermeture transitive est alors donnée par la matrice $M^{*}$ valant :
$$M^* = M + M^2 + M^3 + ... + M^{n}$$
Construire une fonction FT(M)
qui retourne la fermeture transitive d'une matrice d'adjacence $M$ en utilisant la matrice $M^*$.
puissance(A,p)
du semestre 1, qui calcule $A^p$. FT(M2)
.display(FT(M2),title="FT(M2)",dispo="dot")
print(equivalence(M1),equivalence(M2),equivalence(M3))
True False False
ordre(M)
qui, pour une matrice booléene donnée $M$, renvoie True
si 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$ de 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
display(hasse(M4),title="Hasse de M4")
matdiv(n)
retournant la matrice d'adjacence de la relation "divise" sur les nombres entiers 1, 2, ..., n.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]])
display(hasse(matdiv(8)), label=[1,2,3,4,5,6,7,8], title="matdiv(8)")