Relacije u SAGE-u
verzija: SageMath 9.4
In [1]:
load('relacije.sage')
Binarna relacija zadana pomoću neke formule
Primjer
Na skupu svih podskupova skupa $\{1,2,3\}$ zadana je relacija $\rho$ formulom: $x\mathrel{\rho}y\Leftrightarrow x\subseteq y$. Odredite matricu incidencije relacije $\rho$, ispišite njezine elemente i nacrtajte njezin graf.
Rješenje
In [2]:
skup1 = Subsets(3).list()
formula1 = lambda x,y: x & y == x
Matrica incidencije relacije $\rho$
In [3]:
matrica1 = relacija_formula(skup1,formula1)
matrica1
Out[3]:
In [4]:
matrica_table(matrica1,skup1,skup1)
In [5]:
matrica_html(matrica1,skup1,skup1)
Out[5]:
Elementi relacije $\rho$
In [6]:
relacija_formula(skup1,formula1,izlaz="elementi")
Out[6]:
Graf relacije $\rho$
In [7]:
relacija_formula(skup1,formula1,izlaz="graf").show(figsize=[6,6])
Binarna relacija zadana pomoću matrice incidencije
Primjer
Na skupu $\{1,2,3,4\}$ zadana je relacija matricom incidencije $$\begin{bmatrix}1&0&0&1\\ 0&1&1&0\\ 0&0&1&1\\ 0&0&1&0\end{bmatrix}.$$ Ispišite elemente zadane relacije i nacrtajte njezin graf.
Rješenje
In [8]:
M1 = matrix([[1,0,0,1],[0,1,1,0],[0,0,1,1],[0,0,1,0]])
Elementi relacije
In [9]:
relacija_matrica(M1)
Out[9]:
Graf relacije
In [10]:
relacija_matrica(M1,izlaz="graf")
Out[10]:
Primjer
Na skupu $\{a,b,c,d\}$ zadana je relacija matricom incidencije $$\begin{bmatrix}1&0&0&1\\ 0&1&1&0\\ 0&0&1&1\\ 0&0&1&0\end{bmatrix}.$$ Ispišite elemente zadane relacije i nacrtajte njezin graf.
Rješenje
In [11]:
var('a,b,c,d')
M2 = matrix([[1,0,0,1],[0,1,1,0],[0,0,1,1],[0,0,1,0]])
Elementi relacije
In [12]:
relacija_matrica(M2,oznakeElemenata=[a,b,c,d])
Out[12]:
Graf relacije
In [13]:
relacija_matrica(M2,oznakeElemenata=['a','b','c','d'],izlaz="graf")
Out[13]:
Binarna relacija zadana pomoću svojih elemenata
Primjer
Na skupu $\{1,2,3,4\}$ zadana je relacija $\rho=\{(1,1), (1,4), (2,2), (2,3), (3,3), (3,4), (4,3)\}$. Odredite matricu incidencije i nacrtajte graf relacije $\rho$.
Rješenje
In [14]:
skup2 = [1,2,3,4]
rel = [(1,1),(1,4),(2,2),(2,3),(3,3),(3,4),(4,3)]
Matrica incidencije relacije $\rho$
In [15]:
relacija_elementi(skup2,rel)
Out[15]:
Graf relacije $\rho$
In [16]:
relacija_elementi(skup2,rel,izlaz="graf",velicinaVrha=600)
Out[16]:
Binarna relacija zadana pomoću grafa
Primjer
Na skupu $\{a,b,c,d\}$ zadana je relacija $\rho$ svojim grafom $\{a:[a,d], b:[b,c], c:[c,d], d:[c]\}$. Odredite matricu incidencije, nacrtajte graf relacije $\rho$ i ispišite njezine elemente.
Rješenje
In [17]:
vrhovi = ['a','b','c','d']
graf = {'a':['a','d'],'b':['b','c'],'c':['c','d'],'d':['c']}
Graf relacije $\rho$
In [18]:
relacija_graf(vrhovi,graf)
Out[18]:
Matrica incidencije relacije $\rho$
In [19]:
relacija_graf(vrhovi,graf,izlaz="matrica")
Out[19]:
Elementi relacije $\rho$
In [20]:
relacija_graf(vrhovi,graf,izlaz="elementi")
Out[20]:
Svojstva binarnih relacija
Zadatak
Na skupu $A=\{0,1,2,3,4,5,6\}$ zadana je relacija $R$ sa $$x\mathrel{R}y\Leftrightarrow (x < y) \text{ i } x \text{ je prost broj}.$$ Ispišite elemente zadane relacije, nacrtajte graf i napišite matricu incidencije. Provjerite koja svojstva zadovoljava relacija $R$.
Rješenje
In [21]:
formula2 = lambda x,y: (x<y) and is_prime(x)
Elementi relacije $R$
In [22]:
relacija_formula(range(7),formula2,izlaz="elementi")
Out[22]:
Graf relacije $R$
In [23]:
relacija_formula(range(7),formula2,izlaz="graf")
Out[23]:
Matrica incidencije relacije $R$
In [24]:
matricaR=relacija_formula(range(7),formula2,izlaz="matrica")
matrica_html(matricaR,range(7),range(7))
Out[24]:
Svojstva relacije $R$
In [25]:
[refleksivna(matricaR),irefleksivna(matricaR)]
Out[25]:
In [26]:
[simetricna(matricaR),antisimetricna(matricaR),asimetricna(matricaR)]
Out[26]:
In [27]:
[kompletna(matricaR),strogo_kompletna(matricaR)]
Out[27]:
In [28]:
tranzitivna(matricaR)
Out[28]:
In [29]:
[relacija_ekvivalencije(matricaR),parcijalni_uredjaj(matricaR),linearni_uredjaj(matricaR)]
Out[29]:
Zadatak
Nacrtajte graf relacije $\rho=\big\{(x,y)\in\mathbb{R}^2: y\geq\sqrt{x},\, x,y\in[0,1]\big\}$.
Rješenje
In [30]:
var('x,y')
region_plot(y >= sqrt(x),(x,0,1),(y,0,1))
Out[30]:
In [31]:
region_plot([y >= sqrt(x),x<1,y<1],(x,0,1.3),(y,-0.3,1.3),aspect_ratio=1,incol='pink')
Out[31]:
Zadatak
Na skupu $A=\{2,3,4,5,6,7,8,9,10\}$ zadana je relacija $\rho=\big\{(x,y)\in A^2: x\equiv y\!\pmod{4}\big\}$. Ispišite elemente zadane relacije, nacrtajte graf i napišite matricu incidencije. Dokažite da je $\rho$ relacija ekvivalencije.
Rješenje
In [32]:
A = range(2,11)
for3 = lambda x,y: mod(x-y,4)==0
Elementi relacije $\rho$
In [33]:
relacija_formula(A,for3,izlaz="elementi")
Out[33]:
Graf relacije $\rho$
In [34]:
relacija_formula(A,for3,izlaz="graf").show(figsize=[5,5])
Matrica incidencije relacije $\rho$
In [35]:
matricaRO=relacija_formula(A,for3,izlaz="matrica")
matrica_html(matricaRO,A,A)
Out[35]:
$\rho$ je relacija ekvivalencije
In [36]:
relacija_ekvivalencije(matricaRO)
Out[36]:
Zadatak
Na skupu $S=\{1,2,4,6,8\}$ zadana je relacija $\preccurlyeq$ s $$a\preccurlyeq b\Leftrightarrow \frac{a}{b}\in\mathbb{N}.$$ Ispišite elemente zadane relacije, nacrtajte graf i napišite matricu incidencije. Dokažite da je $\preccurlyeq$ relacija parcijalnog uređaja.
Rješenje
In [37]:
S = [1,2,4,6,8]
for4 = lambda a,b: mod(a,b)==0
Elementi relacije $\preccurlyeq$
In [38]:
relacija_formula(S,for4,izlaz="elementi")
Out[38]:
Graf relacije $\preccurlyeq$
In [39]:
relacija_formula(S,for4,izlaz="graf")
Out[39]:
Matrica incidencije relacije $\preccurlyeq$
In [40]:
mat=relacija_formula(S,for4,izlaz="matrica")
matrica_html(mat,S,S)
Out[40]:
$\preccurlyeq$ je relacija parcijalnog uređaja
In [41]:
parcijalni_uredjaj(mat)
Out[41]:
$\preccurlyeq$ nije relacija linearnog uređaja
In [42]:
linearni_uredjaj(mat)
Out[42]:
Hasseov dijagram parcijalnog uređaja $\preccurlyeq$
In [43]:
hasse=Poset((S,for4))
hasse.show(figsize=[3,3],axes_pad=0.1)
ne postoji najmanji element
In [44]:
[hasse.has_bottom(),hasse.bottom()]
Out[44]:
najveći element je 1
In [45]:
[hasse.has_top(),hasse.top()]
Out[45]:
minimalni elementi
In [46]:
hasse.minimal_elements()
Out[46]:
maksimalni elementi
In [47]:
hasse.maximal_elements()
Out[47]:
Parcijalno uređeni skupovi i Hasseovi dijagrami
Skup svih podskupova skupa $\{1,2,3\}$ uz parcijalni uređaj "biti podskup"
In [48]:
Subsets(3).list()
Out[48]:
In [49]:
Subsets(3)
Out[49]:
In [50]:
type(Subsets(3))
Out[50]:
definicija parcijalnog uređaja
In [51]:
pus1=Poset((Subsets(3).list(),lambda x,y: x & y == x))
Hasseov dijagram
In [52]:
pus1.show(vertex_size=1600,axes_pad=0.1)
In [53]:
type(pus1)
Out[53]:
najmanji element
In [54]:
pus1.bottom()
Out[54]:
najveći element
In [55]:
pus1.top()
Out[55]:
Skup svih nepraznih podskupova skupa $\{1,2,3\}$ uz parcijalni uređaj "biti podskup"
In [56]:
Subsets(3).list()[1:]
Out[56]:
definicija parcijalnog uređaja (dva načina)
In [57]:
pus2=Poset((Subsets(3).list()[1:], lambda x,y: x & y == x))
pus2dva=pus1.subposet(Subsets(3).list()[1:])
Hasseov dijagram
In [58]:
pus2.show(vertex_size=1600,figsize=[4,5],axes_pad=0.1)
In [59]:
pus2dva.show(vertex_size=1600,figsize=[4,5],axes_pad=0.1)
minimalni i maksimalni elementi
In [60]:
pus2.minimal_elements()
Out[60]:
In [61]:
pus2.maximal_elements()
Out[61]:
matrica incidencije
In [62]:
matPUS2 = relacija_formula(Subsets(3).list()[1:],lambda x,y: x & y == x,izlaz="matrica")
matrica_html(matPUS2, Subsets(3).list()[1:], Subsets(3).list()[1:])
Out[62]:
Graf relacije
In [63]:
relacija_formula(Subsets(3).list()[1:],lambda x,y: x & y == x,izlaz="graf").show(figsize=[5,5])
$\mathcal{P}(\{1,2,3\})\setminus\{\emptyset,\{1,2,3\}\}$ uz parcijalni uređaj "biti podskup"
In [64]:
Subsets(3).list()[1:-1]
Out[64]:
definicija parcijalnog uređaja (dva načina)
In [65]:
pus3=Poset((Subsets(3).list()[1:-1], lambda x,y: x & y == x))
pus3dva=pus1.subposet(Subsets(3).list()[1:-1])
Hasseov dijagram
In [66]:
pus3.show(figsize=[5,4],vertex_size=1000,axes_pad=0.1)
minimalni i maksimalni elementi
In [67]:
pus3.minimal_elements()
Out[67]:
In [68]:
pus3.maximal_elements()
Out[68]:
matrica incidencije
In [69]:
matPUS3 = relacija_formula(Subsets(3).list()[1:-1], lambda x,y: x & y == x,izlaz="matrica")
matrica_html(matPUS3, Subsets(3).list()[1:-1], Subsets(3).list()[1:-1])
Out[69]:
Graf relacije
In [70]:
relacija_formula(Subsets(3).list()[1:-1], lambda x,y: x & y == x,izlaz="graf").show(figsize=[5,5])
Parcijalno uređeni skup zadan preko elemenata (dva načina)
In [71]:
var('a,b,c,d,e,f')
pus5=Poset((['a','b','c','d','e','f'],[('a','d'),('d','e'),('b','e'),('b','c'),('c','f')]))
pus5dva=Poset({a:[d],b:[c,e],c:[f],d:[e],e:[],f:[]})
Hasseov dijagram
In [72]:
pus5.show(vertex_color='yellow',figsize=(4,4),axes_pad=0.1)
In [73]:
pus5dva.show(figsize=(4,4),axes_pad=0.1)
minimalni i maksimalni elementi
In [74]:
pus5dva.minimal_elements()
Out[74]:
In [75]:
pus5dva.maximal_elements()
Out[75]:
In [76]:
matPUS5 = matrica_incidencije_PUS((['a','b','c','d','e','f'],[('a','d'),('d','e'),('b','e'),('b','c'),('c','f')]))
matrica_html(matPUS5, [r'\(a\)',r'\(b\)',r'\(c\)',r'\(d\)',r'\(e\)',r'\(f\)'], [r'\(a\)',r'\(b\)',r'\(c\)',r'\(d\)',r'\(e\)',r'\(f\)'])
Out[76]:
In [77]:
matPUS5dva = matrica_incidencije_PUS({a:[d],b:[c,e],c:[f],d:[e],e:[],f:[]},redoslijed_elemenata=[a,b,c,d,e,f])
matrica_html(matPUS5dva, [a,b,c,d,e,f], [a,b,c,d,e,f])
Out[77]:
Graf relacije
In [78]:
relacija_matrica(matPUS5, oznakeElemenata=[a,b,c,d,e,f], izlaz="graf").show(figsize=[5,5])
Elementi relacije
In [79]:
relacija_matrica(matPUS5,oznakeElemenata=[a,b,c,d,e,f],izlaz="elementi")
Out[79]:
In [80]:
elementi_PUS((['a','b','c','d','e','f'],[('a','d'),('d','e'),('b','e'),('b','c'),('c','f')]))
Out[80]:
In [81]:
elementi_PUS({a:[d],b:[c,e],c:[f],d:[e],e:[],f:[]},redoslijed_elemenata=[a,b,c,d,e,f])
Out[81]:
Zadatak
Na skupu $A=\{0,1,2\}\times\{2,5,8\}$ definiramo relaciju parcijalnog uređaja $\preccurlyeq$ s $$(a,b)\preccurlyeq(c,d)\Leftrightarrow a+b \mid c+d.$$ Nacrtajte Hasseov dijagram i odredite najmanji, najveći, minimalne i maksimalne elemente u parcijalno uređenom skupu $A$.
Rješenje
In [82]:
A = list(map(lambda x:tuple(x),cartesian_product(([0,1,2],[2,5,8])).list()))
A
Out[82]:
In [83]:
rel = lambda x,y:mod(y[0]+y[1],x[0]+x[1])==0
In [84]:
pus6 = Poset((A,rel))
Elementi relacije
In [85]:
relacija_formula(A,rel,izlaz="elementi")
Out[85]:
Matrica incidencije relacije
In [86]:
matPUS6 = relacija_formula(A,rel,izlaz="matrica")
matrica_html(matPUS6,A,A)
Out[86]:
Graf relacije
In [87]:
relacija_formula(A,rel,izlaz="graf",velicinaVrha=900).show(figsize=[5,5])
Hasseov dijagram
In [88]:
pus6.show(vertex_size=900,vertex_color='yellow',figsize=[5,5],axes_pad=0.1)
parcijalno uređeni skup A nema najmanji, niti najveći element
In [89]:
[pus6.has_bottom(),pus6.has_top()]
Out[89]:
minimalni i maksimalni elementi u parcijalno uređenom skupu $A$
In [90]:
pus6.minimal_elements()
Out[90]:
In [91]:
pus6.maximal_elements()
Out[91]:
svi elementi između $(0,2)$ i $(0,8)$ u parcijalno uređenom skupu $A$
In [92]:
pus6.interval((0,2),(0,8))
Out[92]:
In [93]:
pus6.closed_interval((0,2),(0,8))
Out[93]:
In [94]:
pus6.open_interval((0,2),(0,8))
Out[94]:
između $(0,2)$ i $(1,5)$ nema drugih elemenata osim njih samih
In [95]:
pus6.interval((0,2),(1,5))
Out[95]:
In [96]:
pus6.open_interval((0,2),(1,5))
Out[96]:
između $(1,5)$ i $(0,2)$ nema niti jednog elementa jer je $(1,5)$ veći od $(0,2)$
In [97]:
pus6.interval((1,5),(0,2))
Out[97]:
između $(1,5)$ i $(0,8)$ nema niti jednog elementa jer su ti elementi neusporedivi
In [98]:
pus6.interval((1,5),(0,8))
Out[98]:
svi elementi od kojih postoji luk prema elementu $(2,8)$
In [99]:
pus6.lower_covers((2,8))
Out[99]:
ne postoji element od kojeg bi postojao luk prema elementu $(1,2)$
In [100]:
pus6.lower_covers((1,2))
Out[100]:
od elementa $(2,8)$ ne postoji niti jedan luk prema nekom drugom elementu
In [101]:
pus6.upper_covers((2,8))
Out[101]:
od elementa $(1,2)$ postoje lukovi prema elementima $(1,8)$ i $(1,5)$
In [102]:
pus6.upper_covers((1,2))
Out[102]:
uspoređivanje elemenata
In [103]:
pus6.compare_elements((0,2),(0,2))
Out[103]:
In [104]:
pus6.compare_elements((0,2),(0,8))
Out[104]:
In [105]:
pus6.compare_elements((0,8),(0,2))
Out[105]:
In [106]:
print(pus6.compare_elements((0,2),(0,5)))
Nivoi u Hasseovom dijagramu
In [107]:
pus6.level_sets()
Out[107]:
neko proširenje parcijalnog uređaja na skupu $A$ do linearnog uređaja na skupu $A$
In [108]:
pus6.linear_extension()
Out[108]:
postoji ukupno 8154 različitih linearnih proširenja definiranog parcijalnog uređaja na skupu $A$
In [109]:
sva_prosirenja=pus6.linear_extensions()
len(sva_prosirenja)
Out[109]:
još neka proširenja parcijalnog uređaja na skupu $A$ do linearnog uređaja na skupu $A$
In [110]:
sva_prosirenja[1001]
Out[110]:
In [111]:
sva_prosirenja[83]
Out[111]:
In [112]:
sva_prosirenja[8100]
Out[112]:
svi antilanci u parcijalno uređenom skupu $A$
In [113]:
list(pus6.antichains())
Out[113]:
Zadatak
Na skupu $A=\{2,3,4,5,6,7,8,9,10\}$ definiramo relaciju parcijalnog uređaja $\preccurlyeq$ s $$x\preccurlyeq y\Leftrightarrow (x \mid y) \vee \big((x \text{ je prost}) \wedge (x< y)\big).$$ Nacrtajte Hasseov dijagram i odredite najmanji, najveći, minimalne i maksimalne elemente u parcijalno uređenom skupu $A$.
Rješenje
In [114]:
A = range(2,11)
relA = lambda x,y:mod(y,x)==0 or (is_prime(x) and x<y)
In [115]:
pus7 = Poset((A,relA))
Elementi relacije
In [116]:
relacija_formula(A,relA,izlaz="elementi")
Out[116]:
Matrica incidencije relacije
In [117]:
matPUS7 = relacija_formula(A,relA,izlaz="matrica")
matrica_html(matPUS7,A,A)
Out[117]:
Graf relacije
In [118]:
relacija_formula(A,relA,izlaz="graf").show(figsize=[5,5])
Hasseov dijagram
In [119]:
pus7.show(vertex_color='yellow',figsize=[4,4],axes_pad=0.1)
najmanji i najveći element
In [120]:
[pus7.has_bottom(),pus7.has_top()]
Out[120]:
In [121]:
pus7.bottom()
Out[121]:
minimalni i maksimalni elementi
In [122]:
pus7.minimal_elements()
Out[122]:
In [123]:
pus7.maximal_elements()
Out[123]:
svi elementi između 3 i 10
In [124]:
pus7.interval(3,10)
Out[124]:
In [125]:
pus7.open_interval(3,10)
Out[125]:
između 4 i 9 nema niti jednog elementa
In [126]:
pus7.interval(4,9)
Out[126]:
svi elementi od kojih postoji luk prema elementu 7
In [127]:
pus7.lower_covers(7)
Out[127]:
svi elementi prema kojima postoji luk od elementa 7
In [128]:
pus7.upper_covers(7)
Out[128]:
Nivoi u Hasseovom dijagramu
In [129]:
pus7.level_sets()
Out[129]:
neko proširenje parcijalnog uređaja na skupu $A$ do linearnog uređaja na skupu $A$
In [130]:
pus7.linear_extension()
Out[130]:
postoji ukupno 138 različitih linearnih proširenja definiranog parcijalnog uređaja na skupu $A$
In [131]:
svi=pus7.linear_extensions()
len(svi)
Out[131]:
još neka proširenja parcijalnog uređaja na skupu $A$ do linearnog uređaja na skupu $A$
In [132]:
svi[8]
Out[132]:
In [133]:
svi[59]
Out[133]:
In [134]:
svi[135]
Out[134]:
svi antilanci u parcijalno uređenom skupu $A$
In [135]:
list(pus7.antichains())
Out[135]:
Mreže
Mreža djeljitelja broja 12
definicija mreže
In [136]:
mreza1 = LatticePoset((divisors(12),lambda x,y:mod(y,x)==0))
Hasseov dijagram
In [137]:
mreza1.show(vertex_color='yellow',figsize=[4,4],axes_pad=0.1)
radi se o distributivnoj mreži
In [138]:
mreza1.is_distributive()
Out[138]:
$2\cdot3=1$
In [139]:
mreza1.meet(2,3)
Out[139]:
$2+3=6$
In [140]:
mreza1.join(2,3)
Out[140]:
$4+3=12$
In [141]:
mreza1.join(4,3)
Out[141]:
$4\cdot3=1$
In [142]:
mreza1.meet(4,3)
Out[142]:
Mreža djeljitelja broja 36
In [143]:
mreza2 = LatticePoset((divisors(36),lambda x,y:mod(y,x)==0))
In [144]:
mreza2.show(vertex_color='yellow',figsize=[4.5,4.5],axes_pad=0.1)
$4+18=36$
In [145]:
mreza2.join(4,18)
Out[145]:
$4\cdot18=2$
In [146]:
mreza2.meet(4,18)
Out[146]:
Mreža djeljitelja broja 90
In [147]:
mreza3 = LatticePoset((divisors(90),lambda x,y:mod(y,x)==0))
In [148]:
mreza3.show(vertex_color='yellow',axes_pad=0.1,vertex_size=500,figsize=[5,5])
$18+10=90$
In [149]:
mreza3.join(18,10)
Out[149]:
$18\cdot10=2$
In [150]:
mreza3.meet(18,10)
Out[150]:
Mreža svih podskupova $n$-članog skupa
In [151]:
Posets.BooleanLattice(4).show(axes_pad=0.1)
In [152]:
Posets.BooleanLattice(5).show(figsize=[10,10],vertex_size=500)
In [153]:
Posets.BooleanLattice(5).is_distributive()
Out[153]:
In [154]:
Posets.DiamondPoset(8).show()
In [155]:
Posets.PentagonPoset().show(figsize=[4,4],axes_pad=0.1)
In [156]:
Posets.PentagonPoset().is_distributive()
Out[156]:
In [157]:
Posets.IntegerPartitions(8).show(figsize=(10,10),vertex_size=1000,axes_pad=0.1)
Zatvorenja binarnih relacija
Refleksivno zatvorenje binarne relacije
Neka je $\rho$ binarna relacija na skupu $A$. Refleksivno zatvorenje relacije $\rho$ je relacija $R$ na skupu $A$ za koju vrijedi:
- Relacija $R$ je refleksivna relacija i sadrži relaciju $\rho$,
- Relacija $R$ je najmanja refleksivna relacija koja sadrži relaciju $\rho$, tj. svaka druga refleksivna relacija na skupu $A$ koja sadrži relaciju $\rho$ sadrži ujedno i relaciju $R$.
Primjer
Relacija (ne nužno refleksivna) zadana svojom matricom incidencije
In [158]:
matrica=random_matrix(GF(2),6,6)
In [159]:
refleksivna(matrica)
Out[159]:
refleksivno zatvorenje zadane relacije
In [160]:
matrica_refl = refleksivno_zatvorenje(matrica)
In [161]:
refleksivna(matrica_refl)
Out[161]:
In [162]:
matrica_html(matrica,range(1,7),range(1,7))
Out[162]:
In [163]:
matrica_html(matrica_refl,range(1,7),range(1,7))
Out[163]:
elementi relacije i elementi njezinog refleksivnog zatvorenja
In [164]:
relacija_matrica(matrica,izlaz="elementi")
Out[164]:
In [165]:
relacija_matrica(matrica_refl,izlaz="elementi")
Out[165]:
graf relacije i graf njezinog refleksivnog zatvorenja
In [166]:
graphics_array([relacija_matrica(matrica,izlaz="graf"),relacija_matrica(matrica_refl,izlaz="graf")]).show(figsize=[9,9])
Simetrično zatvorenje binarne relacije
Neka je $\rho$ binarna relacija na skupu $A$. Simetrično zatvorenje relacije $\rho$ je relacija $R$ na skupu $A$ za koju vrijedi:
- Relacija $R$ je simetrična relacija i sadrži relaciju $\rho$,
- Relacija $R$ je najmanja simetrična relacija koja sadrži relaciju $\rho$, tj. svaka druga simetrična relacija na skupu $A$ koja sadrži relaciju $\rho$, sadrži ujedno i relaciju $R$.
Primjer
Relacija (ne nužno simetrična) zadana svojom matricom incidencije
In [167]:
matrica2 = random_matrix(GF(2),6,6)
In [168]:
simetricna(matrica2)
Out[168]:
simetrično zatvorenje zadane relacije
In [169]:
matrica2_sim = simetricno_zatvorenje(matrica2)
In [170]:
simetricna(matrica2_sim)
Out[170]:
In [171]:
matrica_html(matrica2,range(1,7),range(1,7))
Out[171]:
In [172]:
matrica_html(matrica2_sim,range(1,7),range(1,7))
Out[172]:
elementi relacije i elementi njezinog simetričnog zatvorenja
In [173]:
relacija_matrica(matrica2,izlaz="elementi")
Out[173]:
In [174]:
relacija_matrica(matrica2_sim,izlaz="elementi")
Out[174]:
graf relacije i graf njezinog simetričnog zatvorenja
In [175]:
graphics_array([relacija_matrica(matrica2,izlaz="graf"),relacija_matrica(matrica2_sim,izlaz="graf")]).show(figsize=[9,9])
Tranzitivno zatvorenje binarne relacije
Neka je $\rho$ binarna relacija na skupu $A$. Tranzitivno zatvorenje relacije $\rho$ je relacija $R$ na skupu $A$ za koju vrijedi:
- Relacija $R$ je tranzitivna relacija i sadrži relaciju $\rho$,
- Relacija $R$ je najmanja tranzitivna relacija koja sadrži relaciju $\rho$, tj. svaka druga tranzitivna relacija na skupu $A$ koja sadrži relaciju $\rho$, sadrži ujedno i relaciju $R$.
Relacija (ne nužno tranzitivna) zadana svojom matricom incidencije
In [176]:
matrica3 = matrix([[0,0,0,1],[1,0,1,0],[1,0,0,1],[0,0,1,0]])
In [177]:
tranzitivna(matrica3)
Out[177]:
tranzitivno zatvorenje zadane relacije
In [178]:
matrica3_tran = tranzitivno_zatvorenje(matrica3)
In [179]:
tranzitivna(matrica3_tran)
Out[179]:
In [180]:
matrica_html(matrica3,range(1,5),range(1,5))
Out[180]:
In [181]:
matrica_html(matrica3_tran,range(1,5),range(1,5))
Out[181]:
elementi relacije i elementi njezinog tranzitivnog zatvorenja
In [182]:
relacija_matrica(matrica3, izlaz="elementi")
Out[182]:
In [183]:
relacija_matrica(matrica3_tran, izlaz="elementi")
Out[183]:
graf relacije i graf njezinog tranzitivnog zatvorenja
In [184]:
graphics_array([relacija_matrica(matrica3,izlaz="graf"),relacija_matrica(matrica3_tran,izlaz="graf")]).show(figsize=[9,9])
Najmanja relacija ekvivalencije koja sadrži zadanu relaciju
zadana relacija nije relacija ekvivalencije (nije čak niti refleksivna, niti simetrična, niti tranzitivna)
In [185]:
relacija = [(1,1),(1,9),(2,2),(3,3),(4,4),(4,9),(5,5),(8,2),(9,1),(9,4),(9,9)]
In [186]:
relacijaMatrica = relacija_elementi(range(1,10),relacija,izlaz="matrica")
In [187]:
[refleksivna(relacijaMatrica),simetricna(relacijaMatrica),tranzitivna(relacijaMatrica)]
Out[187]:
najmanja relacija ekvivalencije koja sadrži zadanu relaciju
In [188]:
rel_ekv = ekvivalencija_zatvorenje(relacijaMatrica)
In [189]:
[refleksivna(rel_ekv),simetricna(rel_ekv),tranzitivna(rel_ekv)]
Out[189]:
njihove matrice incidencije
In [190]:
matrica_html(relacijaMatrica,range(1,10),range(1,10))
Out[190]:
In [191]:
matrica_html(rel_ekv,range(1,10),range(1,10))
Out[191]:
njihovi elementi
In [192]:
relacija
Out[192]:
In [193]:
relacija_matrica(rel_ekv,izlaz="elementi")
Out[193]:
njihovi grafovi
In [194]:
graphics_array([relacija_matrica(relacijaMatrica,izlaz="graf"),relacija_matrica(rel_ekv,izlaz="graf")]).show(figsize=[9,9])
klasa ekvivalencije elementa 4
In [195]:
klase_ekvivalencije(rel_ekv, element=4)
Out[195]:
Kvocijentni skup (klase ekvivalencije svih elemenata)
In [196]:
klase_ekvivalencije(rel_ekv)
Out[196]:
In [ ]: