Grafovi za prvi zadatak (SAGE kod)¶

In [2]:
G1 = Graph({'a':['b','c'],'b':['d','e'],'c':['d','e']})
G2 = Graph({'a':['b','c'],'b':['d'],'c':['e'],'d':['f'],'e':['f']})
G3 = graphs.CycleGraph(7)
G3.relabel({0:'a',1:'b',2:'c',3:'d',4:'e',5:'f',6:'g'})
G4 = graphs.StarGraph(8)
G4.relabel({0:'a',1:'b',2:'c',3:'d',4:'e',5:'f',6:'g',7:'h',8:'i'})
In [3]:
lista1 = [G1.plot(layout="circular",graph_border=True),
          G2.plot(layout="circular",graph_border=True),
          G3.plot(layout="circular",graph_border=True),
          G4.plot(graph_border=True)]
In [4]:
graphics_array(lista1,1,4).show(figsize=[8,4])

1. zadatak¶

Zadani su grafovi $G_1, G_2, G_3$ i $G_4$ na donjoj slici.

  1. Ispitajte koji su od zadanih grafova bipartitni i odredite pripadnu biparticiju vrhova.
  2. Odredite strukove zadanih grafova.
  3. Napišite matricu susjedstva prvog grafa.
  4. Odredite ukupni broj svih (a,d)-šetnji duljine 3 u prvom grafu.
  5. Odredite ukupni broj svih šetnji duljine 3 u prvom grafu.

Rješenje (bipartitnost grafa G1)¶

In [7]:
G1.bipartite_sets()
Out[7]:
({'b', 'c'}, {'a', 'd', 'e'})

Rješenje (bipartitnost grafa G2)¶

In [9]:
G2.bipartite_sets()
Out[9]:
({'b', 'c', 'f'}, {'a', 'd', 'e'})

Rješenje (bipartitnost grafa G3)¶

In [11]:
G3.is_bipartite()
Out[11]:
False

Rješenje (bipartitnost grafa G4)¶

In [13]:
G4.bipartite_sets()
Out[13]:
({'a'}, {'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'})

Rješenje (strukovi grafova)¶

In [15]:
G1.girth(), G2.girth(), G3.girth(), G4.girth()
Out[15]:
(4, 6, 7, +Infinity)

Rješenje (Matrica susjedstva grafa G1)¶

In [17]:
G1.vertices()
Out[17]:
['a', 'b', 'c', 'd', 'e']

Rješenje (Matrica susjedstva grafa G1)¶

In [19]:
A1 = G1.adjacency_matrix(); A1
Out[19]:
[0 1 1 0 0]
[1 0 0 1 1]
[1 0 0 1 1]
[0 1 1 0 0]
[0 1 1 0 0]

broj svih (a,d)-šetnji duljine 3 u G1¶

In [20]:
A1^3
Out[20]:
[0 6 6 0 0]
[6 0 0 6 6]
[6 0 0 6 6]
[0 6 6 0 0]
[0 6 6 0 0]

ukupni broj svih šetnji duljine 3 u G1¶

In [21]:
sum(sum(A1^3))
Out[21]:
72

Grafovi za drugi zadatak (SAGE kod)¶

In [22]:
H1 = graphs.ButterflyGraph()
H2 = graphs.DiamondGraph()
H3 = graphs.KingGraph([3,3])
H1.relabel({0:'a',1:'b',2:'c',3:'d',4:'e'})
H2.relabel({0:'a',1:'b',2:'c',3:'d'})
H3.relabel(['a','b','c','d','e','f','g','h','k'])
posH3 = {'a':[0,0],'b':[1,0],'c':[2,0],'d':[0,1],'e':[1,1],
         'f':[2,1],'g':[0,2],'h':[1,2],'k':[2,2]}
In [23]:
lista2 = [H1.plot(graph_border=True),H2.plot(graph_border=True),
          H3.plot(pos=posH3,graph_border=True)]
In [24]:
graphics_array(lista2,1,3).show(figsize=[7,4])

2. zadatak¶

Zadani su grafovi $H_1, H_2$ i $H_3$ na donjoj slici.

  1. Ispitajte jesu li zadani grafovi Eulerovi. Ukoliko je neki od grafova Eulerov, odredite u njemu jednu Eulerovu turu. Ukoliko neki od grafova nije Eulerov, ispitajte ima li Eulerovu stazu.
  2. Ispitajte jesu li zadani grafovi Hamiltonovi. Ukoliko je neki od grafova Hamiltonov, odredite u njemu jedan Hamiltonov ciklus. Ukoliko neki od grafova nije Hamiltonov, ispitajte ima li Hamiltonov put.
  3. Može li se pomoću Diracovog teorema za neki od grafova zaključiti je li Hamiltonov?

Rješenje (jesu li grafovi Eulerovi)¶

In [27]:
H1.degree(), H2.degree()
Out[27]:
([2, 2, 2, 2, 4], [2, 3, 3, 2])
In [28]:
H3.degree()
Out[28]:
[3, 5, 5, 8, 3, 5, 3, 5, 3]

Rješenje (jesu li grafovi Eulerovi)¶

In [30]:
H1.is_eulerian(), H2.is_eulerian(), H3.is_eulerian()
Out[30]:
(True, False, False)
In [31]:
H1.eulerian_circuit(labels=False,return_vertices=True)[1]
Out[31]:
['a', 'e', 'c', 'b', 'e', 'd', 'a']

Eulerova staza¶

In [35]:
eulerova_staza(H2)
Out[35]:
['b', 'a', 'c', 'b', 'd', 'c']
In [36]:
eulerova_staza(H3)
Out[36]:
'Graf nema Eulerovu stazu'

Rješenje (jesu li grafovi Hamiltonovi)¶

In [38]:
H1.is_hamiltonian(),H2.is_hamiltonian(),H3.is_hamiltonian()
Out[38]:
(False, True, True)

Rješenje (jesu li grafovi Hamiltonovi)¶

$H_1$ ima Hamiltonov put, $H_2$ i $H_3$ imaju Hamiltonove cikluse¶

Diracov teorem¶

  • $\delta(H_1)=2,\ \nu(H_1)=5$
  • Ne vrijedi $\delta(H_1)\geqslant\frac{\nu}{2}$ pa ne možemo na temelju Diracovog teorema zaključiti je li $H_1$ Hamiltonov graf ili nije.
  • $\delta(H_2)=2,\ \nu(H_2)=4$
  • Kako vrijedi $\delta(H_2)\geqslant\frac{\nu}{2}$, na temelju Diracovog teorema zaključujemo da je $H_2$ Hamiltonov graf.
  • $\delta(H_3)=3,\ \nu(H_3)=9$
  • Ne vrijedi $\delta(H_3)\geqslant\frac{\nu}{2}$ pa ne možemo na temelju Diracovog teorema zaključiti je li $H_3$ Hamiltonov graf ili nije.

3. zadatak¶

Riješite problem kineskog poštara u težinskom grafu

Out[47]:
Out[48]:

Vrhovi neparnog stupnja¶

Out[49]:
[R, S, B, P]
Out[50]:

Udaljenosti između vrhova neparnog stupnja i uparivanja¶

{(R, S): 11, (B, P): 9, (R, B): 11, (S, P): 8, (R, P): 10, (S, B): 17}
Out[52]:
[([(R, S), (B, P)], 20), ([(R, B), (S, P)], 19), ([(R, P), (S, B)], 27)]
Out[53]:

Eulerova tura u pseudografu i težina optimalne ture¶

[A, S, E, P, S, P, D, F, B, C, R, C, B, D, R, A]
Out[55]:
87

Koliko ima različitih uparivanja ako u grafu ima ukupno $2n$ vrhova neparnog stupnja?¶

$$\frac{\binom{2n}{2}\binom{2n-2}{2}\dotsb\binom{2}{2}}{n!}=\frac{(2n)!}{2^n\cdot n!}$$
  • Dijelimo s $n!$ jer nam nije bitan poredak parova.
In [56]:
dict([(2*n, factorial(2*n) / (2**n * factorial(n))) 
      for n in range(1,11)])
Out[56]:
{2: 1,
 4: 3,
 6: 15,
 8: 105,
 10: 945,
 12: 10395,
 14: 135135,
 16: 2027025,
 18: 34459425,
 20: 654729075}

4. zadatak¶

Pomoću poboljšane verzije Dijkstrinog algoritma pronađite najkraće putove od vrha $R$ do svih preostalih vrhova u zadanom težinskom grafu.

Out[58]:

Ručni postupak¶

Out[59]:
0 1 2 3 4 5 6 7 8
A('-', '∞')(R, 2) * * * * * * *
B('-', '∞')('-', '∞')('-', '∞')(D, 13) (C, 11) (C, 11) (C, 11)* *
C('-', '∞')(R, 6) (R, 6) (R, 6) * * * * *
D('-', '∞')(R, 6) (R, 6) * * * * * *
E('-', '∞')('-', '∞')('-', '∞')('-', '∞')('-', '∞')('-', '∞')(P, 19)(P, 19)(S, 18)
F('-', '∞')('-', '∞')('-', '∞')(D, 8) (D, 8) * * * *
P('-', '∞')('-', '∞')('-', '∞')(D, 10) (D, 10) (D, 10) * * *
R('-', 0) * * * * * * * *
S('-', '∞')('-', '∞')(A, 11) (A, 11) (A, 11) (A, 11) (A, 11)(A, 11)*

Stablo najkraćih putova¶

Out[60]:

5. zadatak¶

Pomoću Floyd-Warshallovog algoritma odredite najkraće udaljenosti izmedu svaka dva vrha u težinskom grafu

Out[63]:
Out[64]:
Out[65]:
k=0 \(u_{1}\) \(u_{2}\) \(u_{3}\) \(u_{4}\)
\(u_{1}\) \(0\) \(3\) \(5\) \(+\infty\)
\(u_{2}\) \(3\) \(0\) \(1\) \(7\)
\(u_{3}\) \(5\) \(1\) \(0\) \(2\)
\(u_{4}\) \(+\infty\) \(7\) \(2\) \(0\)
k=1 \(u_{1}\) \(u_{2}\) \(u_{3}\) \(u_{4}\)
\(u_{1}\) \(0\) \(3\) \(5\) \(+\infty\)
\(u_{2}\) \(3\) \(0\) \(1\) \(7\)
\(u_{3}\) \(5\) \(1\) \(0\) \(2\)
\(u_{4}\) \(+\infty\) \(7\) \(2\) \(0\)
k=2 \(u_{1}\) \(u_{2}\) \(u_{3}\) \(u_{4}\)
\(u_{1}\) \(0\) \(3\) \(4\) \(10\)
\(u_{2}\) \(3\) \(0\) \(1\) \(7\)
\(u_{3}\) \(4\) \(1\) \(0\) \(2\)
\(u_{4}\) \(10\) \(7\) \(2\) \(0\)
k=3 \(u_{1}\) \(u_{2}\) \(u_{3}\) \(u_{4}\)
\(u_{1}\) \(0\) \(3\) \(4\) \(6\)
\(u_{2}\) \(3\) \(0\) \(1\) \(3\)
\(u_{3}\) \(4\) \(1\) \(0\) \(2\)
\(u_{4}\) \(6\) \(3\) \(2\) \(0\)
k=4 \(u_{1}\) \(u_{2}\) \(u_{3}\) \(u_{4}\)
\(u_{1}\) \(0\) \(3\) \(4\) \(6\)
\(u_{2}\) \(3\) \(0\) \(1\) \(3\)
\(u_{3}\) \(4\) \(1\) \(0\) \(2\)
\(u_{4}\) \(6\) \(3\) \(2\) \(0\)