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'})
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)]
graphics_array(lista1,1,4).show(figsize=[8,4])
Zadani su grafovi G1,G2,G3 i G4 na donjoj slici.
G1.bipartite_sets()
({'b', 'c'}, {'a', 'd', 'e'})
G2.bipartite_sets()
({'b', 'c', 'f'}, {'a', 'd', 'e'})
G3.is_bipartite()
False
G4.bipartite_sets()
({'a'}, {'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'})
G1.girth(), G2.girth(), G3.girth(), G4.girth()
(4, 6, 7, +Infinity)
G1.vertices()
['a', 'b', 'c', 'd', 'e']
A1 = G1.adjacency_matrix(); A1
[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]
A1^3
[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]
sum(sum(A1^3))
72
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]}
lista2 = [H1.plot(graph_border=True),H2.plot(graph_border=True),
H3.plot(pos=posH3,graph_border=True)]
graphics_array(lista2,1,3).show(figsize=[7,4])
Zadani su grafovi H1,H2 i H3 na donjoj slici.
H1.degree(), H2.degree()
([2, 2, 2, 2, 4], [2, 3, 3, 2])
H3.degree()
[3, 5, 5, 8, 3, 5, 3, 5, 3]
H1.is_eulerian(), H2.is_eulerian(), H3.is_eulerian()
(True, False, False)
H1.eulerian_circuit(labels=False,return_vertices=True)[1]
['a', 'e', 'c', 'b', 'e', 'd', 'a']
eulerova_staza(H2)
['b', 'a', 'c', 'b', 'd', 'c']
eulerova_staza(H3)
'Graf nema Eulerovu stazu'
H1.is_hamiltonian(),H2.is_hamiltonian(),H3.is_hamiltonian()
(False, True, True)
Riješite problem kineskog poštara u težinskom grafu
[R, S, B, P]
{(R, S): 11, (B, P): 9, (R, B): 11, (S, P): 8, (R, P): 10, (S, B): 17}
[([(R, S), (B, P)], 20), ([(R, B), (S, P)], 19), ([(R, P), (S, B)], 27)]
[A, S, E, P, S, P, D, F, B, C, R, C, B, D, R, A]
87
dict([(2*n, factorial(2*n) / (2**n * factorial(n)))
for n in range(1,11)])
{2: 1, 4: 3, 6: 15, 8: 105, 10: 945, 12: 10395, 14: 135135, 16: 2027025, 18: 34459425, 20: 654729075}
Pomoću poboljšane verzije Dijkstrinog algoritma pronađite najkraće putove od vrha R do svih preostalih vrhova u zadanom težinskom grafu.
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) | * |
Pomoću Floyd-Warshallovog algoritma odredite najkraće udaljenosti izmedu svaka dva vrha u težinskom grafu
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|