Stabla u SAGE-u
import sage.misc.banner
banner()
neka već definirana stabla u SAGE-u
BalancedTree
graphs.BalancedTree(3,2).show()
graphs.BalancedTree(2,3).show()
stablo nacrtano kao korijensko stablo
graphs.BalancedTree(3,2).show(layout="tree",tree_root=0)
graphs.BalancedTree(3,2).show(layout="tree",tree_root=8)
graphs.BalancedTree(3,2).show(layout="tree",tree_root=1,tree_orientation="up")
graphs.BalancedTree(2,3).show(layout="tree",tree_root=0)
graphs.BalancedTree(2,3).show(layout="tree",tree_root=4)
FibonacciTree
graphs.FibonacciTree(4).show()
graphs.FibonacciTree(8).show(figsize=(12,10),vertex_size=400)
PathGraph
graphs.PathGraph(8).show()
graphs.PathGraph(20).show()
StarGraph
graphs.StarGraph(7).show()
graphs.StarGraph(19).show(vertex_size=400)
DegreeSequenceTree
graphs.DegreeSequenceTree([2,1,2,3,1,1,1,2,1,4]).show(graph_border=True)
graphs.DegreeSequenceTree([3,1,3,3,1,1,1,2,1]).show(graph_border=True)
Pazite, u stablu vrijedi $\varepsilon=\nu-1$ pa zbog $\sum\limits_{v\in V(G)}{d(v)}=2\varepsilon$ mora biti $\nu-\frac{1}{2}\sum\limits_{v\in V(G)}{d(v)}=1$
graphs.trees
sva neizomorfna stabla sa 5 vrha
graphs_list.show_graphs(list(graphs.trees(5)))
sva neizomorfna stabla sa 7 vrhova
graphs_list.show_graphs(list(graphs.trees(7)))
šuma
stablo1=graphs.PathGraph(5)
stablo2=graphs.StarGraph(7)
graf=stablo1.disjoint_union(stablo2)
graf.show(vertex_labels=False,graph_border=True,vertex_size=80)
graf.is_forest()
graf.is_tree()
Kontrakcija brida
ako ne dozvolimo višestruke bridove u grafu
G1=Graph({1:[2,4],2:[3,5],3:[4],4:[5]})
pozicije1={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[1,1]}
pozicije2={1:[0,0],2:[2,0],3:[2,2],4:[0,2]}
G2=G1.copy()
G2.merge_vertices([1,5])
graphics_array([G1.plot(pos=pozicije1,graph_border=True),G2.plot(pos=pozicije2,graph_border=True)]).show(figsize=[6,4])
ako dozvolimo višestruke bridove u grafu
H1=Graph({1:[2,4],2:[3,5],3:[4],4:[5]})
pozicije1={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[1,1]}
pozicije2={1:[0.5,0.5],2:[2,0],3:[2,2],4:[0,2]}
H2=H1.copy()
H2.allow_multiple_edges(True)
H2.merge_vertices([1,5])
graphics_array([H1.plot(pos=pozicije1,graph_border=True),H2.plot(pos=pozicije2,graph_border=True)]).show(figsize=[6,4])
općenitije, možemo istovremeno i više vrhova poistovjetiti
T1=Graph({1:[2,4],2:[3,5],3:[4],4:[5]})
pozicije1={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[1,1]}
pozicije2={1:[1,1],2:[2,0],4:[0,2]}
T2=T1.copy()
T2.allow_multiple_edges(True)
T2.merge_vertices([1,3,5])
graphics_array([T1.plot(pos=pozicije1,graph_border=True),T2.plot(pos=pozicije2,graph_border=True)]).show(figsize=[6,4])
Razapinjuća stabla grafa
1. primjer
graf1=Graph({1:[2,4],2:[3,4],3:[4]})
poz1={1:[0,0],2:[1,0],3:[1,1],4:[0,1]}
graf1.show(pos=poz1,figsize=[3,3])
ukupni broj razapinjućih stabala grafa
graf1.spanning_trees_count()
neko razapinjuće stablo grafa
graf1.edge_disjoint_spanning_trees(1)
graf1.edge_disjoint_spanning_trees(1)[0].show(pos=poz1,figsize=[3,3])
promatrani graf nema barem dva bridovima disjunktna razapinjuća stabla
graf1.edge_disjoint_spanning_trees(2)
matrični teorem o stablima
graf1.kirchhoff_matrix()
svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu
graf1.kirchhoff_matrix().adjugate()
2. primjer
graf2=graphs.CompleteBipartiteGraph(2,3)
poz2={0:[0,1.5],1:[0,0.5],2:[2,2],3:[2,1],4:[2,0]}
graf2.show(pos=poz2,figsize=[3,3])
ukupni broj razapinjućih stabala grafa
graf2.spanning_trees_count()
neko razapinjuće stablo grafa
graf2.edge_disjoint_spanning_trees(1)
graf2.edge_disjoint_spanning_trees(1)[0].show(pos=poz2,figsize=[3,3])
promatrani graf nema barem dva bridovima disjunktna razapinjuća stabla
graf2.edge_disjoint_spanning_trees(2)
matrični teorem o stablima
graf2.kirchhoff_matrix()
svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu
graf2.kirchhoff_matrix().adjugate()
3. primjer
graf3=Graph({1:[2,4,5],2:[3,5],3:[4],4:[5]})
poz3={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[1,1]}
graf3.show(pos=poz3,figsize=[3,3])
ukupni broj razapinjućih stabala grafa
graf3.spanning_trees_count()
neko razapinjuće stablo grafa
graf3.edge_disjoint_spanning_trees(1)
graf3.edge_disjoint_spanning_trees(1)[0].show(pos=poz3,figsize=[3,3])
promatrani graf nema barem dva bridovima disjunktna razapinjuća stabla
graf3.edge_disjoint_spanning_trees(2)
matrični teorem o stablima
graf3.kirchhoff_matrix()
svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu
graf3.kirchhoff_matrix().adjugate()
4. primjer
graf4=Graph({1:[2,4],2:[3,5],3:[6],4:[5,7],5:[6,7],6:[7]})
poz4={1:[0,0],2:[1,0],3:[2,0],4:[0,1],5:[1,1],6:[2,1],7:[1,2]}
graf4.show(pos=poz4,figsize=[3,3])
ukupni broj razapinjućih stabala grafa
graf4.spanning_trees_count()
neko razapinjuće stablo grafa
graf4.edge_disjoint_spanning_trees(1)
graf4.edge_disjoint_spanning_trees(1)[0].show(pos=poz4,figsize=[3,3])
promatrani graf nema barem dva bridovima disjunktna razapinjuća stabla
graf4.edge_disjoint_spanning_trees(2)
matrični teorem o stablima
graf4.kirchhoff_matrix()
svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu
graf4.kirchhoff_matrix().adjugate()
5. primjer
graf5=Graph({1:[2,2,2,4,4,4],2:[3,3,3],3:[4,4,4],4:[5,5,5]})
poz5={1:[0,0],2:[2,0],3:[2,2],4:[0,2],5:[-2,2]}
graf5.show(pos=poz5,ymax=2.1,ymin=-0.1)
ukupni broj razapinjućih stabala grafa
graf5.spanning_trees_count()
neko razapinjuće stablo - ne radi baš dobro na grafovima koji nisu jednostavni
graf5.edge_disjoint_spanning_trees(1)[0]
matrični teorem o stablima
graf5.kirchhoff_matrix()
svi kofaktori gornje matrice su međusobno jednaki i jednaki su upravo broju razapinjućih stabala u grafu
graf5.kirchhoff_matrix().adjugate()
6. primjer
graphs.CompleteGraph(6).show(layout="circular",figsize=[3,3])
graphs.CompleteGraph(6).spanning_trees_count()
$K_6$ ima tri po bridovima disjunktna razapinjuća stabla
graphs.CompleteGraph(6).edge_disjoint_spanning_trees(3)
graphs_list.show_graphs(graphs.CompleteGraph(6).edge_disjoint_spanning_trees(3))
DFS i BFS algoritam
gr=Graph({1:[3,5],2:[5],3:[4,6],4:[5,7],5:[8],6:[7],7:[8]})
pozicije={1:[1,0],2:[2,0],3:[0,1],4:[1,1],5:[2,1],6:[0,2],7:[1,2],8:[2,2]}
gr.show(pos=pozicije,figsize=[3,3])
DFS algoritam daje redoslijed posjećivanja vrhova počevši s vrhom "1"
gr.depth_first_search(1)
list(gr.depth_first_search(1))
DFS algoritam daje redoslijed posjećivanja vrhova počevši s vrhom "4"
list(gr.depth_first_search(4))
Ako želimo dobiti i bridove koji se nalaze u DFS-stablu, implementirat ćemo svoju funkciju. Za svaki vrh $v$, $d[v]$ mjeri u kojem koraku je vrh $v$ prvi puta posjećen, a $f[v]$ mjeri u kojem koraku je završeno posjećivanje svih susjeda vrha $v$. Vrhove bojamo s tri boje: WHITE, GRAY i BLACK. Vrh $v$ je WHITE prije koraka $d[v]$, GRAY između koraka $d[v]$ i $f[v]$, a BLACK nakon koraka $d[v]$. Prethodnik vrha $v$ u DFS-stablu je vrh $P[v]$. Iako nama u ovom trenutku nisu možda potrebne sve navedene varijable, DFS algoritam je ipak implementiran u ovolikoj općenitosti jer je on osnova za neke druge algoritme u kojima spomenute varijable mogu biti od neizmjerne važnosti. Također, dolje je dana rekurzivna implementacija DFS algortima, a za vježbu možete pokušati implementirati nerekurzivnu verziju u kojoj ćete koristiti stog. Za detalje pogledajte knjigu Introduction to Algorithms od autora Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein.
def DFS(G,v0):
global time
V=G.vertices()
V.remove(v0)
vrhovi=[v0]+V
color={}
d={}
f={}
P={}
time=0
def DFS_posjet(u):
global time
color[u]="GRAY"
time=time+1
d[u]=time
for v in G[u]:
if color[v]=="WHITE":
P[v]=u
DFS_posjet(v)
color[u]="BLACK"
time=time+1
f[u]=time
for u in vrhovi:
color[u]="WHITE"
P[u]=None
for u in vrhovi:
if color[u]=="WHITE":
DFS_posjet(u)
redoslijed_vrhova=sorted(G.vertices(),key=lambda x: d[x])
bridovi=[]
for u in redoslijed_vrhova:
if P[u]!=None:
if (u,P[u]) in G.edges(labels=False):
bridovi.append((u,P[u]))
else:
bridovi.append((P[u],u))
return (redoslijed_vrhova,bridovi,d,f)
DFS(gr,1)
DFS(gr,4)
Sada možemo bez problema definirati i funkciju koja će pronađeno DFS-stablo istaknuti na grafu
def DFS_graf(G,v0,raspored_vrhova=None,lay="circular",bojaBridova="red",boja_v0="yellow"):
podaci=DFS(G,v0)
if raspored_vrhova==None:
slika=G.plot(edge_colors={bojaBridova:podaci[1]},vertex_colors={boja_v0:[podaci[0][0]]},layout=laj)
else:
slika=G.plot(edge_colors={bojaBridova:podaci[1]},vertex_colors={boja_v0:[podaci[0][0]]},pos=raspored_vrhova)
return slika
DFS_graf(gr,1,raspored_vrhova=pozicije,boja_v0="red").show(figsize=[3,3])
DFS_graf(gr,4,raspored_vrhova=pozicije).show(figsize=[3,3])
Animacija DFS-stabla s početkom u vrhu 4
Neposjećeni vrhovi su obojani crvenom bojom. Nakon što je vrh posjećen, obojan je sa žutom bojom, a nakon što je se iz njega ne može više dalje prema novim neposjećenim vrhovima, obojan je zelenom bojom. Bridovi koji se postupeno dodaju u DFS stablo, obojani su crvenom bojom.
rjecnik1=DFS(gr,4)[2]
rjecnik2=DFS(gr,4)[3]
bridovi=DFS(gr,4)[1]
algoritam=sorted(list(map(lambda x: (x[0],[x[1],'d']),map(lambda x: (x[1],x[0]), rjecnik1.items()))) + list(map(lambda x: (x[0],[x[1],'f']),
map(lambda x: (x[1],x[0]), rjecnik2.items()))))
def boja_vrha(korak):
lista=algoritam[0:korak]
boje={"yellow":[],"green":[]}
for x in lista:
if x[1][1]=='d':
boje["yellow"].append(x[1][0])
else:
boje["yellow"].remove(x[1][0])
boje["green"].append(x[1][0])
return boje
def boja_brida(korak):
if korak==1: return {}
if korak>=11: return {"red":bridovi}
if (korak>1) and (korak<6):
return {"red":bridovi[0:korak-1]}
if (korak==6):
return {"red":bridovi[0:4]}
if (korak>=7) or (korak<=9):
return {"red":bridovi[0:korak-2]}
if (korak==10):
return {"red":bridovi[0:-1]}
aDSF=animate([gr.plot(edge_colors=boja_brida(k),vertex_colors=boja_vrha(k),pos=pozicije,graph_border=True,
figsize=[3,3]) for k in srange(1,len(algoritam)+1,1)])
aDSF.show(delay=150,iterations=0)
interaktivno proučavanje pojedinog koraka DFS algoritma
rjecnik1=DFS(gr,4)[2]
rjecnik2=DFS(gr,4)[3]
bridovi=DFS(gr,4)[1]
algoritam=sorted(list(map(lambda x: (x[0],[x[1],'d']),map(lambda x: (x[1],x[0]), rjecnik1.items()))) + list(map(lambda x: (x[0],[x[1],'f']),
map(lambda x: (x[1],x[0]), rjecnik2.items()))))
def boja_vrha(korak):
lista=algoritam[0:korak]
boje={"yellow":[],"green":[]}
for x in lista:
if x[1][1]=='d':
boje["yellow"].append(x[1][0])
else:
boje["yellow"].remove(x[1][0])
boje["green"].append(x[1][0])
return boje
def boja_brida(korak):
if korak==1: return {}
if korak>=11: return {"red":bridovi}
if (korak>1) and (korak<8):
return {"red":bridovi[0:korak-1]}
if (korak>=8) and (korak<11):
return {"red":bridovi[0:-1]}
d=len(algoritam)
@interact
def _(k=selector([1..d],nrows=1)):
gr.plot(edge_colors=boja_brida(k),vertex_colors=boja_vrha(k),pos=pozicije,graph_border=True).show(figsize=[4,4])
BFS algoritam daje redoslijed posjećivanja vrhova počevši od vrha "1"
gr.breadth_first_search(1)
list(gr.breadth_first_search(1))
BFS algoritam daje redoslijed posjećivanja vrhova počevši od vrha "4"
list(gr.breadth_first_search(4))
Ako želimo dobiti i bridove koji se nalaze u BFS-stablu, implementirat ćemo svoju funkciju. Za svaki vrh $v$, $d[v]$ mjeri udaljenost vrha $v$ od početnog vrha $v_0$ s kojim algoritam započinje. Vrhove bojamo s tri boje: WHITE, GRAY i BLACK. Neposjećeni vrhovi su obojani bojom WHITE, posjećeni vrhovi bojom GRAY, a ukoliko su posjećenom vrhu posjećeni i svi njegovi susjedi, tada je on obojan bojom BLACK. Prethodnik vrha $v$ u BFS-stablu je vrh $P[v]$. Za detalje pogledajte knjigu Introduction to Algorithms od autora Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein.
def BFS(G,v0):
V=G.vertices()
V.remove(v0)
color={}
P={}
d={}
for u in V:
color[u]="WHITE"
d[u]=Infinity
P[u]=None
color[v0]="GRAY"
d[v0]=0
P[v0]=None
Q=[]
Q.append(v0)
redoslijed_vrhova=[v0]
while Q!=[]:
u=Q.pop(0)
for v in G[u]:
if color[v]=="WHITE":
color[v]="GRAY"
d[v]=d[u]+1
P[v]=u
Q.append(v)
redoslijed_vrhova.append(v)
color[u]="BLACK"
bridovi=[]
for u in redoslijed_vrhova:
if P[u]!=None:
if (u,P[u]) in G.edges(labels=False):
bridovi.append((u,P[u]))
else:
bridovi.append((P[u],u))
return (redoslijed_vrhova,bridovi,d)
BFS(gr,1)
BFS(gr,4)
Sada možemo bez problema definirati i funkciju koja će pronađeno BFS-stablo istaknuti na grafu
def BFS_graf(G,v0,raspored_vrhova=None,lay="circular",bojaBridova="red",boja_v0="yellow"):
podaci=BFS(G,v0)
if raspored_vrhova==None:
slika=G.plot(edge_colors={bojaBridova:podaci[1]},vertex_colors={boja_v0:[podaci[0][0]]},layout=laj)
else:
slika=G.plot(edge_colors={bojaBridova:podaci[1]},vertex_colors={boja_v0:[podaci[0][0]]},pos=raspored_vrhova)
return slika
BFS_graf(gr,1,raspored_vrhova=pozicije).show(figsize=[3,3])
BFS_graf(gr,4,raspored_vrhova=pozicije).show(figsize=[3,3])
Animacija BFS-stabla s početkom u vrhu 4
alg=BFS(gr,4)
aBFS=animate([gr.plot(pos=pozicije,graph_border=True,figsize=[3,3],edge_colors={"red":alg[1][0:k-1]},
vertex_colors={"yellow":alg[0][0:k]}) for k in srange(1,len(alg[0])+1,1)])
aBFS.show(delay=150,iterations=0)
interaktivno proučavanje pojedinog koraka u BFS algoritmu
alg=BFS(gr,4)
@interact
def _(korak=selector([1..len(alg[0])],nrows=1)):
gr.plot(pos=pozicije,graph_border=True,edge_colors={"red":alg[1][0:korak-1]},
vertex_colors={"yellow":alg[0][0:korak]}).show(figsize=[4,4])
