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 G1,G2,G3 i G4 na donjoj slici.
- Ispitajte koji su od zadanih grafova bipartitni i odredite pripadnu biparticiju vrhova.
- Odredite strukove zadanih grafova.
- Napišite matricu susjedstva prvog grafa.
- Odredite ukupni broj svih (a,d)-šetnji duljine 3 u prvom grafu.
- 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 H1,H2 i H3 na donjoj slici.
- 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.
- 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.
- 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)¶
H1 ima Hamiltonov put, H2 i H3 imaju Hamiltonove cikluse¶
Diracov teorem¶
- δ(H1)=2, ν(H1)=5
- Ne vrijedi δ(H1)⩾ν2 pa ne možemo na temelju Diracovog teorema zaključiti je li H1 Hamiltonov graf ili nije.
- δ(H2)=2, ν(H2)=4
- Kako vrijedi δ(H2)⩾ν2, na temelju Diracovog teorema zaključujemo da je H2 Hamiltonov graf.
- δ(H3)=3, ν(H3)=9
- Ne vrijedi δ(H3)⩾ν2 pa ne možemo na temelju Diracovog teorema zaključiti je li H3 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?¶
(2n2)(2n−22)⋯(22)n!=(2n)!2n⋅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]:
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
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 ])