Svojstva grafova u SAGE-u

U ovom dijelu ćemo proći kroz neke naredbe koje ispituju razna svojstva grafa. Paralelno ćemo koristiti uz SAGE naredbe i networkx modul.

In [1]:
import sage.misc.banner
banner()

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.2, Release Date: 2020-10-24                     │
│ Using Python 3.8.6. Type "help()" for help.                        │
└────────────────────────────────────────────────────────────────────┘
In [2]:
from IPython.core.display import Image
In [3]:
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

In [4]:
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])
Out[4]:
In [5]:
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])
Out[5]:
In [6]:
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])
Out[6]:

Kako bismo te grafove mogli kreirati s networkx modulom

In [7]:
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.

In [8]:
P=nx.petersen_graph()
In [9]:
nx.write_adjlist(P,"petersen.adjlist")
In [10]:
nx.write_edgelist(P,"petersen.edgelist")
In [11]:
nx.write_multiline_adjlist(P,"petersen.multiadjlist")

Učitavanje grafa iz vanjske datoteke

In [12]:
G1nx=nx.read_adjlist("graf1_adjlist.sage",nodetype=int)
In [13]:
G1nx.nodes()
Out[13]:
NodeView((1, 2, 3, 4, 5, 6))
In [14]:
G1nx.edges()
Out[14]:
EdgeView([(1, 2), (1, 3), (1, 4), (2, 4), (2, 5), (3, 4), (3, 5), (3, 6), (4, 5), (5, 6)])
In [15]:
dat1=open("graf1_adjlist.sage",'r')
podaci1=dat1.read()
dat1.close()
In [16]:
podaci1
Out[16]:
'#graf1\n1 2 3 4\n2 4 5\n3 4 5 6\n4 5\n5 6\n6'
In [17]:
print(podaci1)

#graf1
1 2 3 4
2 4 5
3 4 5 6
4 5
5 6
6
In [18]:
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')
In [19]:
G2nx=nx.read_adjlist("graf2_adjlist.sage",create_using=nx.MultiGraph(),nodetype=int)
In [20]:
G2nx.nodes()
Out[20]:
NodeView((1, 2, 3, 4, 5, 6))
In [21]:
G2nx.edges()
Out[21]:
MultiEdgeDataView([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 5), (5, 6)])
In [22]:
dat2=open("graf2_adjlist.sage",'r')
podaci2=dat2.read()
dat2.close()
In [23]:
podaci2
Out[23]:
'#graf2\n1 2 3\n2 3\n3 4\n4 5 5\n5 6\n6'
In [24]:
print(podaci2)

#graf2
1 2 3
2 3
3 4
4 5 5
5 6
6
In [25]:
G2sage=Graph(Matrix(nx.to_numpy_matrix(G2nx,dtype=int)))
s2=G2sage.graphviz_string()
os.system("echo '%s' | dot -Kcirco -Tpng > graf2.png" % s2)
Out[25]:
0
In [26]:
Image(filename="graf2.png")
Out[26]:
In [27]:
G3nx=nx.read_adjlist("graf3_adjlist.sage",nodetype=int)
In [28]:
G3nx.nodes()
Out[28]:
NodeView((1, 2, 6, 3, 7, 8, 4, 5))
In [29]:
G3nx.edges()
Out[29]:
EdgeView([(1, 2), (1, 6), (2, 3), (2, 7), (2, 8), (6, 5), (3, 4), (7, 5), (8, 5), (4, 5)])
In [30]:
dat3=open("graf3_adjlist.sage",'r')
podaci3=dat3.read()
dat3.close()
In [31]:
podaci3
Out[31]:
'#graf3\n1 2 6\n2 3 7 8\n3 4\n4 5\n5 6 7 8\n6\n7\n8'
In [32]:
print(podaci3)

#graf3
1 2 6
2 3 7 8
3 4
4 5
5 6 7 8
6
7
8
In [33]:
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')

Svojstva grafova

Je li graf prazan?

Promatrani grafovi nisu prazni jer svaki od njih ima barem jedan brid

In [34]:
G1.num_edges(),G2.num_edges(),G3.num_edges()
Out[34]:
(10, 7, 10)
In [35]:
G1nx.number_of_edges(),G2nx.number_of_edges(),G3nx.number_of_edges()
Out[35]:
(10, 7, 10)

možemo definirati svoju funkciju koja će vraćati True ako je graf prazan, a u protivnom False.

In [36]:
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
In [37]:
is_empty(G1),is_empty(G2),is_empty(G3)
Out[37]:
(False, False, False)
In [38]:
is_empty(G1nx),is_empty(G2nx),is_empty(G3nx)
Out[38]:
(False, False, False)
In [39]:
is_empty(Graph(5)),is_empty(nx.empty_graph(5))
Out[39]:
(True, True)

Broj petlji u grafu

Promatrani grafovi nemaju petlji

In [40]:
G1.number_of_loops(),G2.number_of_loops(),G3.number_of_loops()
Out[40]:
(0, 0, 0)
In [41]:
nx.number_of_selfloops(G1nx),nx.number_of_selfloops(G2nx),nx.number_of_selfloops(G3nx)
Out[41]:
(0, 0, 0)
In [42]:
G1.has_loops(),G2.has_loops(),G3.has_loops()
Out[42]:
(False, False, False)
In [43]:
list(nx.selfloop_edges(G1nx)), list(nx.selfloop_edges(G2nx)), list(nx.selfloop_edges(G3nx))
Out[43]:
([], [], [])

Ima li graf višestrukih bridova

In [44]:
G1.has_multiple_edges(),G2.has_multiple_edges(),G3.has_multiple_edges()
Out[44]:
(False, True, False)
In [45]:
G1nx.is_multigraph(),G2nx.is_multigraph(),G3nx.is_multigraph()
Out[45]:
(False, True, False)

Je li graf usmjeren

In [46]:
G1.is_directed(),G2.is_directed(),G3.is_directed()
Out[46]:
(False, False, False)
In [47]:
G1nx.is_directed(),G2nx.is_directed(),G3nx.is_directed()
Out[47]:
(False, False, False)

Je li graf bipartitni

promatrani grafovi nisu bipartitni

In [48]:
G1.is_bipartite(),G2.is_bipartite(),G3.is_bipartite()
Out[48]:
(False, False, False)
In [49]:
nx.is_bipartite(G1nx),nx.is_bipartite(G2nx),nx.is_bipartite(G3nx)
Out[49]:
(False, False, False)

Kubni graf jest bipartitni

In [50]:
graphs.CubeGraph(3).is_bipartite()
Out[50]:
True
In [51]:
nx.is_bipartite(nx.cubical_graph())
Out[51]:
True

biparticija kubnog grafa

In [52]:
Graph.bipartite_sets(graphs.CubeGraph(3))
Out[52]:
({'000', '011', '101', '110'}, {'001', '010', '100', '111'})
In [53]:
nx.bipartite.sets(nx.cubical_graph())
Out[53]:
({0, 2, 5, 7}, {1, 3, 4, 6})

Je li je graf povezan

In [54]:
G1.is_connected(),G2.is_connected(),G3.is_connected()
Out[54]:
(True, True, True)
In [55]:
nx.is_connected(G1nx),nx.is_connected(G2nx),nx.is_connected(G3nx)
Out[55]:
(True, True, True)

Broj komponenata povezanosti

In [56]:
G1.connected_components_number(),G2.connected_components_number(),G3.connected_components_number()
Out[56]:
(1, 1, 1)
In [57]:
nx.number_connected_components(G1nx),nx.number_connected_components(G2nx),nx.number_connected_components(G3nx)
Out[57]:
(1, 1, 1)
In [58]:
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)
In [59]:
U.connected_components_number()
Out[59]:
2
In [60]:
nx.number_connected_components(Unx)
Out[60]:
2

komponente povezanosti grafa

In [61]:
U.plot(graph_border=True,vertex_size=700,layout="spring")
Out[61]:

komponente povezanosti

In [62]:
U.connected_components()
Out[62]:
[[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)],
 [(1, 0), (1, 1), (1, 2), (1, 3), (1, 4)]]

komponenta povezanosti koja sadrži vrh (1,1)

In [63]:
U.connected_component_containing_vertex((1,1))
Out[63]:
[(1, 0), (1, 1), (1, 2), (1, 3), (1, 4)]

komponente povezanosti kao podgrafovi

In [64]:
komp=U.connected_components_subgraphs()
komp
Out[64]:
[Subgraph of (Complete graph disjoint_union Complete bipartite graph of order 3+2): Graph on 5 vertices,
 Subgraph of (Complete graph disjoint_union Complete bipartite graph of order 3+2): Graph on 5 vertices]
In [65]:
graphs_list.show_graphs(komp)
In [66]:
figure(figsize=(4,4))
nx.draw_circular(Unx,with_labels=True,node_color='y')

komponente povezanosti

In [67]:
list(nx.connected_components(Unx))
Out[67]:
[{0, 1, 2, 3, 4}, {5, 6, 7, 8, 9}]

komponente povezanosti kao podgrafovi

In [68]:
komp_Unx=[]
for c in nx.connected_components(Unx):
    komp_Unx.append(Unx.subgraph(c).copy())
In [69]:
komp_Unx
Out[69]:
[<networkx.classes.graph.Graph object at 0x7f6b8577f4c0>,
 <networkx.classes.graph.Graph object at 0x7f6b8577fb20>]
In [70]:
figure(figsize=(3,3))
nx.draw_circular(komp_Unx[0],with_labels=True,node_color='y')
In [71]:
figure(figsize=(3,3))
nx.draw_circular(komp_Unx[1],with_labels=True,node_color='y')

Da li je graf jednostavan

In [72]:
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
In [73]:
is_simple(G1),is_simple(G2),is_simple(G3)
Out[73]:
(True, False, True)
In [74]:
is_simple(G1nx),is_simple(G2nx),is_simple(G3nx)
Out[74]:
(True, False, True)

Da li je graf potpun

In [75]:
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
In [76]:
is_complete(G1),is_complete(G2),is_complete(G3)
Out[76]:
(False, False, False)
In [77]:
is_complete(G1nx),is_complete(G2nx),is_complete(G3nx)
Out[77]:
(False, False, False)
In [78]:
is_complete(graphs.CompleteGraph(8))
Out[78]:
True
In [79]:
is_complete(nx.complete_graph(8))
Out[79]:
True

Da li je graf regularan

In [80]:
G1.is_regular(),G2.is_regular(),G3.is_regular()
Out[80]:
(False, False, False)
In [81]:
def regularan(Gnx):
    if len(set(dict(Gnx.degree()).values()))==1:
        return (True,list(dict(Gnx.degree()).values())[0])
    else:
        return False
In [82]:
regularan(G1nx),regularan(G2nx),regularan(G3nx)
Out[82]:
(False, False, False)
In [83]:
graphs.PetersenGraph().is_regular()
Out[83]:
True
In [84]:
regularan(nx.petersen_graph())
Out[84]:
(True, 3)
In [85]:
graphs.CompleteGraph(8).is_regular()
Out[85]:
True
In [86]:
regularan(nx.complete_graph(8))
Out[86]:
(True, 7)

Da li je graf aciklički, tj. da li nema ciklusa

In [87]:
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
In [88]:
is_acyclic(G1),is_acyclic(G2),is_acyclic(G3)
Out[88]:
(False, False, False)
In [89]:
is_acyclic(G1nx),is_acyclic(G2nx),is_acyclic(G3nx)
Out[89]:
(False, False, False)
In [90]:
is_acyclic(graphs.PathGraph(8))
Out[90]:
True
In [91]:
is_acyclic(nx.path_graph(8))
Out[91]:
True

Da li je graf stablo

In [92]:
G1.is_tree(),G2.is_tree(),G3.is_tree()
Out[92]:
(False, False, False)
In [93]:
graphs.PathGraph(8).is_tree()
Out[93]:
True
In [94]:
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
In [95]:
TreeQ(G1nx),TreeQ(G2nx),TreeQ(G3nx)
Out[95]:
(False, False, False)
In [96]:
TreeQ(nx.path_graph(8))
Out[96]:
True

Da li je graf ravninski

In [97]:
G1.is_planar(),G2.is_planar(),G3.is_planar()
Out[97]:
(True, True, True)
In [98]:
graphs.CompleteGraph(5).is_planar()
Out[98]:
False
In [99]:
graphs.CompleteBipartiteGraph(3,3).is_planar()
Out[99]:
False

Da li je graf Eulerov

In [100]:
G1.is_eulerian(),G2.is_eulerian(),G3.is_eulerian()
Out[100]:
(False, False, True)
In [101]:
G1e=Graph(G1,multiedges=True)
G1e.add_edge((1,2))
In [102]:
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])
Out[102]:
In [103]:
G1e.is_eulerian()
Out[103]:
True
In [104]:
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
In [105]:
EulerianQ(G1nx),EulerianQ(G2nx),EulerianQ(G3nx)
Out[105]:
(False, False, False)
In [106]:
EulerianQ(G1e.networkx_graph())
Out[106]:
False

Da li je graf Hamiltonov

In [107]:
G1.is_hamiltonian(),G3.is_hamiltonian()
Out[107]:
(True, False)
In [108]:
G2.is_hamiltonian()
Out[108]:
False

Susjedni vrhovi nekog vrha u grafu

In [109]:
G1.neighbors(2)
Out[109]:
[1, 4, 5]
In [110]:
G1[2]
Out[110]:
[1, 4, 5]
In [111]:
[v for v in G1.neighbor_iterator(2)]
Out[111]:
[1, 4, 5]
In [112]:
list(G1nx.neighbors(2))
Out[112]:
[1, 4, 5]
In [113]:
G1nx[2]
Out[113]:
AtlasView({1: {}, 4: {}, 5: {}})
In [114]:
[v for v in G1nx.neighbors(2)]
Out[114]:
[1, 4, 5]

Udaljenost dva vrha u grafu

In [115]:
G2.distance(3,1)
Out[115]:
1
In [116]:
G2.distance(2,5)
Out[116]:
3
In [117]:
G2.shortest_path_length(2,5)
Out[117]:
3
In [118]:
nx.shortest_path_length(G2nx,3,1)
Out[118]:
1
In [119]:
nx.shortest_path_length(G2nx,2,5)
Out[119]:
3

Najkraći put između dva vrha u grafu

In [120]:
G2.shortest_path(3,1)
Out[120]:
[3, 1]
In [121]:
G2.shortest_path(2,5)
Out[121]:
[2, 3, 4, 5]
In [122]:
G3.shortest_path(1,7)
Out[122]:
[1, 2, 7]
In [123]:
nx.shortest_path(G2nx,3,1)
Out[123]:
[3, 1]
In [124]:
nx.shortest_path(G2nx,2,5)
Out[124]:
[2, 3, 4, 5]
In [125]:
nx.shortest_path(G3nx,1,7)
Out[125]:
[1, 2, 7]

Udaljenost od zadanog vrha prema svim preostalim vrhovima u grafu

In [126]:
G2.shortest_path_lengths(2)
Out[126]:
{2: 0, 3: 1, 1: 1, 4: 2, 5: 3, 6: 4}
In [127]:
G2.shortest_path_lengths(4)
Out[127]:
{4: 0, 5: 1, 3: 1, 2: 2, 1: 2, 6: 2}
In [128]:
G3.shortest_path_lengths(1)
Out[128]:
{1: 0, 6: 1, 2: 1, 8: 2, 7: 2, 3: 2, 5: 2, 4: 3}
In [129]:
nx.shortest_path_length(G2nx,2)
Out[129]:
{2: 0, 1: 1, 3: 1, 4: 2, 5: 3, 6: 4}
In [130]:
nx.shortest_path_length(G2nx,4)
Out[130]:
{4: 0, 3: 1, 5: 1, 1: 2, 2: 2, 6: 2}
In [131]:
nx.shortest_path_length(G3nx,1)
Out[131]:
{1: 0, 2: 1, 6: 1, 3: 2, 5: 2, 7: 2, 8: 2, 4: 3}

Najkraći putovi od zadanog vrha prema svim preostalim vrhovima u grafu

In [132]:
G2.shortest_paths(2)
Out[132]:
{2: [2],
 3: [2, 3],
 1: [2, 1],
 4: [2, 3, 4],
 5: [2, 3, 4, 5],
 6: [2, 3, 4, 5, 6]}
In [133]:
G2.shortest_paths(4)
Out[133]:
{4: [4], 5: [4, 5], 3: [4, 3], 2: [4, 3, 2], 1: [4, 3, 1], 6: [4, 5, 6]}
In [134]:
G3.shortest_paths(1)
Out[134]:
{1: [1],
 6: [1, 6],
 2: [1, 2],
 8: [1, 2, 8],
 7: [1, 2, 7],
 3: [1, 2, 3],
 5: [1, 6, 5],
 4: [1, 6, 5, 4]}
In [135]:
nx.shortest_path(G2nx,2)
Out[135]:
{2: [2],
 1: [2, 1],
 3: [2, 3],
 4: [2, 3, 4],
 5: [2, 3, 4, 5],
 6: [2, 3, 4, 5, 6]}
In [136]:
nx.shortest_path(G2nx,4)
Out[136]:
{4: [4], 3: [4, 3], 5: [4, 5], 1: [4, 3, 1], 2: [4, 3, 2], 6: [4, 5, 6]}
In [137]:
nx.shortest_path(G3nx,1)
Out[137]:
{1: [1],
 2: [1, 2],
 6: [1, 6],
 3: [1, 2, 3],
 7: [1, 2, 7],
 8: [1, 2, 8],
 5: [1, 6, 5],
 4: [1, 2, 3, 4]}
In [138]:
nx.single_source_shortest_path(G2nx,4)
Out[138]:
{4: [4], 3: [4, 3], 5: [4, 5], 1: [4, 3, 1], 2: [4, 3, 2], 6: [4, 5, 6]}

Najkraće udaljenosti između svaka dva vrha u grafu

In [139]:
G1.distance_all_pairs()
Out[139]:
{1: {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2},
 2: {1: 1, 2: 0, 3: 2, 4: 1, 5: 1, 6: 2},
 3: {1: 1, 2: 2, 3: 0, 4: 1, 5: 1, 6: 1},
 4: {1: 1, 2: 1, 3: 1, 4: 0, 5: 1, 6: 2},
 5: {1: 2, 2: 1, 3: 1, 4: 1, 5: 0, 6: 1},
 6: {1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 0}}
In [140]:
G2.distance_all_pairs()
Out[140]:
{1: {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4},
 2: {1: 1, 2: 0, 3: 1, 4: 2, 5: 3, 6: 4},
 3: {1: 1, 2: 1, 3: 0, 4: 1, 5: 2, 6: 3},
 4: {1: 2, 2: 2, 3: 1, 4: 0, 5: 1, 6: 2},
 5: {1: 3, 2: 3, 3: 2, 4: 1, 5: 0, 6: 1},
 6: {1: 4, 2: 4, 3: 3, 4: 2, 5: 1, 6: 0}}
In [141]:
G3.distance_all_pairs()
Out[141]:
{1: {1: 0, 2: 1, 3: 2, 4: 3, 5: 2, 6: 1, 7: 2, 8: 2},
 2: {1: 1, 2: 0, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 1},
 3: {1: 2, 2: 1, 3: 0, 4: 1, 5: 2, 6: 3, 7: 2, 8: 2},
 4: {1: 3, 2: 2, 3: 1, 4: 0, 5: 1, 6: 2, 7: 2, 8: 2},
 5: {1: 2, 2: 2, 3: 2, 4: 1, 5: 0, 6: 1, 7: 1, 8: 1},
 6: {1: 1, 2: 2, 3: 3, 4: 2, 5: 1, 6: 0, 7: 2, 8: 2},
 7: {1: 2, 2: 1, 3: 2, 4: 2, 5: 1, 6: 2, 7: 0, 8: 2},
 8: {1: 2, 2: 1, 3: 2, 4: 2, 5: 1, 6: 2, 7: 2, 8: 0}}
In [142]:
dict(nx.shortest_path_length(G1nx))
Out[142]:
{1: {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2},
 2: {2: 0, 1: 1, 4: 1, 5: 1, 3: 2, 6: 2},
 3: {3: 0, 1: 1, 4: 1, 5: 1, 6: 1, 2: 2},
 4: {4: 0, 1: 1, 2: 1, 3: 1, 5: 1, 6: 2},
 5: {5: 0, 2: 1, 3: 1, 4: 1, 6: 1, 1: 2},
 6: {6: 0, 3: 1, 5: 1, 1: 2, 2: 2, 4: 2}}
In [143]:
dict(nx.shortest_path_length(G2nx))
Out[143]:
{1: {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4},
 2: {2: 0, 1: 1, 3: 1, 4: 2, 5: 3, 6: 4},
 3: {3: 0, 1: 1, 2: 1, 4: 1, 5: 2, 6: 3},
 4: {4: 0, 3: 1, 5: 1, 1: 2, 2: 2, 6: 2},
 5: {5: 0, 4: 1, 6: 1, 3: 2, 1: 3, 2: 3},
 6: {6: 0, 5: 1, 4: 2, 3: 3, 1: 4, 2: 4}}
In [144]:
dict(nx.shortest_path_length(G3nx))
Out[144]:
{1: {1: 0, 2: 1, 6: 1, 3: 2, 5: 2, 7: 2, 8: 2, 4: 3},
 2: {2: 0, 8: 1, 1: 1, 3: 1, 7: 1, 4: 2, 5: 2, 6: 2},
 6: {6: 0, 1: 1, 5: 1, 2: 2, 4: 2, 7: 2, 8: 2, 3: 3},
 3: {3: 0, 2: 1, 4: 1, 1: 2, 5: 2, 7: 2, 8: 2, 6: 3},
 7: {7: 0, 2: 1, 5: 1, 1: 2, 3: 2, 4: 2, 6: 2, 8: 2},
 8: {8: 0, 2: 1, 5: 1, 1: 2, 3: 2, 4: 2, 6: 2, 7: 2},
 4: {4: 0, 3: 1, 5: 1, 2: 2, 6: 2, 7: 2, 8: 2, 1: 3},
 5: {5: 0, 8: 1, 4: 1, 6: 1, 7: 1, 1: 2, 2: 2, 3: 2}}

Najkraći putovi između svaka dva vrha u grafu

In [145]:
G1.shortest_path_all_pairs()
Out[145]:
({1: {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2},
  2: {1: 1, 2: 0, 3: 2, 4: 1, 5: 1, 6: 2},
  3: {1: 1, 2: 2, 3: 0, 4: 1, 5: 1, 6: 1},
  4: {1: 1, 2: 1, 3: 1, 4: 0, 5: 1, 6: 2},
  5: {1: 2, 2: 1, 3: 1, 4: 1, 5: 0, 6: 1},
  6: {1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 0}},
 {1: {1: None, 2: 1, 3: 1, 4: 1, 5: 2, 6: 3},
  2: {1: 2, 2: None, 3: 1, 4: 2, 5: 2, 6: 5},
  3: {1: 3, 2: 1, 3: None, 4: 3, 5: 3, 6: 3},
  4: {1: 4, 2: 4, 3: 4, 4: None, 5: 4, 6: 3},
  5: {1: 2, 2: 5, 3: 5, 4: 5, 5: None, 6: 5},
  6: {1: 3, 2: 5, 3: 6, 4: 3, 5: 6, 6: None}})

udaljenosti

In [146]:
G1.shortest_path_all_pairs()[0]
Out[146]:
{1: {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2},
 2: {1: 1, 2: 0, 3: 2, 4: 1, 5: 1, 6: 2},
 3: {1: 1, 2: 2, 3: 0, 4: 1, 5: 1, 6: 1},
 4: {1: 1, 2: 1, 3: 1, 4: 0, 5: 1, 6: 2},
 5: {1: 2, 2: 1, 3: 1, 4: 1, 5: 0, 6: 1},
 6: {1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 0}}

prethodnici pojedinog vrha na najkraćem putu između dva vrha

In [147]:
G1.shortest_path_all_pairs()[1]
Out[147]:
{1: {1: None, 2: 1, 3: 1, 4: 1, 5: 2, 6: 3},
 2: {1: 2, 2: None, 3: 1, 4: 2, 5: 2, 6: 5},
 3: {1: 3, 2: 1, 3: None, 4: 3, 5: 3, 6: 3},
 4: {1: 4, 2: 4, 3: 4, 4: None, 5: 4, 6: 3},
 5: {1: 2, 2: 5, 3: 5, 4: 5, 5: None, 6: 5},
 6: {1: 3, 2: 5, 3: 6, 4: 3, 5: 6, 6: None}}
In [148]:
nx.shortest_path(G1nx)
Out[148]:
{1: {1: [1], 2: [1, 2], 3: [1, 3], 4: [1, 4], 5: [1, 2, 5], 6: [1, 3, 6]},
 2: {2: [2], 1: [2, 1], 4: [2, 4], 5: [2, 5], 3: [2, 1, 3], 6: [2, 5, 6]},
 3: {3: [3], 1: [3, 1], 4: [3, 4], 5: [3, 5], 6: [3, 6], 2: [3, 1, 2]},
 4: {4: [4], 1: [4, 1], 2: [4, 2], 3: [4, 3], 5: [4, 5], 6: [4, 3, 6]},
 5: {5: [5], 2: [5, 2], 3: [5, 3], 4: [5, 4], 6: [5, 6], 1: [5, 2, 1]},
 6: {6: [6], 3: [6, 3], 5: [6, 5], 1: [6, 3, 1], 4: [6, 3, 4], 2: [6, 5, 2]}}
In [149]:
G2.shortest_path_all_pairs()[1]
Out[149]:
{1: {1: None, 2: 1, 3: 1, 4: 3, 5: 4, 6: 5},
 2: {1: 2, 2: None, 3: 2, 4: 3, 5: 4, 6: 5},
 3: {1: 3, 2: 3, 3: None, 4: 3, 5: 4, 6: 5},
 4: {1: 3, 2: 3, 3: 4, 4: None, 5: 4, 6: 5},
 5: {1: 3, 2: 3, 3: 4, 4: 5, 5: None, 6: 5},
 6: {1: 3, 2: 3, 3: 4, 4: 5, 5: 6, 6: None}}
In [150]:
nx.shortest_path(G2nx)
Out[150]:
{1: {1: [1],
  2: [1, 2],
  3: [1, 3],
  4: [1, 3, 4],
  5: [1, 3, 4, 5],
  6: [1, 3, 4, 5, 6]},
 2: {2: [2],
  1: [2, 1],
  3: [2, 3],
  4: [2, 3, 4],
  5: [2, 3, 4, 5],
  6: [2, 3, 4, 5, 6]},
 3: {3: [3], 1: [3, 1], 2: [3, 2], 4: [3, 4], 5: [3, 4, 5], 6: [3, 4, 5, 6]},
 4: {4: [4], 3: [4, 3], 5: [4, 5], 1: [4, 3, 1], 2: [4, 3, 2], 6: [4, 5, 6]},
 5: {5: [5],
  4: [5, 4],
  6: [5, 6],
  3: [5, 4, 3],
  1: [5, 4, 3, 1],
  2: [5, 4, 3, 2]},
 6: {6: [6],
  5: [6, 5],
  4: [6, 5, 4],
  3: [6, 5, 4, 3],
  1: [6, 5, 4, 3, 1],
  2: [6, 5, 4, 3, 2]}}
In [151]:
G3.shortest_path_all_pairs()[1]
Out[151]:
{1: {1: None, 2: 1, 3: 2, 4: 3, 5: 6, 6: 1, 7: 2, 8: 2},
 2: {1: 2, 2: None, 3: 2, 4: 3, 5: 7, 6: 1, 7: 2, 8: 2},
 3: {1: 2, 2: 3, 3: None, 4: 3, 5: 4, 6: 1, 7: 2, 8: 2},
 4: {1: 2, 2: 3, 3: 4, 4: None, 5: 4, 6: 5, 7: 5, 8: 5},
 5: {1: 6, 2: 7, 3: 4, 4: 5, 5: None, 6: 5, 7: 5, 8: 5},
 6: {1: 6, 2: 1, 3: 2, 4: 5, 5: 6, 6: None, 7: 5, 8: 5},
 7: {1: 2, 2: 7, 3: 2, 4: 5, 5: 7, 6: 5, 7: None, 8: 2},
 8: {1: 2, 2: 8, 3: 2, 4: 5, 5: 8, 6: 5, 7: 2, 8: None}}
In [152]:
nx.shortest_path(G3nx)
Out[152]:
{1: {1: [1],
  2: [1, 2],
  6: [1, 6],
  3: [1, 2, 3],
  7: [1, 2, 7],
  8: [1, 2, 8],
  5: [1, 6, 5],
  4: [1, 2, 3, 4]},
 2: {2: [2],
  1: [2, 1],
  3: [2, 3],
  7: [2, 7],
  8: [2, 8],
  6: [2, 1, 6],
  4: [2, 3, 4],
  5: [2, 7, 5]},
 6: {6: [6],
  1: [6, 1],
  5: [6, 5],
  2: [6, 1, 2],
  4: [6, 5, 4],
  7: [6, 5, 7],
  8: [6, 5, 8],
  3: [6, 1, 2, 3]},
 3: {3: [3],
  2: [3, 2],
  4: [3, 4],
  1: [3, 2, 1],
  7: [3, 2, 7],
  8: [3, 2, 8],
  5: [3, 4, 5],
  6: [3, 2, 1, 6]},
 7: {7: [7],
  2: [7, 2],
  5: [7, 5],
  1: [7, 2, 1],
  3: [7, 2, 3],
  8: [7, 2, 8],
  4: [7, 5, 4],
  6: [7, 5, 6]},
 8: {8: [8],
  2: [8, 2],
  5: [8, 5],
  1: [8, 2, 1],
  3: [8, 2, 3],
  7: [8, 2, 7],
  4: [8, 5, 4],
  6: [8, 5, 6]},
 4: {4: [4],
  3: [4, 3],
  5: [4, 5],
  2: [4, 3, 2],
  6: [4, 5, 6],
  7: [4, 5, 7],
  8: [4, 5, 8],
  1: [4, 3, 2, 1]},
 5: {5: [5],
  4: [5, 4],
  6: [5, 6],
  7: [5, 7],
  8: [5, 8],
  3: [5, 4, 3],
  1: [5, 6, 1],
  2: [5, 7, 2]}}

Ekscentricitet vrha - maksimalna udaljenost vrha od svih preostalih vrhova u grafu

In [153]:
G1.eccentricity()
Out[153]:
[2, 2, 2, 2, 2, 2]
In [154]:
G1.eccentricity(with_labels=True)
Out[154]:
{1: 2, 2: 2, 3: 2, 4: 2, 5: 2, 6: 2}
In [155]:
G1.eccentricity([2,3,6],with_labels=True)
Out[155]:
{2: 2, 3: 2, 6: 2}
In [156]:
G1.eccentricity(5)
Out[156]:
2
In [157]:
G2.eccentricity()
Out[157]:
[4, 4, 3, 2, 3, 4]
In [158]:
G2.eccentricity(with_labels=True)
Out[158]:
{1: 4, 2: 4, 3: 3, 4: 2, 5: 3, 6: 4}
In [159]:
G3.eccentricity()
Out[159]:
[3, 2, 3, 3, 2, 3, 2, 2]
In [160]:
G3.eccentricity(with_labels=True)
Out[160]:
{1: 3, 2: 2, 3: 3, 4: 3, 5: 2, 6: 3, 7: 2, 8: 2}
In [161]:
nx.eccentricity(G1nx)
Out[161]:
{1: 2, 2: 2, 3: 2, 4: 2, 5: 2, 6: 2}
In [162]:
nx.eccentricity(G2nx)
Out[162]:
{1: 4, 2: 4, 3: 3, 4: 2, 5: 3, 6: 4}
In [163]:
nx.eccentricity(G2nx,4)
Out[163]:
2
In [164]:
nx.eccentricity(G3nx)
Out[164]:
{1: 3, 2: 2, 6: 3, 3: 3, 7: 2, 8: 2, 4: 3, 5: 2}

Radijus grafa - minimalni ekscentricitet

In [165]:
G1.radius()
Out[165]:
2
In [166]:
G2.radius()
Out[166]:
2
In [167]:
G3.radius()
Out[167]:
2
In [168]:
nx.radius(G1nx)
Out[168]:
2
In [169]:
nx.radius(G2nx)
Out[169]:
2
In [170]:
nx.radius(G3nx)
Out[170]:
2

Dijametar grafa - maksimalni ekscentricitet

In [171]:
G1.diameter()
Out[171]:
2
In [172]:
G2.diameter()
Out[172]:
4
In [173]:
G3.diameter()
Out[173]:
3
In [174]:
nx.diameter(G1nx)
Out[174]:
2
In [175]:
nx.diameter(G2nx)
Out[175]:
4
In [176]:
nx.diameter(G3nx)
Out[176]:
3

Struk grafa

In [177]:
G1.girth()
Out[177]:
3
In [178]:
G2.girth()
Out[178]:
2
In [179]:
G3.girth()
Out[179]:
4

Rezni bridovi grafa

In [180]:
list(G1.bridges())
Out[180]:
[]
In [181]:
list(G2.bridges())
Out[181]:
[(5, 6, None), (3, 4, None)]
In [182]:
list(G3.bridges())
Out[182]:
[]

Koliko najmanje bridova treba ukloniti iz grafa da on postane nepovezan

In [183]:
G1.edge_connectivity()
Out[183]:
2
In [184]:
G1.edge_connectivity(value_only=False)
Out[184]:
[2, [(6, 3), (6, 5)]]
In [185]:
G1.edge_connectivity(value_only=False,vertices=True)
Out[185]:
[2, [(6, 3), (6, 5)], [[1, 2, 3, 4, 5], [6]]]
In [186]:
G2.allow_multiple_edges(False)
G2.edge_connectivity(value_only=False,implementation="boost")
Out[186]:
[1, [(6, 5)]]
In [187]:
G3.edge_connectivity(value_only=False)
Out[187]:
[2, [(1, 2), (1, 6)]]

Koliko najmanje bridova treba ukoniti između dva vrha da graf postane nepovezan, a ta dva vrha da pripadaju različitim komponentama povezanosti

In [188]:
G1.edge_cut(1,3,value_only=False,vertices=True)
Out[188]:
[3, [(1, 2, None), (1, 3, None), (1, 4, None)], [[1], [2, 3, 4, 5, 6]]]
In [189]:
G2.edge_cut(2,3,value_only=False,vertices=True)
Out[189]:
[2, [(1, 2, None), (2, 3, None)], [[2], [1, 3, 4, 5, 6]]]
In [190]:
G2.edge_cut(1,2,value_only=False)
Out[190]:
[2, [(1, 2, None), (1, 3, None)]]
In [191]:
G3.edge_cut(1,5,value_only=False,vertices=True)
Out[191]:
[2, [(1, 2, None), (1, 6, None)], [[1], [2, 3, 4, 5, 6, 7, 8]]]

Rezni vrhovi grafa

In [192]:
G1.blocks_and_cut_vertices()[1]
Out[192]:
[]
In [193]:
G2.blocks_and_cut_vertices()[1]
Out[193]:
[3, 4, 5]
In [194]:
G3.blocks_and_cut_vertices()[1]
Out[194]:
[]

Bikomponente ili blokovi u grafu - maksimalni inducirani podgrafovi koji nemaju reznih vrhova

In [195]:
G1.blocks_and_cut_vertices()[0]
Out[195]:
[[1, 2, 3, 4, 5, 6]]
In [196]:
G2.blocks_and_cut_vertices()[0]
Out[196]:
[[5, 6], [4, 5], [3, 4], [1, 2, 3]]
In [197]:
G3.blocks_and_cut_vertices()[0]
Out[197]:
[[1, 2, 6, 3, 7, 8, 4, 5]]

Koliko najmanje vrhova treba ukloniti iz grafa da on postane nepovezan

In [198]:
G1.vertex_connectivity()
Out[198]:
2
In [199]:
G1.vertex_connectivity(value_only=False)
Out[199]:
(2, [3, 5])
In [200]:
G1.vertex_connectivity(value_only=False,sets=True)
Out[200]:
(2, [3, 5], [[1, 2, 4], [6]])
In [201]:
G2.vertex_connectivity()
Out[201]:
1
In [202]:
G2.vertex_connectivity(value_only=False,sets=True)
Out[202]:
(1, [5], [[6], [1, 2, 3, 4]])
In [203]:
G3.vertex_connectivity(value_only=False,sets=True)
Out[203]:
(2, [2, 5], [[8], [1, 3, 4, 6, 7]])

Koliko najmanje vrhova treba ukoniti između dva vrha da graf postane nepovezan, a ta dva vrha da pripadaju različitim komponentama povezanosti

In [204]:
G1.vertex_cut(1,4)

---------------------------------------------------------------------------
EmptySetError                             Traceback (most recent call last)
<ipython-input-204-1ffd80b2574e> in <module>
----> 1 G1.vertex_cut(Integer(1),Integer(4))

/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in vertex_cut(self, s, t, value_only, vertices, solver, verbose)
   6708         if g.has_edge(s, t):
   6709             from sage.categories.sets_cat import EmptySetError
-> 6710             raise EmptySetError("there can be no vertex cut between adjacent vertices")
   6711         if vertices:
   6712             value_only = False

EmptySetError: there can be no vertex cut between adjacent vertices
In [205]:
G1.vertex_cut(1,5)
Out[205]:
3
In [206]:
G1.vertex_cut(1,5,value_only=False,vertices=True)
Out[206]:
(3, [2, 3, 4], [[1], [5, 6]])
In [207]:
G2.vertex_cut(2,4,value_only=False,vertices=True)
Out[207]:
(1, [3], [[1, 2], [4, 5, 6]])
In [208]:
G3.vertex_cut(1,3,value_only=False,vertices=True)
Out[208]:
(2, [2, 4], [[1, 5, 6, 7, 8], [3]])

Hamiltonov ciklus

In [209]:
G1.hamiltonian_cycle()
Out[209]:
In [210]:
G1.hamiltonian_cycle().show()

želimo li istaknuti Hamiltonov ciklus na zadanom grafu, možemo definirati svoju funkciju koja će to raditi

In [211]:
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
In [212]:
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])
In [213]:
G2.hamiltonian_cycle()

---------------------------------------------------------------------------
EmptySetError                             Traceback (most recent call last)
<ipython-input-213-bfa16ef694e4> in <module>
----> 1 G2.hamiltonian_cycle()

/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in hamiltonian_cycle(self, algorithm, solver, constraint_generation, verbose, verbose_constraints)
   8310             from sage.numerical.mip import MIPSolverException
   8311             try:
-> 8312                 return self.traveling_salesman_problem(use_edge_labels=False, solver=solver,
   8313                                                        constraint_generation=constraint_generation,
   8314                                                        verbose=verbose, verbose_constraints=verbose_constraints)

/usr/lib/python3.8/site-packages/sage/graphs/generic_graph.py in traveling_salesman_problem(self, use_edge_labels, maximize, solver, constraint_generation, verbose, verbose_constraints)
   7982             # Checks whether the graph is 2-connected
   7983             if not self.strong_orientation().is_strongly_connected():
-> 7984                 raise EmptySetError("the given graph is not Hamiltonian")
   7985 
   7986         ######################################

EmptySetError: the given graph is not Hamiltonian
In [214]:
hamiltonov_ciklus(G2)
Out[214]:
'Error: Graf nije Hamiltonov'
In [215]:
hamiltonov_ciklus(G3)
Out[215]:
'Error: Graf nije Hamiltonov'

Eulerova tura

In [216]:
G3.eulerian_circuit(labels=False)
Out[216]:
[(1, 6),
 (6, 5),
 (5, 8),
 (8, 2),
 (2, 7),
 (7, 5),
 (5, 4),
 (4, 3),
 (3, 2),
 (2, 1)]
In [217]:
G3.eulerian_circuit(labels=False,return_vertices=True)
Out[217]:
([(1, 6),
  (6, 5),
  (5, 8),
  (8, 2),
  (2, 7),
  (7, 5),
  (5, 4),
  (4, 3),
  (3, 2),
  (2, 1)],
 [1, 6, 5, 8, 2, 7, 5, 4, 3, 2, 1])
In [218]:
G3.eulerian_circuit(labels=False,return_vertices=True)[1]
Out[218]:
[1, 6, 5, 8, 2, 7, 5, 4, 3, 2, 1]

Animacija Eulerove ture

In [219]:
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

In [220]:
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])

Nekoliko zadataka

1. zadatak

U zadanom grafu pronađite

     

  1. Sve putove između vrhova $b$ i $d$.
  2. Sve putove između vrhova $b$ i $c$.
  3. Broj šetnji duljine $3$ između vrhova $b$ i $c$.
  4. Ukupni broj svih šetnji duljine $3$.

Rješenje

In [221]:
graf1=Graph({'a':['a','b','d'],'b':['c','d','d'],'c':['d']})

a) dio - donja naredba daje sve putove na pripadnom jednostavnom grafu

In [222]:
graf1.all_paths('b','d')
Out[222]:
[['b', 'c', 'd'], ['b', 'a', 'd'], ['b', 'd']]

b) dio - donja naredba daje sve putove na pripadnom jednostavnom grafu

In [223]:
graf1.all_paths('b','c')
Out[223]:
[['b', 'c'], ['b', 'a', 'd', 'c'], ['b', 'd', 'c']]

c) dio

In [224]:
graf1.vertices()
Out[224]:
['a', 'b', 'c', 'd']
In [225]:
mat1=graf1.adjacency_matrix();mat1
Out[225]:
[1 1 0 1]
[1 0 1 2]
[0 1 0 1]
[1 2 1 0]
In [226]:
mat1^3
Out[226]:
[ 9 11  6 11]
[11  9  8 17]
[ 6  8  4  8]
[11 17  8  9]

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)

In [227]:
(mat1^3)[1,2]
Out[227]:
8
In [228]:
(mat1^3)[graf1.vertices().index('b'),graf1.vertices().index('c')]
Out[228]:
8

d) dio

In [229]:
sum(sum(mat1^3))
Out[229]:
153

2. zadatak

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$.

  1. Ima li petlji u grafu? Da li je graf jednostavan?
  2. Ima li izoliranih vrhova u grafu?
  3. Izračunajte stupnjeve svih vrhova.
  4. Nacrtajte graf.
  5. Odredite broj šetnji duljine 2 i duljine 3 između vrhova $v_1$ i $v_2$, te vrhova $v_1$ i $v_4$.

Rješenje

In [230]:
graf2=Graph({'v1':['v1','v2','v2','v3'],'v2':['v3'],'v4':[]})
In [231]:
graf2.vertices(),graf2.edges(labels=False)
Out[231]:
(['v1', 'v2', 'v3', 'v4'],
 [('v1', 'v1'), ('v1', 'v2'), ('v1', 'v2'), ('v1', 'v3'), ('v2', 'v3')])

a) dio

In [232]:
graf2.has_loops()
Out[232]:
True
In [233]:
graf2.loop_edges()
Out[233]:
[('v1', 'v1', None)]
In [234]:
is_simple(graf2)
Out[234]:
False
In [235]:
graf2.multiple_edges(labels=False)
Out[235]:
[('v1', 'v2'), ('v1', 'v2')]

b) dio -  vrh $v_4$ je izolirani vrh

In [236]:
for vrh in graf2.vertices():
    if graf2.degree(vrh)==0:
        print(vrh,)

v4

c) dio

In [237]:
graf2.degree(labels=True)
Out[237]:
{'v4': 0, 'v2': 3, 'v3': 2, 'v1': 5}

d) dio

In [238]:
graf2.plot(graph_border=True,figsize=[5,4])
Out[238]:

e) dio

In [239]:
mat2=graf2.adjacency_matrix();mat2
Out[239]:
[1 2 1 0]
[2 0 1 0]
[1 1 0 0]
[0 0 0 0]

broj $(v_1,v_2)$-šetnji duljine 2

In [240]:
(mat2^2)[0,1]
Out[240]:
3

broj $(v_1,v_4)$-šetnji duljine 2

In [241]:
(mat2^2)[0,3]
Out[241]:
0

broj $(v_1,v_2)$-šetnji duljine 3

In [242]:
(mat2^3)[0,1]
Out[242]:
15

broj $(v_1,v_4)$-šetnji duljine 3

In [243]:
(mat2^3)[0,3]
Out[243]:
0

3. zadatak

  1. Da li je graf Hamiltonov?
  2. Postoji li Hamiltonov put u grafu?
  3. Da li je graf Eulerov?
  4. Postoji li Eulerova staza u grafu

Rješenje

In [244]:
graf3=Graph({'A':['B','C','E'],'B':['C','D','E'],'C':['D','E']})
In [245]:
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])
Out[245]:

Zadani graf jest Hamiltonov

In [246]:
graf3.hamiltonian_cycle().plot(layout="circular",figsize=[5,4])
Out[246]:
In [247]:
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.

In [248]:
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"
In [249]:
hamiltonov_put(graf3)
Out[249]:
[('A', 'B'), ('B', 'D'), ('C', 'D'), ('C', 'E')]

Funkcija hamiltonov_put_graf ističe neki Hamiltonov put na zadanom grafu ukoliko on postoji.

In [250]:
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"
In [251]:
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

In [252]:
graf3.is_eulerian()
Out[252]:
False
In [253]:
graf3.degree()
Out[253]:
[2, 4, 3, 4, 3]
In [254]:
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
In [255]:
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
In [256]:
eulerova_staza(graf3)
Out[256]:
['A', 'B', 'D', 'C', 'B', 'E', 'C', 'A', 'E']
In [257]:
eulerova_staza(graf3,izlaz="bridovi")
Out[257]:
[('A', 'B'),
 ('B', 'D'),
 ('D', 'C'),
 ('C', 'B'),
 ('B', 'E'),
 ('E', 'C'),
 ('C', 'A'),
 ('A', 'E')]
In [258]:
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])

4. zadatak

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. .

Rješenje

In [259]:
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)])
In [260]:
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

In [261]:
konjic_skok(3,3).plot(pos=pozicije_konjic(3,3),graph_border=True,vertex_size=700,figsize=[4,4])
Out[261]:
In [262]:
konjic_skok(3,3).is_hamiltonian()
Out[262]:
False

Na $8\times8$ ploči to je moguće

In [263]:
konjic_skok(8,8).is_hamiltonian()
Out[263]:
True
In [264]:
konjic_skok(8,8).plot(pos=pozicije_konjic(8,8),graph_border=True,vertex_labels=False,vertex_size=100,figsize=[5,5])
Out[264]:

animacija konjićeve ture na $8\times8$ ploči

Kako bi se lakše pratila animacija, uvodimo sljedeće bojanje polja:

  • polja obojana žutom bojom su polja koja je konjić već posjetio.
  • polje obojano svijetloplavom bojom je polje na kojem je konjić bio u prethodnom koraku
  • polje obojano svijetlozelenom bojom je polje na kojem se konjić trenutno nalazi u tekućem koraku
In [265]:
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]]}
In [266]:
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

In [267]:
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])
In [ ]: