Osnovni pojmovi iz teorije grafova u SAGE-u

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.                        │
└────────────────────────────────────────────────────────────────────┘

Prazan graf

prazan graf s nula vrhova (pazite, prema našoj definiciji graf mora imati barem jedan vrh). Ovdje je uveden i graf s nula vrhova zbog jednostavnije konstrukcije kompliciranijih grafova.

In [2]:
G=graphs.EmptyGraph()
G
Out[2]:
Graph on 0 vertices (use the .plot() method to plot)

broj vrhova i bridova

In [3]:
G.num_verts()
Out[3]:
0
In [4]:
G.num_edges()
Out[4]:
0

vrhovi i bridovi

In [5]:
G.vertices()
Out[5]:
[]
In [6]:
G.edges()
Out[6]:
[]

prazan graf s pet vrhova

In [7]:
G=Graph(5)
G.show(figsize=[5,3])
In [8]:
G.show(layout="circular",figsize=[3,3])

drukčije oznake vrhova

In [9]:
H=Graph([['a','b','c','d','e'], lambda i,j:False])
H.show(layout="circular",figsize=[3,3])

bez oznaka vrhova i željena veličina vrha i boje vrha

In [10]:
H.show(vertex_labels=False,layout="circular",vertex_size=50,vertex_color="yellow",figsize=[3,3])
In [11]:
H.show(layout="circular",vertex_color={"yellow":['a','d'],"red":['b'],"green":['c','e']},figsize=[3,3])

broj vrhova i bridova

In [12]:
H.num_verts()
Out[12]:
5
In [13]:
H.num_edges()
Out[13]:
0

vrhovi i bridovi

In [14]:
H.vertices()
Out[14]:
['a', 'b', 'c', 'd', 'e']
In [15]:
H.edges()
Out[15]:
[]

Potpuni bipartitni graf

$K_{2,3}$

In [16]:
K23=graphs.CompleteBipartiteGraph(2,3)
K23
Out[16]:
In [17]:
K23.show()

broj vrhova i bridova

In [18]:
K23.num_verts()
Out[18]:
5
In [19]:
K23.num_edges()
Out[19]:
6

Vrhovi i bridovi

In [20]:
K23.vertices()
Out[20]:
[0, 1, 2, 3, 4]
In [21]:
K23.edges()
Out[21]:
[(0, 2, None), (0, 3, None), (0, 4, None), (1, 2, None), (1, 3, None), (1, 4, None)]
In [22]:
K23.edges(labels=False)
Out[22]:
[(0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4)]

stupnjevi vrhova

In [23]:
K23.degree()
Out[23]:
[3, 3, 2, 2, 2]
In [24]:
K23.degree(labels=True)
Out[24]:
{0: 3, 1: 3, 2: 2, 3: 2, 4: 2}
In [25]:
K23.degree(3)
Out[25]:
2

ispitivanje regularnosti

In [26]:
K23.is_regular()
Out[26]:
False

matrica susjedstva

In [27]:
K23.adjacency_matrix()
Out[27]:
[0 0 1 1 1]
[0 0 1 1 1]
[1 1 0 0 0]
[1 1 0 0 0]
[1 1 0 0 0]

matrica incidencije

In [28]:
K23.incidence_matrix()
Out[28]:
[1 1 1 0 0 0]
[0 0 0 1 1 1]
[1 0 0 1 0 0]
[0 1 0 0 1 0]
[0 0 1 0 0 1]

$K_{3,3}$

In [29]:
K33=graphs.CompleteBipartiteGraph(3,3)
K33
Out[29]:
In [30]:
K33.show()

broj vrhova i bridova

In [31]:
K33.num_verts()
Out[31]:
6
In [32]:
K33.num_edges()
Out[32]:
9

vrhovi i bridovi

In [33]:
K33.vertices()
Out[33]:
[0, 1, 2, 3, 4, 5]
In [34]:
K33.edges(labels=False)
Out[34]:
[(0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)]

stupnjevi vrhova

In [35]:
K33.degree()
Out[35]:
[3, 3, 3, 3, 3, 3]
In [36]:
K33.degree(labels=True)
Out[36]:
{0: 3, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3}
In [37]:
K33.degree(4)
Out[37]:
3

ispitivanje regularnosti

In [38]:
K33.is_regular()
Out[38]:
True

matrica susjedstva

In [39]:
K33.adjacency_matrix()
Out[39]:
[0 0 0 1 1 1]
[0 0 0 1 1 1]
[0 0 0 1 1 1]
[1 1 1 0 0 0]
[1 1 1 0 0 0]
[1 1 1 0 0 0]

matrica incidencije

In [40]:
K33.incidence_matrix()
Out[40]:
[1 1 1 0 0 0 0 0 0]
[0 0 0 1 1 1 0 0 0]
[0 0 0 0 0 0 1 1 1]
[1 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 0 1 0]
[0 0 1 0 0 1 0 0 1]

$K_{4,3}$

In [41]:
K43=graphs.CompleteBipartiteGraph(4,3)
K43
Out[41]:
In [42]:
K43.show()

broj vrhova i bridova

In [43]:
K43.num_verts()
Out[43]:
7
In [44]:
K43.num_edges()
Out[44]:
12

vrhovi i bridovi

In [45]:
K43.vertices()
Out[45]:
[0, 1, 2, 3, 4, 5, 6]
In [46]:
K43.edges(labels=False)
Out[46]:
[(0, 4), (0, 5), (0, 6), (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)]

stupnjevi vrhova

In [47]:
K43.degree()
Out[47]:
[3, 3, 3, 3, 4, 4, 4]
In [48]:
K43.degree(labels=True)
Out[48]:
{0: 3, 1: 3, 2: 3, 3: 3, 4: 4, 5: 4, 6: 4}
In [49]:
K43.degree(2)
Out[49]:
3

ispitivanje regularnosti

In [50]:
K43.is_regular()
Out[50]:
False

matrica susjedstva

In [51]:
K43.adjacency_matrix()
Out[51]:
[0 0 0 0 1 1 1]
[0 0 0 0 1 1 1]
[0 0 0 0 1 1 1]
[0 0 0 0 1 1 1]
[1 1 1 1 0 0 0]
[1 1 1 1 0 0 0]
[1 1 1 1 0 0 0]

matrica incidencije

In [52]:
K43.incidence_matrix()
Out[52]:
[1 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 1 1 1 0 0 0 0 0 0]
[0 0 0 0 0 0 1 1 1 0 0 0]
[0 0 0 0 0 0 0 0 0 1 1 1]
[1 0 0 1 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 0 1 0 0 1 0]
[0 0 1 0 0 1 0 0 1 0 0 1]

Petersenov graf

In [53]:
P=graphs.PetersenGraph()
P
Out[53]:
In [54]:
P.show(figsize=[4,4])

broj vrhova i bridova

In [55]:
P.num_verts()
Out[55]:
10
In [56]:
P.num_edges()
Out[56]:
15

vrhovi i bridovi

In [57]:
P.vertices()
Out[57]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [58]:
P.edges(labels=False)
Out[58]:
[(0, 1), (0, 4), (0, 5), (1, 2), (1, 6), (2, 3), (2, 7), (3, 4), (3, 8), (4, 9), (5, 7), (5, 8), (6, 8), (6, 9), (7, 9)]

stupnjevi vrhova

In [59]:
P.degree()
Out[59]:
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
In [60]:
P.degree(labels=True)
Out[60]:
{0: 3, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3, 7: 3, 8: 3, 9: 3}

ispitivanje regularnosti

In [61]:
P.is_regular()
Out[61]:
True

matrica susjedstva

In [62]:
P.adjacency_matrix()
Out[62]:
[0 1 0 0 1 1 0 0 0 0]
[1 0 1 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 1]
[1 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 1 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 1 0 1 1 0 0]

matrica incidencije

In [63]:
P.incidence_matrix()
Out[63]:
[1 1 1 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 1 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 1 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 1 1 0 0 0 0 0 0]
[0 1 0 0 0 0 0 1 0 1 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 1 1 0 0 0]
[0 0 0 0 1 0 0 0 0 0 0 0 1 1 0]
[0 0 0 0 0 0 1 0 0 0 1 0 0 0 1]
[0 0 0 0 0 0 0 0 1 0 0 1 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 1 1]

Kubni graf

In [64]:
Kub=graphs.CubeGraph(3)
In [65]:
Kub.show(vertex_size=500,figsize=(4.5,4.5),layout="spring")

broj vrhova i bridova

In [66]:
Kub.num_verts()
Out[66]:
8
In [67]:
Kub.num_edges()
Out[67]:
12

vrhovi i bridovi

In [68]:
Kub.vertices()
Out[68]:
['000', '001', '010', '011', '100', '101', '110', '111']
In [69]:
Kub.edges(labels=False)
Out[69]:
[('000', '001'), ('000', '010'), ('000', '100'), ('001', '011'), ('001', '101'), ('010', '011'), ('010', '110'), ('011', '111'), ('100', '101'), ('100', '110'), ('101', '111'), ('110', '111')]

stupnjevi vrhova

In [70]:
Kub.degree()
Out[70]:
[3, 3, 3, 3, 3, 3, 3, 3]
In [71]:
Kub.degree(labels=True)
Out[71]:
{'000': 3,
 '001': 3,
 '010': 3,
 '011': 3,
 '100': 3,
 '101': 3,
 '110': 3,
 '111': 3}
In [72]:
Kub.degree('001')
Out[72]:
3

ispitivanje regularnosti

In [73]:
Kub.is_regular()
Out[73]:
True

matrica susjedstva

In [74]:
Kub.adjacency_matrix()
Out[74]:
[0 1 1 0 1 0 0 0]
[1 0 0 1 0 1 0 0]
[1 0 0 1 0 0 1 0]
[0 1 1 0 0 0 0 1]
[1 0 0 0 0 1 1 0]
[0 1 0 0 1 0 0 1]
[0 0 1 0 1 0 0 1]
[0 0 0 1 0 1 1 0]

matrica incidencije

In [75]:
Kub.incidence_matrix()
Out[75]:
[1 1 1 0 0 0 0 0 0 0 0 0]
[1 0 0 1 1 0 0 0 0 0 0 0]
[0 1 0 0 0 1 1 0 0 0 0 0]
[0 0 0 1 0 1 0 1 0 0 0 0]
[0 0 1 0 0 0 0 0 1 1 0 0]
[0 0 0 0 1 0 0 0 1 0 1 0]
[0 0 0 0 0 0 1 0 0 1 0 1]
[0 0 0 0 0 0 0 1 0 0 1 1]

Potpuni graf

In [76]:
K5=graphs.CompleteGraph(5)
K5
Out[76]:
In [77]:
K5.show()

broj vrhova i bridova

In [78]:
K5.num_verts()
Out[78]:
5
In [79]:
K5.num_edges()
Out[79]:
10

vrhovi i bridovi

In [80]:
K5.vertices()
Out[80]:
[0, 1, 2, 3, 4]
In [81]:
K5.edges(labels=False)
Out[81]:
[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

stupnjevi vrhova

In [82]:
K5.degree()
Out[82]:
[4, 4, 4, 4, 4]
In [83]:
K5.degree(labels=True)
Out[83]:
{0: 4, 1: 4, 2: 4, 3: 4, 4: 4}

ispitivanje regularnosti

In [84]:
K5.is_regular()
Out[84]:
True

matrica susjedstva

In [85]:
K5.adjacency_matrix()
Out[85]:
[0 1 1 1 1]
[1 0 1 1 1]
[1 1 0 1 1]
[1 1 1 0 1]
[1 1 1 1 0]

matrica incidencije

In [86]:
K5.incidence_matrix()
Out[86]:
[1 1 1 1 0 0 0 0 0 0]
[1 0 0 0 1 1 1 0 0 0]
[0 1 0 0 1 0 0 1 1 0]
[0 0 1 0 0 1 0 1 0 1]
[0 0 0 1 0 0 1 0 1 1]

$K_{\nu},\quad \nu\in\{1,2,3,\ldots,19\}$

In [87]:
lista=[]
for i in range(1,20):
    lista.append(graphs.CompleteGraph(i))
graphs_list.to_graphics_array(lista).show(figsize=[8,8])

$K_{25}$

In [88]:
graphs.CompleteGraph(25).show()
In [89]:
graphs.CompleteGraph(25).show(vertex_size=10,vertex_labels=False)

$n$-dimenzionalna kocka

In [90]:
Kub4=graphs.CubeGraph(4)
Kub4
Out[90]:
In [91]:
Kub4.show(vertex_size=400,figsize=(6,6),layout="spring")

broj vrhova i bridova

In [92]:
Kub4.num_verts()
Out[92]:
16
In [93]:
Kub4.num_edges()
Out[93]:
32

vrhovi i bridovi

In [94]:
Kub4.vertices()
Out[94]:
['0000',
 '0001',
 '0010',
 '0011',
 '0100',
 '0101',
 '0110',
 '0111',
 '1000',
 '1001',
 '1010',
 '1011',
 '1100',
 '1101',
 '1110',
 '1111']
In [95]:
Kub4.edges(labels=False)
Out[95]:
[('0000', '0001'), ('0000', '0010'), ('0000', '0100'), ('0000', '1000'), ('0001', '0011'), ('0001', '0101'), ('0001', '1001'), ('0010', '0011'), ('0010', '0110'), ('0010', '1010'), ('0011', '0111'), ('0011', '1011'), ('0100', '0101'), ('0100', '0110'), ('0100', '1100'), ('0101', '0111'), ('0101', '1101'), ('0110', '0111'), ('0110', '1110'), ('0111', '1111'), ('1000', '1001'), ('1000', '1010'), ('1000', '1100'), ('1001', '1011'), ('1001', '1101'), ('1010', '1011'), ('1010', '1110'), ('1011', '1111'), ('1100', '1101'), ('1100', '1110'), ('1101', '1111'), ('1110', '1111')]

stupnjevi vrhova

In [96]:
Kub4.degree()
Out[96]:
[4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
In [97]:
Kub4.degree(labels=True)
Out[97]:
{'0000': 4,
 '0001': 4,
 '0010': 4,
 '0011': 4,
 '0100': 4,
 '0101': 4,
 '0110': 4,
 '0111': 4,
 '1000': 4,
 '1001': 4,
 '1010': 4,
 '1011': 4,
 '1100': 4,
 '1101': 4,
 '1110': 4,
 '1111': 4}
In [98]:
Kub4.degree('1101')
Out[98]:
4

ispitivanje regularnosti

In [99]:
Kub4.is_regular()
Out[99]:
True

matrica susjedstva

In [100]:
Kub4.adjacency_matrix()
Out[100]:
[0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0]
[1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0]
[1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0]
[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0]
[0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0]
[0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0]
[0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1]
[1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0]
[0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0]
[0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0]
[0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1]
[0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1]
[0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0]

matrica incidencije

In [101]:
Kub4.incidence_matrix()
Out[101]:
[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1]

još nekoliko kocki u višim dimenzijama

In [102]:
graphs.CubeGraph(5).show(vertex_labels=False,vertex_size=10,figsize=(5,5),layout="spring")
In [103]:
graphs.CubeGraph(6).show(vertex_labels=False,vertex_size=10,figsize=(5,5),layout="spring")
In [104]:
graphs.CubeGraph(7).show(vertex_labels=False,vertex_size=10,figsize=(5,5),layout="spring")

Komplementarni graf

komplement potpunog grafa $K_4$

In [105]:
K4=graphs.CompleteGraph(4)
K4.complement()
Out[105]:
In [106]:
K4.complement().show(figsize=[3,3])

komplement Petersenovog grafa

Petersenov graf je već ranije spremljen u varijablu P

In [107]:
P.complement().show()

komplement potpunog bipartitnog grafa $K_{2,3}$

In [108]:
K23.complement().show(layout="spring",graph_border=True)

Linijski graf

linijski graf potpunog grafa $K_4$

In [109]:
K4.line_graph().show(layout="circular")
In [110]:
K4.line_graph(labels=False).show(layout="circular",vertex_size=800,xmin=-1,xmax=1,ymin=-1.1,ymax=1.1)

linijski graf Petersenovog grafa

In [111]:
P.line_graph(labels=False).show(layout="spring",vertex_size=200)
In [112]:
P.line_graph(labels=False).show(layout="circular",vertex_size=500)

linijski graf poptunog bipartitnog grafa $K_{2,3}$

In [113]:
K23.line_graph(labels=False).show(vertex_size=800,graph_border=True)

linijski graf kubnog grafa

In [114]:
Kub.line_graph(labels=False).show()
In [115]:
Kub.line_graph().show(vertex_labels=False)

Podgrafovi

inducirani podgrafovi

In [116]:
podgraf1=K23.subgraph(vertices=[0,2,3,4],algorithm='add')
gr=graphics_array([K23.plot(graph_border=True),podgraf1.plot(graph_border=True)])
gr.show(figsize=[8,6])
In [117]:
podgraf2=P.subgraph(vertices=[0,2,3,5,7,9],algorithm='add')
podgraf3=P.subgraph(vertices=[0,2,3,5,9],algorithm='add')
gr2=graphics_array([P.plot(graph_border=True),podgraf2.plot(graph_border=True),podgraf3.plot(graph_border=True)])
gr2.show(figsize=[10,6])

brisanje vrhova

In [118]:
K23=graphs.CompleteBipartiteGraph(2,3)
K23_1=graphs.CompleteBipartiteGraph(2,3)
K23_1.delete_vertex(0)
K23_2=graphs.CompleteBipartiteGraph(2,3)
K23_2.delete_vertices([0,3])
gr3=graphics_array([K23.plot(graph_border=True),K23_1.plot(graph_border=True),K23_2.plot(graph_border=True)])
gr3.show(figsize=[10,6])
In [119]:
P=graphs.PetersenGraph()
P1=graphs.PetersenGraph()
P1.delete_vertex(9)
P2=graphs.PetersenGraph()
P2.delete_vertices([0,1,2,3,4])
gr4=graphics_array([P.plot(graph_border=True),P1.plot(graph_border=True),P2.plot(graph_border=True)])
gr4.show(figsize=[10,6])

brisanje bridova

In [120]:
K23=graphs.CompleteBipartiteGraph(2,3)
K23_1=graphs.CompleteBipartiteGraph(2,3)
K23_1.delete_edge(1,3)
K23_2=graphs.CompleteBipartiteGraph(2,3)
K23_2.delete_edges([(0,3),(1,2)])
gr5=graphics_array([K23.plot(graph_border=True),K23_1.plot(graph_border=True),K23_2.plot(graph_border=True)])
gr5.show(figsize=[10,6])
In [121]:
P=graphs.PetersenGraph()
P1=graphs.PetersenGraph()
P1.delete_edge(0,5)
P2=graphs.PetersenGraph()
P2.delete_edges([(0,5),(1,6),(2,7),(3,8),(4,9)])
gr6=graphics_array([P.plot(graph_border=True),P1.plot(graph_border=True),P2.plot(graph_border=True)])
gr6.show(figsize=[10,6])

proizvoljni podgrafovi

In [122]:
podgraf4=P.subgraph(vertices=range(10),edges=[(0,5),(1,6),(2,7),(3,8),(4,9)],algorithm='add')
podgraf5=P.subgraph(vertices=[5,6,7,8,9],edges=[(6,9),(5,7),(5,8)],algorithm='add')
gr7=graphics_array([P.plot(graph_border=True),podgraf4.plot(graph_border=True),podgraf5.plot(graph_border=True)])
gr7.show(figsize=[10,6])

random inducirani podgraf

In [123]:
ran1=P.random_subgraph(0.3)
ran2=P.random_subgraph(0.7)
gr8=graphics_array([P.plot(graph_border=True),ran1.plot(graph_border=True),ran2.plot(graph_border=True)])
gr8.show(figsize=[10,6])

unija grafova

In [124]:
unija=P.union(K23)
gr9=graphics_array([P.plot(graph_border=True),K23.plot(graph_border=True),unija.plot(graph_border=True)])
gr9.show(figsize=[10,6])

disjunktna unija grafova

In [125]:
dis_unija=P.disjoint_union(K23)
gr10=graphics_array([P.plot(graph_border=True),K23.plot(graph_border=True),dis_unija.plot(graph_border=True,layout="circular")])
gr10.show(figsize=[14,7])

Nekoliko zadataka

1. zadatak

Graf $G$ zadan je matricom susjedstva

$$A=\begin{bmatrix}1&1&1&1\\ 1&1&1&1\\ 1&1&1&1\\ 1&1&1&1\end{bmatrix}.$$

Nacrtajte graf $G$, odredite stupnjeve njegovih vrhova, matricu incidencije i provjerite da li je regularan i jednostavni.

Rješenje

definicija i prikaz grafa $G$

In [126]:
G=Graph(matrix([[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]]),loops=True)
G.show(graph_border=True)

stupnjevi vrhova

In [127]:
G.degree(labels=True)
Out[127]:
{0: 5, 1: 5, 2: 5, 3: 5}

graf $G$ je regularan

In [128]:
G.is_regular()
Out[128]:
True

graf $G$ nije jednostavan

In [129]:
G.to_simple()==G
Out[129]:
False

matrica incidencije

In [130]:
G.incidence_matrix()
Out[130]:
[2 1 1 1 0 0 0 0 0 0]
[0 1 0 0 2 1 1 0 0 0]
[0 0 1 0 0 1 0 2 1 0]
[0 0 0 1 0 0 1 0 1 2]

2. zadatak

Graf $G$ zadan je matricom susjedstva

$$A=\begin{bmatrix}1&2&0&2&1\\ 2&1&2&0&1\\ 0&2&1&2&1\\ 2&0&2&1&1\\ 1&1&1&1&0\end{bmatrix}.$$

Nacrtajte graf $G$, odredite stupnjeve njegovih vrhova, matricu incidencije i provjerite da li je regularan i jednostavni.

Rješenje

definicija i prikaz grafa $G$

In [131]:
G=Graph(matrix([[1,2,0,2,1],[2,1,2,0,1],[0,2,1,2,1],[2,0,2,1,1],[1,1,1,1,0]]))
G.show(graph_border=True,pos={0:[0,2],1:[2,2],2:[2,0],3:[0,0],4:[1,1]})

stupnjevi vrhova

In [132]:
G.degree(labels=True)
Out[132]:
{0: 7, 1: 7, 2: 7, 3: 7, 4: 4}

graf $G$ nije regularan

In [133]:
G.is_regular()
Out[133]:
False

Graf $G$ nije jednostavan

In [134]:
G.to_simple()==G
Out[134]:
False

matrica incidencije

In [135]:
G.incidence_matrix()
Out[135]:
[2 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
[0 1 1 0 0 0 2 1 1 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 1 0 2 1 1 1 0 0]
[0 0 0 1 1 0 0 0 0 0 0 1 1 0 2 1]
[0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1]

3. zadatak

Zadani su grafovi

 

  1. Pronađite matrice susjedstva $A_1$ i $A_2$ zadanih grafova.
  2. Dokažite da su grafovi $G_1$ i $G_2$ izomorfni tako da konstruirate jedan izomorfizam.
  3. Pronađite matricu permutacije $P$ takvu da je $PA_1P^T=A_2$.

Rješenje

In [136]:
graf1=Graph({'v1':['v2','v4','v5'],'v2':['v3'],'v3':['v5'],'v4':[],'v5':[]})
graf2=Graph({'u1':['u2','u5'],'u2':['u4'],'u3':['u4'],'u4':['u5'],'u5':[]})
In [137]:
matrica1=graf1.adjacency_matrix()
In [138]:
graf1.show(graph_border=True)
In [139]:
matrica2=graf2.adjacency_matrix()

grafovi su izomorfni

In [140]:
graf1.is_isomorphic(graf2)
Out[140]:
True

dobivanje izomorfizma

In [141]:
graf1.is_isomorphic(graf2,certificate=True)
Out[141]:
(True, {'v3': 'u1', 'v5': 'u5', 'v1': 'u4', 'v4': 'u3', 'v2': 'u2'})

možemo raditi i s pythonovim modulom NetworkX

In [142]:
graf1=Graph({'v1':['v2','v4','v5'],'v2':['v3'],'v3':['v5'],'v4':[],'v5':[]})
graf2=Graph({'u1':['u2','u5'],'u2':['u4'],'u3':['u4'],'u4':['u5'],'u5':[]})
G1=graf1.networkx_graph()
G2=graf2.networkx_graph()
In [143]:
type(graf1),type(graf2)
Out[143]:
(<class 'sage.graphs.graph.Graph'>, <class 'sage.graphs.graph.Graph'>)
In [144]:
type(G1),type(G2)
Out[144]:
(<class 'networkx.classes.graph.Graph'>,
 <class 'networkx.classes.graph.Graph'>)
In [145]:
G1.nodes(),G2.nodes()
Out[145]:
(NodeView(('v3', 'v5', 'v1', 'v4', 'v2')),
 NodeView(('u1', 'u4', 'u3', 'u5', 'u2')))
In [146]:
import networkx as nx
In [147]:
nx.is_isomorphic(G1,G2)
Out[147]:
True
In [148]:
GM=nx.isomorphism.GraphMatcher(G1,G2)
In [149]:
type(GM)
Out[149]:
<class 'networkx.algorithms.isomorphism.vf2userfunc.GraphMatcher'>
In [150]:
GM.G1_nodes,GM.G2_nodes
Out[150]:
({'v1', 'v2', 'v3', 'v4', 'v5'}, {'u1', 'u2', 'u3', 'u4', 'u5'})
In [151]:
GM.is_isomorphic()
Out[151]:
True

izomorfizam grafova

In [152]:
GM.mapping
Out[152]:
{'v3': 'u1', 'v2': 'u5', 'v1': 'u4', 'v4': 'u3', 'v5': 'u2'}
In [153]:
GM.core_1
Out[153]:
{'v3': 'u1', 'v2': 'u5', 'v1': 'u4', 'v4': 'u3', 'v5': 'u2'}
In [154]:
GM.core_2
Out[154]:
{'u1': 'v3', 'u5': 'v2', 'u4': 'v1', 'u3': 'v4', 'u2': 'v5'}

svi izomorfizmi

In [155]:
for u in GM.isomorphisms_iter():
    print(u)

{'v3': 'u1', 'v2': 'u5', 'v1': 'u4', 'v4': 'u3', 'v5': 'u2'}
{'v3': 'u1', 'v5': 'u5', 'v1': 'u4', 'v4': 'u3', 'v2': 'u2'}

matrica permutacije

In [156]:
grupa=SymmetricGroup(5)

$[1,2,3,4,5] \mapsto [4,2,1,3,5]$

In [157]:
grupa([4,2,1,3,5])
Out[157]:
(1,4,3)

matrica permutacije $P$ za prvi izomorfizam

In [158]:
grupa([4,2,1,3,5]).matrix().transpose()
Out[158]:
[0 0 1 0 0]
[0 1 0 0 0]
[0 0 0 1 0]
[1 0 0 0 0]
[0 0 0 0 1]

$[1,2,3,4,5]\mapsto [4,5,1,3,2]$

In [159]:
grupa([4,5,1,3,2])
Out[159]:
(1,4,3)(2,5)

matrica permutacije $P$ za drugi izomorfizam

In [160]:
grupa([4,5,1,3,2]).matrix().transpose()
Out[160]:
[0 0 1 0 0]
[0 0 0 0 1]
[0 0 0 1 0]
[1 0 0 0 0]
[0 1 0 0 0]

4. zadatak

Dokažite da su grafovi $G_1$ i $G_2$ izomorfni tako da konstruirate jedan izomorfizam između njih.

 

Pronađite i njihove matrice susjedstva $A_1$ i $A_2$ takve da $i$-tom retku u pojedinoj matrici odgovara vrh $u_i$ odnosno vrh $v_i$. Pronađite matricu permutacije $P$ za koju vrijedi $PA_1P^T=A_2$.

Rješenje

Radit ćemo odmah s networkx modulom.

In [161]:
graf1=Graph({1:[3,4,5],2:[4,5,6],3:[5,6],4:[6]})
graf2=Graph({1:[2,5,6],2:[3,6],3:[4,5],4:[5,6]})
G1=graf1.networkx_graph()
G2=graf2.networkx_graph()
In [162]:
G1.nodes(),G2.nodes()
Out[162]:
(NodeView((1, 2, 3, 4, 5, 6)), NodeView((1, 2, 3, 4, 5, 6)))
In [163]:
GM=nx.isomorphism.GraphMatcher(G1,G2)
In [164]:
GM.G1_nodes,GM.G2_nodes
Out[164]:
({1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 6})
In [165]:
GM.is_isomorphic()
Out[165]:
True

jedan izomorfizam

In [166]:
GM.mapping
Out[166]:
{1: 1, 3: 2, 6: 3, 2: 4, 4: 5, 5: 6}

svi izomorfizmi

In [167]:
for u in GM.isomorphisms_iter():
    print(u)

{1: 1, 3: 2, 6: 3, 2: 4, 4: 5, 5: 6}
{1: 1, 5: 2, 2: 3, 6: 4, 4: 5, 3: 6}
{2: 1, 4: 2, 1: 3, 3: 4, 5: 5, 6: 6}
{2: 1, 6: 2, 3: 3, 1: 4, 5: 5, 4: 6}
{3: 1, 1: 2, 4: 3, 2: 4, 6: 5, 5: 6}
{3: 1, 5: 2, 2: 3, 4: 4, 6: 5, 1: 6}
{4: 1, 2: 2, 5: 3, 3: 4, 1: 5, 6: 6}
{4: 1, 6: 2, 3: 3, 5: 4, 1: 5, 2: 6}
{5: 1, 1: 2, 4: 3, 6: 4, 2: 5, 3: 6}
{5: 1, 3: 2, 6: 3, 4: 4, 2: 5, 1: 6}
{6: 1, 2: 2, 5: 3, 1: 4, 3: 5, 4: 6}
{6: 1, 4: 2, 1: 3, 5: 4, 3: 5, 2: 6}

matrice susjedstva

In [168]:
graf1.adjacency_matrix()
Out[168]:
[0 0 1 1 1 0]
[0 0 0 1 1 1]
[1 0 0 0 1 1]
[1 1 0 0 0 1]
[1 1 1 0 0 0]
[0 1 1 1 0 0]
In [169]:
graf2.adjacency_matrix()
Out[169]:
[0 1 0 0 1 1]
[1 0 1 0 0 1]
[0 1 0 1 1 0]
[0 0 1 0 1 1]
[1 0 1 1 0 0]
[1 1 0 1 0 0]

matrica permutacije

pronađimo matrice permutacije za izomorfizme $\{1: 1,  2: 4,  3: 2,  4: 5,  5: 6,  6: 3\}$ i $\{1: 3,  2: 6,  3: 5,  4: 2,  5: 4,  6: 1\}$. Analogno se radi i za ostale izomorfizme.

In [170]:
grupa=SymmetricGroup(6)

za izomorfizam $\{1: 1,  2: 4,  3: 2,  4: 5,  5: 6,  6: 3\}$

In [171]:
grupa([1,4,2,5,6,3]).matrix().transpose()
Out[171]:
[1 0 0 0 0 0]
[0 0 1 0 0 0]
[0 0 0 0 0 1]
[0 1 0 0 0 0]
[0 0 0 1 0 0]
[0 0 0 0 1 0]

za izomorfizam $\{1: 3,  2: 6,  3: 5,  4: 2,  5: 4,  6: 1\}$

In [172]:
grupa([3,6,5,2,4,1]).matrix().transpose()
Out[172]:
[0 0 0 0 0 1]
[0 0 0 1 0 0]
[1 0 0 0 0 0]
[0 0 0 0 1 0]
[0 0 1 0 0 0]
[0 1 0 0 0 0]

5. zadatak

Nacrtajte sve jednostavne neizomorfne grafove s tri vrha.

Rješenje

In [173]:
triVrha=list(graphs(3))
lista3=[g.plot(vertex_size=30,vertex_labels=False,layout="circular",graph_border=True) for g in triVrha]
graphics_array(lista3,2,2).show(figsize=[4,4])

6. zadatak

Nacrtajte sve jednostavne neizomorfne grafove s četiri vrha.

Rješenje

In [174]:
cetiriVrha=list(graphs(4))
lista4=[g.plot(vertex_size=30,vertex_labels=False,layout="circular",graph_border=True) for g in cetiriVrha]
graphics_array(lista4,4,3)
Out[174]:

7. zadatak

Nacrtajte sve jednostavne neizomorfne grafove s pet vrhova.

Rješenje

In [175]:
len(list(graphs(5)))
Out[175]:
34
In [176]:
petVrha=list(graphs(5))
lista5=[g.plot(vertex_size=30,vertex_labels=False,layout="circular",graph_border=True) for g in petVrha]
graphics_array(lista5,6,6).show(figsize=[8,8])

8. zadatak

Da li je $G_1$ podgraf od $G_2$?

Rješenje

naredbom subgraph_search tražimo podgrafove u grafu s time da se na izlazu vraća inducirani podgraf koji sadrži zadani graf za kojeg smo ispitivali da li je podgraf.

In [177]:
gr1=Graph({0:[1,3],1:[2],2:[3]})
gr2=Graph({0:[3,4],1:[2,3],2:[3,4],3:[4]})
#gr2.relabel(list('abcde'))
gr3=gr2.subgraph_search(gr1)
In [178]:
gr3
Out[178]:

Uočite da je na trećoj slici vraćen podgraf grafa s druge slike koji sadrži graf na prvoj slici. Dakle, $G_1$ je podgraf od $G_2$.

In [179]:
graphics_array([gr1.plot(graph_border=True,layout="circular"),gr2.plot(graph_border=True,layout="circular"),
                gr3.plot(graph_border=True,layout="circular")])
Out[179]:

$G_1$ nije inducirani podgraf od $G_2$

In [180]:
gr2.subgraph_search(gr1,induced=True) is None
Out[180]:
True

9. zadatak

Da li je $G_1$ podgraf od $G_2$?

Rješenje

In [181]:
gr1=Graph({0:[1,3],1:[2,3],2:[3]})
gr2=Graph({0:[4,5],1:[3,4],2:[3,4],4:[5]})
gr3=gr2.subgraph_search(gr1)

nije vraćen nikakvi podgraf pa zaključujemo da $G_1$ nije podgraf od $G_2$

In [182]:
print(gr3)

None

10. zadatak

Da li je $G_1$ podgraf od $G_2$?

Rješenje

In [183]:
gr1=Graph({0:[2,3,4],1:[2,3,4]})
gr2=Graph({0:[1,4,5],1:[2,3,5],2:[3,4],3:[4],4:[5]})
gr3=gr2.subgraph_search(gr1,induced=False)
gr4=gr2.subgraph_search(gr1,induced=True)

$G_1$ je podgraf od $G_2$

In [184]:
gr3
Out[184]:
In [185]:
graphics_array([gr1.plot(graph_border=True,layout="circular"),gr2.plot(graph_border=True,layout="circular"),
                gr3.plot(graph_border=True,layout="circular")])
Out[185]:

$G_1$ nije inducirani podgraf od $G_2$

In [186]:
print(gr4)

None

Implementirat ćemo funkciju podgraf koja ispituje je li graf G1 podgraf grafa G2. U slučaju da G1 nije podgraf grafa G2, funkcija vraća False, a inače će nacrtati graf G2 i na njemu crvenom bojom istaknuti podgraf G1. Opcije raspored_vrhova i laj služe samo za željeni raspored vrhova prilikom crtanja grafa. Ukoliko je G1 podgraf grafa G2, funkcija vraća samo jednu mogućnost smještanja grafa G1 na graf G2 (ukoliko ima više mogućnosti, funkcija će vratiti samo jednu mogućnost). Radi jednostavnosti implementacije, pretpostavlja se da graf s $n$ vrhova ima oznake vrhova $0,1,2,\ldots,n-1$. U protivnom algoritam neće raditi. Imajte na umu da algoritam radi grubom silom tako da prolazi kroz sve mogućnosti i uzima prvu koja je dobra tako da nije efikasan na velikim grafovima. Općenito ne postoji efikasan algoritam za taj problem.

In [187]:
def podgraf(G1,G2,raspored_vrhova=None,laj="circular"):
    #vrhovi grafova su numerirani prirodnim brojevima i nulom
    bridovi1=G1.edges(labels=False)
    bridovi2=G2.edges(labels=False)
    v1=G1.vertices()
    v2=G2.vertices()
    mogucnosti=Arrangements(v2,len(v1))
    mozeX=True
    for x in mogucnosti:
        podgraf_bridovi=[]
        podgraf_vrhovi=x
        mozeX=True
        for (y1,y2) in bridovi1:
            if ((x[y1],x[y2]) in bridovi2) or ((x[y2],x[y1]) in bridovi2):
                podgraf_bridovi.append((x[y1],x[y2]))
            else:
                mozeX=False
                break
        if mozeX: break
    if not(mozeX): return False
    if raspored_vrhova==None:
        slika=G2.plot(graph_border=True,edge_colors={"red":podgraf_bridovi},vertex_colors={"red":podgraf_vrhovi},layout=laj)
    else:
        slika=G2.plot(graph_border=True,edge_colors={"red":podgraf_bridovi},vertex_colors={"red":podgraf_vrhovi},pos=raspored_vrhova)
    return slika
In [188]:
gr1=Graph({0:[2,3,4],1:[2,3,4]})
gr2=Graph({0:[1,4,5],1:[2,3,5],2:[3,4],3:[4],4:[5]})
In [189]:
podgraf(gr1,gr2)
Out[189]:
In [190]:
podgraf(gr1,gr2,raspored_vrhova={0:[0,1],1:[1,0],2:[2,1],3:[2,2],4:[1,3],5:[0,2]})
Out[190]:

testirajmo našu funkciju i na prethodna dva zadatka

In [191]:
gr1=Graph({0:[1,3],1:[2],2:[3]})
gr2=Graph({0:[3,4],1:[2,3],2:[3,4],3:[4]})
slika=podgraf(gr1,gr2,raspored_vrhova={0:[1,-2],1:[3,-2],2:[4,1],3:[2,2],4:[0,1]})
graphics_array([gr1.plot(graph_border=True),gr2.plot(graph_border=True,pos={0:[1,-2],1:[3,-2],2:[4,1],3:[2,2],4:[0,1]}),
                slika]).show(figsize=[10,7])
In [192]:
gr1=Graph({0:[1,3],1:[2,3],2:[3]})
gr2=Graph({0:[4,5],1:[3,4],2:[3,4],4:[5]})
podgraf(gr1,gr2)
Out[192]:
False
In [193]:
graphics_array([gr1.plot(graph_border=True,pos={0:[0,0],1:[2,0],2:[2,2],3:[0,2]}),gr2.plot(graph_border=True,
                pos={0:[0,-2],1:[3,-2],2:[6,-2],3:[6,2],4:[3,2],5:[0,2]})])
Out[193]:

Korisna napomena

Želite li nešto više saznati o klasi Graph, možete napisati help(Graph) ili pak napisati Graph. (dakle, napisati Graph. i zatim pritisnuti tipku tab na tastaturi; na taj način dobivate implementirane metode na klasi Graph). Na primjer, jedna od njih je add_cycle pa ako želite nešto više o njoj saznati, napišete help(Graph.add_cycle). Isto tako, ako želite saznati koje su još vrste grafova spremljene u SAGE-u (osim onih koji su gore navedeni: potpuni graf, Petersenov graf,...) možete napisati graphs. (dakle, opet znači da treba pritisnuti tipku tab na tastaturi). Isto tako, ako je u varijablu G spremljen neki graf, možete napisati G. da vidite koje sve metode možete na njega primijeniti. Ova priča funkcionira i općenito u SAGE-u za bilo koje klase, a ne samo za grafove.

In [ ]: