U ovom dijelu ćemo proći kroz neke naredbe koje ispituju razna svojstva grafa. Paralelno ćemo koristiti uz SAGE naredbe i networkx modul.
import sage.misc.banner
banner()
from IPython.core.display import Image
G1=Graph({1:[2,3,4],2:[4,5],3:[4,5,6],4:[5],5:[6]})
G2=Graph({1:[2,3],2:[3],3:[4],4:[5,5],5:[6]})
G3=Graph({1:[2,6],2:[3,7,8],3:[4],4:[5],5:[6,7,8]})
Tri grafa na kojima ćemo vršiti ispitivanja
G1.plot(pos={1:[0,2],2:[0,0],3:[2,2],4:[1,1],5:[2,0],6:[3,1]},graph_border=True,figsize=[5,4])
G2.plot(pos={1:[0,0],2:[2,0],3:[1,1.5],4:[3,3],5:[4,1.5],6:[5.5,1]},graph_border=True,figsize=[5,4])
G3.plot(pos={1:[0,2],2:[1,2],3:[2,2],4:[2,0],5:[1,0],6:[0,0],7:[-1,1],8:[3,1]},graph_border=True,figsize=[5,4])
Kako bismo te grafove mogli kreirati s networkx modulom
import networkx as nx
from pylab import *
Tri načina spremanja grafova u datoteku. Klikom na linkove ih možemo spremiti na disk, a kasnije opet te datoteke uploadati u SAGE i normalno ih koristiti.
P=nx.petersen_graph()
nx.write_adjlist(P,"petersen.adjlist")
nx.write_edgelist(P,"petersen.edgelist")
nx.write_multiline_adjlist(P,"petersen.multiadjlist")
Učitavanje grafa iz vanjske datoteke
G1nx=nx.read_adjlist("graf1_adjlist.sage",nodetype=int)
G1nx.nodes()
G1nx.edges()
dat1=open("graf1_adjlist.sage",'r')
podaci1=dat1.read()
dat1.close()
podaci1
print(podaci1)
figure(figsize=(4,4))
nx.draw(G1nx,pos={1:[0,2],2:[0,0],3:[2,2],4:[1,1],5:[2,0],6:[3,1]},with_labels=True,node_color='y')
G2nx=nx.read_adjlist("graf2_adjlist.sage",create_using=nx.MultiGraph(),nodetype=int)
G2nx.nodes()
G2nx.edges()
dat2=open("graf2_adjlist.sage",'r')
podaci2=dat2.read()
dat2.close()
podaci2
print(podaci2)
G2sage=Graph(Matrix(nx.to_numpy_matrix(G2nx,dtype=int)))
s2=G2sage.graphviz_string()
os.system("echo '%s' | dot -Kcirco -Tpng > graf2.png" % s2)
Image(filename="graf2.png")
G3nx=nx.read_adjlist("graf3_adjlist.sage",nodetype=int)
G3nx.nodes()
G3nx.edges()
dat3=open("graf3_adjlist.sage",'r')
podaci3=dat3.read()
dat3.close()
podaci3
print(podaci3)
figure(figsize=(4,3))
nx.draw(G3nx,pos={1:[0,2],2:[1,2],3:[2,2],4:[2,0],5:[1,0],6:[0,0],7:[-1,1],8:[3,1]},with_labels=True,node_color='y')
Promatrani grafovi nisu prazni jer svaki od njih ima barem jedan brid
G1.num_edges(),G2.num_edges(),G3.num_edges()
G1nx.number_of_edges(),G2nx.number_of_edges(),G3nx.number_of_edges()
možemo definirati svoju funkciju koja će vraćati True ako je graf prazan, a u protivnom False.
def is_empty(G):
if type(G)==sage.graphs.graph.Graph:
if G.num_edges()==0:
return True
else:
return False
else:
if G.number_of_edges()==0:
return True
else:
return False
is_empty(G1),is_empty(G2),is_empty(G3)
is_empty(G1nx),is_empty(G2nx),is_empty(G3nx)
is_empty(Graph(5)),is_empty(nx.empty_graph(5))
Promatrani grafovi nemaju petlji
G1.number_of_loops(),G2.number_of_loops(),G3.number_of_loops()
nx.number_of_selfloops(G1nx),nx.number_of_selfloops(G2nx),nx.number_of_selfloops(G3nx)
G1.has_loops(),G2.has_loops(),G3.has_loops()
list(nx.selfloop_edges(G1nx)), list(nx.selfloop_edges(G2nx)), list(nx.selfloop_edges(G3nx))
G1.has_multiple_edges(),G2.has_multiple_edges(),G3.has_multiple_edges()
G1nx.is_multigraph(),G2nx.is_multigraph(),G3nx.is_multigraph()
G1.is_directed(),G2.is_directed(),G3.is_directed()
G1nx.is_directed(),G2nx.is_directed(),G3nx.is_directed()
promatrani grafovi nisu bipartitni
G1.is_bipartite(),G2.is_bipartite(),G3.is_bipartite()
nx.is_bipartite(G1nx),nx.is_bipartite(G2nx),nx.is_bipartite(G3nx)
Kubni graf jest bipartitni
graphs.CubeGraph(3).is_bipartite()
nx.is_bipartite(nx.cubical_graph())
biparticija kubnog grafa
Graph.bipartite_sets(graphs.CubeGraph(3))
nx.bipartite.sets(nx.cubical_graph())
G1.is_connected(),G2.is_connected(),G3.is_connected()
nx.is_connected(G1nx),nx.is_connected(G2nx),nx.is_connected(G3nx)
G1.connected_components_number(),G2.connected_components_number(),G3.connected_components_number()
nx.number_connected_components(G1nx),nx.number_connected_components(G2nx),nx.number_connected_components(G3nx)
G=graphs.CompleteGraph(5)
H=graphs.CompleteBipartiteGraph(3,2)
U=G.disjoint_union(H)
Gnx=nx.complete_graph(5)
Hnx=nx.complete_bipartite_graph(3,2)
Unx=nx.disjoint_union(Gnx,Hnx)
U.connected_components_number()
nx.number_connected_components(Unx)
U.plot(graph_border=True,vertex_size=700,layout="spring")
komponente povezanosti
U.connected_components()
komponenta povezanosti koja sadrži vrh (1,1)
U.connected_component_containing_vertex((1,1))
komponente povezanosti kao podgrafovi
komp=U.connected_components_subgraphs()
komp
graphs_list.show_graphs(komp)
figure(figsize=(4,4))
nx.draw_circular(Unx,with_labels=True,node_color='y')
komponente povezanosti
list(nx.connected_components(Unx))
komponente povezanosti kao podgrafovi
komp_Unx=[]
for c in nx.connected_components(Unx):
komp_Unx.append(Unx.subgraph(c).copy())
komp_Unx
figure(figsize=(3,3))
nx.draw_circular(komp_Unx[0],with_labels=True,node_color='y')
figure(figsize=(3,3))
nx.draw_circular(komp_Unx[1],with_labels=True,node_color='y')
def is_simple(G):
if type(G)==sage.graphs.graph.Graph:
if G.number_of_loops()>0:
return False
if len(set(G.edges(labels=False)))!=G.num_edges():
return False
else:
return True
else:
if nx.number_of_selfloops(G)>0:
return False
if len(set(G.edges()))!=G.number_of_edges():
return False
else:
return True
is_simple(G1),is_simple(G2),is_simple(G3)
is_simple(G1nx),is_simple(G2nx),is_simple(G3nx)
def is_complete(G):
if type(G)==sage.graphs.graph.Graph:
if G.number_of_loops()>0:
return False
if len(set(G.edges(labels=False)))!=G.num_edges():
return False
if G.num_edges()!=(G.num_verts()^2-G.num_verts())/2:
return False
else:
return True
else:
if nx.number_of_selfloops(G)>0:
return False
if len(set(G.edges()))!=G.number_of_edges():
return False
if G.number_of_edges()!=(G.number_of_nodes()^2-G.number_of_nodes())/2:
return False
else:
return True
is_complete(G1),is_complete(G2),is_complete(G3)
is_complete(G1nx),is_complete(G2nx),is_complete(G3nx)
is_complete(graphs.CompleteGraph(8))
is_complete(nx.complete_graph(8))
G1.is_regular(),G2.is_regular(),G3.is_regular()
def regularan(Gnx):
if len(set(dict(Gnx.degree()).values()))==1:
return (True,list(dict(Gnx.degree()).values())[0])
else:
return False
regularan(G1nx),regularan(G2nx),regularan(G3nx)
graphs.PetersenGraph().is_regular()
regularan(nx.petersen_graph())
graphs.CompleteGraph(8).is_regular()
regularan(nx.complete_graph(8))
def is_acyclic(G):
if type(G)==sage.graphs.graph.Graph:
if G.num_edges()==G.num_verts()-G.connected_components_number():
return True
else:
return False
else:
if G.number_of_edges()==G.number_of_nodes()-nx.number_connected_components(G):
return True
else:
return False
is_acyclic(G1),is_acyclic(G2),is_acyclic(G3)
is_acyclic(G1nx),is_acyclic(G2nx),is_acyclic(G3nx)
is_acyclic(graphs.PathGraph(8))
is_acyclic(nx.path_graph(8))
G1.is_tree(),G2.is_tree(),G3.is_tree()
graphs.PathGraph(8).is_tree()
def TreeQ(G):
if nx.number_connected_components(G)==1 and G.number_of_edges()==G.number_of_nodes()-1:
return True
else:
return False
TreeQ(G1nx),TreeQ(G2nx),TreeQ(G3nx)
TreeQ(nx.path_graph(8))
G1.is_planar(),G2.is_planar(),G3.is_planar()
graphs.CompleteGraph(5).is_planar()
graphs.CompleteBipartiteGraph(3,3).is_planar()
G1.is_eulerian(),G2.is_eulerian(),G3.is_eulerian()
G1e=Graph(G1,multiedges=True)
G1e.add_edge((1,2))
G1e.plot(pos={1:[0,2],2:[0,0],3:[2,2],4:[1,1],5:[2,0],6:[3,1]},graph_border=True,figsize=[5,4])
G1e.is_eulerian()
def EulerianQ(Gnx):
if sum(map(lambda x: x%2,dict(Gnx.degree()).values()))==0 and nx.number_connected_components(Gnx)==1:
return True
else:
return False
EulerianQ(G1nx),EulerianQ(G2nx),EulerianQ(G3nx)
EulerianQ(G1e.networkx_graph())
G1.is_hamiltonian(),G3.is_hamiltonian()
G2.is_hamiltonian()
G1.neighbors(2)
G1[2]
[v for v in G1.neighbor_iterator(2)]
list(G1nx.neighbors(2))
G1nx[2]
[v for v in G1nx.neighbors(2)]
G2.distance(3,1)
G2.distance(2,5)
G2.shortest_path_length(2,5)
nx.shortest_path_length(G2nx,3,1)
nx.shortest_path_length(G2nx,2,5)
G2.shortest_path(3,1)
G2.shortest_path(2,5)
G3.shortest_path(1,7)
nx.shortest_path(G2nx,3,1)
nx.shortest_path(G2nx,2,5)
nx.shortest_path(G3nx,1,7)
G2.shortest_path_lengths(2)
G2.shortest_path_lengths(4)
G3.shortest_path_lengths(1)
nx.shortest_path_length(G2nx,2)
nx.shortest_path_length(G2nx,4)
nx.shortest_path_length(G3nx,1)
G2.shortest_paths(2)
G2.shortest_paths(4)
G3.shortest_paths(1)
nx.shortest_path(G2nx,2)
nx.shortest_path(G2nx,4)
nx.shortest_path(G3nx,1)
nx.single_source_shortest_path(G2nx,4)
G1.distance_all_pairs()
G2.distance_all_pairs()
G3.distance_all_pairs()
dict(nx.shortest_path_length(G1nx))
dict(nx.shortest_path_length(G2nx))
dict(nx.shortest_path_length(G3nx))
G1.shortest_path_all_pairs()
udaljenosti
G1.shortest_path_all_pairs()[0]
prethodnici pojedinog vrha na najkraćem putu između dva vrha
G1.shortest_path_all_pairs()[1]
nx.shortest_path(G1nx)
G2.shortest_path_all_pairs()[1]
nx.shortest_path(G2nx)
G3.shortest_path_all_pairs()[1]
nx.shortest_path(G3nx)
G1.eccentricity()
G1.eccentricity(with_labels=True)
G1.eccentricity([2,3,6],with_labels=True)
G1.eccentricity(5)
G2.eccentricity()
G2.eccentricity(with_labels=True)
G3.eccentricity()
G3.eccentricity(with_labels=True)
nx.eccentricity(G1nx)
nx.eccentricity(G2nx)
nx.eccentricity(G2nx,4)
nx.eccentricity(G3nx)
G1.radius()
G2.radius()
G3.radius()
nx.radius(G1nx)
nx.radius(G2nx)
nx.radius(G3nx)
G1.diameter()
G2.diameter()
G3.diameter()
nx.diameter(G1nx)
nx.diameter(G2nx)
nx.diameter(G3nx)
G1.girth()
G2.girth()
G3.girth()
list(G1.bridges())
list(G2.bridges())
list(G3.bridges())
G1.edge_connectivity()
G1.edge_connectivity(value_only=False)
G1.edge_connectivity(value_only=False,vertices=True)
G2.allow_multiple_edges(False)
G2.edge_connectivity(value_only=False,implementation="boost")
G3.edge_connectivity(value_only=False)
G1.edge_cut(1,3,value_only=False,vertices=True)
G2.edge_cut(2,3,value_only=False,vertices=True)
G2.edge_cut(1,2,value_only=False)
G3.edge_cut(1,5,value_only=False,vertices=True)
G1.blocks_and_cut_vertices()[1]
G2.blocks_and_cut_vertices()[1]
G3.blocks_and_cut_vertices()[1]
G1.blocks_and_cut_vertices()[0]
G2.blocks_and_cut_vertices()[0]
G3.blocks_and_cut_vertices()[0]
G1.vertex_connectivity()
G1.vertex_connectivity(value_only=False)
G1.vertex_connectivity(value_only=False,sets=True)
G2.vertex_connectivity()
G2.vertex_connectivity(value_only=False,sets=True)
G3.vertex_connectivity(value_only=False,sets=True)
G1.vertex_cut(1,4)
G1.vertex_cut(1,5)
G1.vertex_cut(1,5,value_only=False,vertices=True)
G2.vertex_cut(2,4,value_only=False,vertices=True)
G3.vertex_cut(1,3,value_only=False,vertices=True)
G1.hamiltonian_cycle()
G1.hamiltonian_cycle().show()
želimo li istaknuti Hamiltonov ciklus na zadanom grafu, možemo definirati svoju funkciju koja će to raditi
def hamiltonov_ciklus(G,pozicije_vrhova=None,laj="spring",boja="red"):
if not(G.is_hamiltonian()):
return "Error: Graf nije Hamiltonov"
bridovi=G.hamiltonian_cycle().edges(labels=False)
if pozicije_vrhova==None:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},layout=laj)
else:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},pos=pozicije_vrhova)
return slika
hamiltonov_ciklus(G1,pozicije_vrhova={1:[0,2],2:[0,0],3:[2,2],4:[1,1],5:[2,0],6:[3,1]}).show(figsize=[5,4])
G2.hamiltonian_cycle()
hamiltonov_ciklus(G2)
hamiltonov_ciklus(G3)
G3.eulerian_circuit(labels=False)
G3.eulerian_circuit(labels=False,return_vertices=True)
G3.eulerian_circuit(labels=False,return_vertices=True)[1]
Animacija Eulerove ture
bridovi=G3.eulerian_circuit(labels=False)
animacija=animate([G3.plot(pos={1:[0,2],2:[1,2],3:[2,2],4:[2,0],5:[1,0],6:[0,0],7:[-1,1],8:[3,1]},
graph_border=True,edge_colors={"red":bridovi[0:k]}) for k in srange(0,len(bridovi)+1,1)])
show(animacija.show(delay=150,iterations=0))
Interakcija korak po korak Eulerove ture
bridovi=G3.eulerian_circuit(labels=False)
d=len(bridovi)
@interact
def _(tura=selector([0..d],nrows=1)):
G3.plot(pos={1:[0,2],2:[1,2],3:[2,2],4:[2,0],5:[1,0],6:[0,0],7:[-1,1],8:[3,1]},
graph_border=True,edge_colors={"red":bridovi[0:tura]}).show(figsize=[5,4])
U zadanom grafu pronađite
graf1=Graph({'a':['a','b','d'],'b':['c','d','d'],'c':['d']})
a) dio - donja naredba daje sve putove na pripadnom jednostavnom grafu
graf1.all_paths('b','d')
b) dio - donja naredba daje sve putove na pripadnom jednostavnom grafu
graf1.all_paths('b','c')
c) dio
graf1.vertices()
mat1=graf1.adjacency_matrix();mat1
mat1^3
raspored vrhova u matrici susjedstva je onakav kakav je i u listi graf1.vertices() pa tražimo element na poziciji (1,2) (pazite: indeksiranje počinje s brojem nula)
(mat1^3)[1,2]
(mat1^3)[graf1.vertices().index('b'),graf1.vertices().index('c')]
d) dio
sum(sum(mat1^3))
Zadana je matrica susjedstva $A=\begin{bmatrix}1&2&1&0\\ 2&0&1&0\\ 1&1&0&0\\ 0&0&0&0\end{bmatrix}$ grafa čiji su vrhovi redom $v_1,v_2,v_3,v_4$.
graf2=Graph({'v1':['v1','v2','v2','v3'],'v2':['v3'],'v4':[]})
graf2.vertices(),graf2.edges(labels=False)
a) dio
graf2.has_loops()
graf2.loop_edges()
is_simple(graf2)
graf2.multiple_edges(labels=False)
b) dio - vrh $v_4$ je izolirani vrh
for vrh in graf2.vertices():
if graf2.degree(vrh)==0:
print(vrh,)
c) dio
graf2.degree(labels=True)
d) dio
graf2.plot(graph_border=True,figsize=[5,4])
e) dio
mat2=graf2.adjacency_matrix();mat2
broj $(v_1,v_2)$-šetnji duljine 2
(mat2^2)[0,1]
broj $(v_1,v_4)$-šetnji duljine 2
(mat2^2)[0,3]
broj $(v_1,v_2)$-šetnji duljine 3
(mat2^3)[0,1]
broj $(v_1,v_4)$-šetnji duljine 3
(mat2^3)[0,3]
graf3=Graph({'A':['B','C','E'],'B':['C','D','E'],'C':['D','E']})
graf3.plot(graph_border=True,pos={'A':[0,0.7],'B':[-1,0],'C':[1,0],'D':[0,-1],'E':[0,2]},figsize=[4,5])
Zadani graf jest Hamiltonov
graf3.hamiltonian_cycle().plot(layout="circular",figsize=[5,4])
hamiltonov_ciklus(graf3,pozicije_vrhova={'A':[0,0.7],'B':[-1,0],'C':[1,0],'D':[0,-1],'E':[0,2]}).show(figsize=[4,5])
Zadani graf ima Hamiltonov put
Funkcija hamiltonov_put daje bridove nekog Hamiltonovog puta u grafu ukoliko on postoji.
def hamiltonov_put(G):
try:
H=G.copy()
H.add_edges(zip(G.vertices(),['vrh']*G.num_verts()))
ciklus=H.hamiltonian_cycle()
ciklus.delete_vertex('vrh')
return ciklus.edges(labels=False)
except ValueError:
return "Error: Graf nema Hamiltonov put"
hamiltonov_put(graf3)
Funkcija hamiltonov_put_graf ističe neki Hamiltonov put na zadanom grafu ukoliko on postoji.
def hamiltonov_put_graf(G,pozicije_vrhova=None,laj="spring",boja="red"):
try:
H=G.copy()
H.add_edges(zip(G.vertices(),['vrh']*G.num_verts()))
ciklus=H.hamiltonian_cycle()
ciklus.delete_vertex('vrh')
bridovi=ciklus.edges(labels=False)
if pozicije_vrhova==None:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},layout=laj)
else:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},pos=pozicije_vrhova)
return slika
except ValueError:
return "Error: Graf nema Hamiltonov put"
hamiltonov_put_graf(graf3,pozicije_vrhova={'A':[0,0.7],'B':[-1,0],'C':[1,0],'D':[0,-1],'E':[0,2]}).show(figsize=[4,5])
Zadani graf nije Eulerov, ali ima Eulerovu stazu zbog toga što je povezan i ima točno dva vrha neparnog stupnja
graf3.is_eulerian()
graf3.degree()
def is_rezni(G,brid):
graf=G.copy()
graf.delete_edge(brid)
if graf.connected_components_number()>G.connected_components_number():
return True
else:
return False
def eulerova_staza(G,izlaz="vrhovi"):
if G.is_eulerian():
return "Graf G ima Eulerovu turu"
neparni_vrhovi=list(filter(lambda vrh: is_odd(G.degree(vrh)), G.vertices()))
if len(neparni_vrhovi)>2:
return "Graf nema Eulerovu stazu"
H=G.copy()
staza=[neparni_vrhovi[0]]
while H.num_edges()!=0:
v=staza[-1]
susjedi=H[v]
if len(susjedi)==1:
staza.append(susjedi[0])
if (v,staza[-1]) in H.edges(labels=False):
H.delete_edge((v,staza[-1]))
else:
H.delete_edge((staza[-1],v))
else:
for vrh in susjedi:
if (v,vrh) in H.edges(labels=False):
brid=(v,vrh)
else:
brid=(vrh,v)
if not(is_rezni(H,brid)):
staza.append(vrh)
H.delete_edge(brid)
break
if izlaz=="vrhovi":
return staza
elif izlaz=="bridovi":
staza2=[]
for k in range(len(staza)-1):
if (staza[k],staza[k+1]) in G.edges(labels=False):
staza2.append((staza[k],staza[k+1]))
else:
staza2.append((staza[k+1],staza[k]))
return staza2
eulerova_staza(graf3)
eulerova_staza(graf3,izlaz="bridovi")
bridovi2=eulerova_staza(graf3,izlaz="bridovi")
d2=len(bridovi2)
@interact
def _(staza=selector([0..d2],nrows=1)):
graf3.plot(pos={'A':[0,0.7],'B':[-1,0],'C':[1,0],'D':[0,-1],'E':[0,2]},graph_border=True,
edge_colors={"red":bridovi2[0:staza]}).show(figsize=[5,4])
Može li skakač na šahovskoj ploči $n\times n,\ n\geqslant3$, krenuti iz nekog mjestai posjetiti svako polje točno jednom i vratiti se natrag na mjesto otkud je počeo? Skakač se kreće u obliku slova $L$, tj. .
def konjic_skok(m,n):
return Graph([list(map(lambda x:tuple(x), cartesian_product((range(1,m+1),range(1,n+1))).list())),
lambda i,j: (abs(i[0]-j[0])==1 and abs(i[1]-j[1])==2) or (abs(i[0]-j[0])==2 and abs(i[1]-j[1])==1)])
def pozicije_konjic(m,n):
pozicije={}
for i in range(1,m+1):
for j in range(1,n+1):
pozicije[(i,j)]=(j,i)
return pozicije
Na $3\times3$ ploči to nije moguće
konjic_skok(3,3).plot(pos=pozicije_konjic(3,3),graph_border=True,vertex_size=700,figsize=[4,4])
konjic_skok(3,3).is_hamiltonian()
Na $8\times8$ ploči to je moguće
konjic_skok(8,8).is_hamiltonian()
konjic_skok(8,8).plot(pos=pozicije_konjic(8,8),graph_border=True,vertex_labels=False,vertex_size=100,figsize=[5,5])
animacija konjićeve ture na $8\times8$ ploči
Kako bi se lakše pratila animacija, uvodimo sljedeće bojanje polja:
def bojanje(korak):
if korak==1:
return {"yellow":[redoslijed_vrhova[0]]}
if korak==2:
return {"cyan":[redoslijed_vrhova[0]],"#00FF00":[redoslijed_vrhova[1]]}
if korak>=3:
return {"yellow":redoslijed_vrhova[0:korak-2],"cyan":[redoslijed_vrhova[korak-2]],"#00FF00":[redoslijed_vrhova[korak-1]]}
ploca88=konjic_skok(8,8).hamiltonian_cycle()
redoslijed_vrhova=[(1,1)]
while len(redoslijed_vrhova)<64:
susjedi=ploca88.neighbors(redoslijed_vrhova[-1])
if susjedi[1] in redoslijed_vrhova:
redoslijed_vrhova.append(susjedi[0])
else:
redoslijed_vrhova.append(susjedi[1])
aa=animate([konjic_skok(8,8).plot(pos=pozicije_konjic(8,8),graph_border=True,vertex_labels=False,vertex_shape='s',
vertex_size=1500,edge_colors={"white":konjic_skok(8,8).edges()},
vertex_colors=bojanje(k)) for k in srange(1,65,1)],figsize=[6,6])
aa.show(delay=150,iterations=0)
Ili ako vam je draže interaktivno proučavati svaki korak
konjic88=konjic_skok(8,8)
ploca88=konjic_skok(8,8).hamiltonian_cycle()
redoslijed_vrhova=[(1,1)]
while len(redoslijed_vrhova)<64:
susjedi=ploca88.neighbors(redoslijed_vrhova[-1])
if susjedi[1] in redoslijed_vrhova:
redoslijed_vrhova.append(susjedi[0])
else:
redoslijed_vrhova.append(susjedi[1])
d3=len(redoslijed_vrhova)
@interact
def _(korak=selector([1..d3],nrows=1)):
konjic_skok(8,8).plot(pos=pozicije_konjic(8,8),graph_border=True,vertex_labels=False,vertex_shape='s',vertex_size=1500,
edge_colors={"white":konjic_skok(8,8).edges()},vertex_colors=bojanje(korak)).show(figsize=[7,6])