1. zadatak¶

Zadan je graf $G$ na donjoj slici.

  1. Napišite matricu susjedstva grafa $G$.
  2. Odredite stupnjeve svih vrhova u grafu $G$, ukupni broj petlji i ukupni broj višestrukih bridova koji nisu petlje.
  3. Pomoću matričnog teorema o stablima odredite ukupni broj razapinjućih stabala grafa $G$.
  4. Koliko ima ukupno neizomorfnih razapinjućih stabala od grafa $G$.
Out[3]:

Rješenje (matrica susjedstva)¶

Out[4]:
In [5]:
G.vertices()
Out[5]:
[a, b, c, d]
In [6]:
A = G.adjacency_matrix(); A
Out[6]:
[0 0 2 1]
[0 1 3 1]
[2 3 1 1]
[1 1 1 0]
Out[7]:
In [8]:
G.degree(labels=True)
Out[8]:
{a: 3, b: 6, c: 8, d: 3}
In [9]:
G.number_of_loops()
Out[9]:
2

Broj višestrukih bridova: 5

Rješenje (Matrični teorem o stablima)¶

Out[10]:
In [11]:
A1 = G1.adjacency_matrix(); A1
Out[11]:
[0 0 2 1]
[0 0 3 1]
[2 3 0 1]
[1 1 1 0]

Rješenje (Matrični teorem o stablima)¶

Out[12]:
In [13]:
A1 = G1.adjacency_matrix()
Q = G1.kirchhoff_matrix()
A1, Q
Out[13]:
(
[0 0 2 1]  [ 3  0 -2 -1]
[0 0 3 1]  [ 0  4 -3 -1]
[2 3 0 1]  [-2 -3  6 -1]
[1 1 1 0], [-1 -1 -1  3]
)
In [14]:
A1 = G1.adjacency_matrix()
Q = G1.kirchhoff_matrix()
A1, Q
Out[14]:
(
[0 0 2 1]  [ 3  0 -2 -1]
[0 0 3 1]  [ 0  4 -3 -1]
[2 3 0 1]  [-2 -3  6 -1]
[1 1 1 0], [-1 -1 -1  3]
)
In [15]:
Q.adjugate()
Out[15]:
[29 29 29 29]
[29 29 29 29]
[29 29 29 29]
[29 29 29 29]
In [16]:
G.spanning_trees_count()
Out[16]:
29

Graf $G$ od ukupno $29$ razapinjućih stabala, do na izomorfizam ima samo dvije klase neizomorfnih razapinjućih stabala.

Sva razapinjuća stabla grafa $G$

In [18]:
lista=[g.plot(vertex_size=30, vertex_labels=False,
              layout="circular",graph_border=True)
       for g in G.spanning_trees()]
graphics_array(lista,4,8)
Out[18]:
In [25]:
Td = Graph(DFS(G,'c')[1])
#Td.plot(layout='tree',tree_root='c',save_pos=True)
posTd = {'k': [1.0, -6],
         'g': [1.0, -5],
         'e': [0.0, -4],
         'b': [0.0, -3],
         'f': [1.0, -4],
         'h': [1.0, -3],
         'd': [0.5, -2],
         'a': [0.5, -1],
         'c': [0.5, 0]}
slikaTd = Td.plot(pos=posTd,figsize=[3.3,3.3])
rezDFS = DFS(G,'c')
pr2 = dict(rezDFS[1])
pr2['c'] = '-'
tablicaDFS = [['v'],['pi(v)'],['d(v)'],['f(v)']]
for v in G.vertex_iterator():
    tablicaDFS[0].append(v)
    tablicaDFS[1].append(pr[v])
    tablicaDFS[2].append(rezDFS[2][v])
    tablicaDFS[3].append(rezDFS[3][v])

2. zadatak¶

Zadan je graf $G$ na donjoj slici.

  1. Pomoću BFS algoritma odredite jedno razapinjuće stablo grafa $G$ tako da krenete od vrha $c$, a susjedne vrhove posjećujete po abecedi prema njihovim imenima. Nacrtajte pripadno korijensko BFS stablo. Odredite prethodnike svakog vrha i udaljenosti svih vrhova od vrha $c$ u zadanom grafu $G$.
  2. Pomoću DFS algoritma odredite jedno razapinjuće stablo grafa $G$ tako da krenete od vrha $c$, a susjedne vrhove posjećujete po abecedi prema njihovim imenima. Nacrtajte pripadno korijensko DFS stablo. Za svaki vrh odredite njegov prethodnik, trenutak kad je vrh prvi put posjećen i trenutak kada je DFS algoritam završio sa istraživanjem pojedinog vrha.
Out[26]:

BFS algoritam

Out[28]:
v cadfhkbeg
pi(v)-caaaccbk
d(v) 012221122

poredak vrhova: c, a, b, k, d, f, h, e, g

DFS algoritam

Out[30]:
v c a d f h k beg
pi(v)- c a a a c cbk
d(v) 1 2 3 9 8 114510
f(v) 1817161415127613

poredak vrhova: c, a, d, b, e, h, f, g, k

3. zadatak¶

Zadan je težinski graf $G$ na donjoj slici.

  1. Pomoću Kruskalovog algoritma pronađite minimalno i maksimalno razapinjuće stablo u zadanom težinskom grafu.
  2. Pomoću Primovog algoritma pronađite minimalno i maksimalno razapinjuće stablo u zadanom težinskom grafu. Algoritam počnite od vrha $c$.
Out[36]:

Kruskal (minimalno razapinjuće stablo)¶

Out[37]:
korak 1 2 3 4 5 6 7 8
brid (b, e)(a, d)(k, g)(k, a)(h, d)(a, c)(b, d)(g, f)
tezina2 3 3 3 4 5 5 6

težina stabla: 31

Kruskal (maksimalno razapinjuće stablo)¶

Out[39]:
korak 1 2 3 4 5 6 7 8
brid (a, f)(b, c)(k, c)(f, h)(g, f)(a, c)(b, d)(b, e)
tezina8 7 7 7 6 5 5 2

težina stabla: 47

Prim (minimalno razapinjuće stablo)¶

Out[41]:
c / korak1 2 3 4 5 6 7 8
brid (a, c)(a, d)(k, a)(k, g)(h, d)(b, d)(b, e)(g, f)
tezina 5 3 3 3 4 5 2 6

težina stabla: 31

Prim (maksimalno razapinjuće stablo)¶

Out[43]:
c / korak1 2 3 4 5 6 7 8
brid (b, c)(k, c)(a, c)(a, f)(f, h)(g, f)(b, d)(b, e)
tezina 7 7 5 8 7 6 5 2

težina stabla: 47

4. zadatak¶

Zadan je graf $G$ na donjoj slici.

  1. Dopušta li graf $G$ jaku orijentaciju? Obrazložite svoj odgovor.
  2. Odredite onu jaku orijentaciju na grafu $G-e$ koja se dobiva preko DFS algoritma koji počinje s vrhom $c$, a susjedne vrhove posjećuje po abecedi prema njihovim imenima.
Out[47]:

Graf $G$ ne dopušta jaku orijentaciju jer ima rezni brid $(b,e)$.

Jaka orijentacija na $G-e$

Out[48]:

Jaka orijentacija na $G-e$