Read Microsoft Word - Metricki problemi u teoriji grafova.doc text version

Alen Selimbegovi

Metricki problemi u teoriji grafova

Poslijediplomski studij Seminarski rad Prof. Nagli: Grafovi i mreze

Zagreb,

Sijecanj, 2005.

Sadrzaj

Sadrzaj.......................................................................................................................................... 2 Uvod ............................................................................................................................................. 3 Izabrani osnovni pojmovi............................................................................................................. 4 Graf........................................................................................................................................... 4 Povezanost grafa ...................................................................................................................... 6 Posebne vrste grafova............................................................................................................... 7 Metrika grafa .............................................................................................................................. 10 Tezinski grafovi...................................................................................................................... 11 Odreivanje najkraeg i najduzeg puta u grafu.......................................................................... 13 Dijkstrin algoritam ................................................................................................................. 13 Bellman-Ford algoritam ......................................................................................................... 14 A* algoritam........................................................................................................................... 15 Stablo minimalne duljine ........................................................................................................... 18 Prim-Jarnikov algoritam......................................................................................................... 18 Kruskalov algoritam............................................................................................................... 19 Usporedba algoritama ............................................................................................................ 19 Steinerov problem .................................................................................................................. 21 Ostali metricki problemi............................................................................................................. 22 Problem trgovackog putnika .................................................................................................. 22 Problem kineskog postara ...................................................................................................... 24 Zadaci ......................................................................................................................................... 25 1. Zadatak ............................................................................................................................... 25 2. Zadatak ............................................................................................................................... 26 3. Zadatak ............................................................................................................................... 27 4. Zadatak ............................................................................................................................... 29 5. Zadatak ............................................................................................................................... 29 6. Zadatak ............................................................................................................................... 34 Literatura i ostali izvori .............................................................................................................. 38

Metricki problemi u teoriji grafova

2

Uvod

Tema seminara izabrani su metricki problemi u teoriji grafova. Na pocetku definirani su pojedini osnovni pojmovi teorije grafova koji se koriste u drugim poglavljima. Slijedea poglavlja govore o metrici grafa, odreivanju najkraeg i najduzeg puta u grafu, sintezi stabla minimalne duzine i ostalim metrickim problemima u teoriji grafova. Na kraju su predstavljeni i rijeseni izabrani zadaci iz teme seminara. Svi primjeri su obraeni i demonstrirani koristei Wolfram Mathematica® 5.0 okruzenje, cija je najbolja primjena u simbolickoj matematici i vizualizaciji matematickih problema.

Metricki problemi u teoriji grafova

3

Izabrani osnovni pojmovi

Graf

Kartezijev produkt dvaju skupova X i Y definira se kao:

X × Y = {( x, y ) x X y Y } .......................................................................................... (1)

Skup X × X oznacava se sa X 2 Binarna relacija u skupu X je svaki podskup skupa X 2 tj. svaki skup za koji vrijedi

X 2 ............................................................................................................................ (2)

Neka je V neprazan skup i binarna relacija u skupu V. Ureen par G=(V, ) naziva se graf (graph). Elementi skupa V su cvorovi grafa G (vertices, nodes, points), a elementi skupa grane grafa G (edges, arcs, lines). Oznacavamo cvorove grafa G sa V(G), a grane sa E(G).

Primjer 1:

<<DiscreteMath`Combinatorica` ?RandomGraph [email protected], pD constructs a random labeled graph on n vertices with an edge probability of p. An option Type is provided, which can take on values Directed and Undirected, and whose default value is Undirected. Type->Directed produces a corresponding random directed graph. The usages [email protected], p, DirectedD, [email protected], p, rangeD, and [email protected], p, range, DirectedD are all obsolete. Use SetEdgeWeights to set random edge weights. More... g = RandomGraph[8,.3] Graph:< 6 , 8 , Undirected > ?ShowGraph [email protected] displays the graph g. [email protected], optionsD modifies the display using the given options. [email protected], DirectedD is obsolete and it is currently identical to [email protected] All options that affect the look of a graph can be specified as options in ShowGraph. The list of options is: VertexColor, VertexStyle, VertexNumber, VertexNumberColor, VertexNumberPosition, VertexLabel, VertexLabelColor, VertexLabelPosition, EdgeColor, EdgeStyle, EdgeLabel, EdgeLabelColor, EdgeLabelPosition, LoopPosition, and EdgeDirection. In addition, options of the Mathematica function Plot and options of the graphics primitive Arrow can also be specified here. If an option specified in ShowGraph differ from options explicitly set within a graph object, then options specified inside the graph object are used. More...

Metricki problemi u teoriji grafova

4

ShowGraph[g,VertexNumberTrue,VertexNumberColorRed,VertexNumberPositionUpp erLeft,EdgeColorBlue]

2 3 1

4

8

5 6

7

?ToOrderedPairs [email protected] constructs a list of ordered pairs representing the edges of the graph g. If g is undirected each edge is interpreted as two ordered pairs. An option called Type that takes on values Simple or All can be used to affect the constructed representation. Type -> Simple forces the removal of multiple edges and self-loops. Type -> All keeps all information and is the default option. More... ToOrderedPairs[g] {{3,2},{4,1},{4,3},{5,4},{6,2},{6,4},{7,6},{8,2},{8,7},{2,3},{1,4},{3,4},{4, 5},{2,6},{4,6},{6,7},{2,8},{7,8}}

Graf G=(V, ) je simetrican ili neorijentiran ako i samo ako je simetricna relacija. Graf G=(V, ) je antisimetrican ili orijentiran ako i samo ako je antisimetricna relacija. Drugi naziv za orijentirani graf je digraf. Dva grafa G1 i G2 su izomorfni (pisemo G1 G2 ), ako postoji bijekcija cvorova koja cuva susjednost. Zanimljivo je da nije naen P-kompletan algoritam za testiranje izomorfizama grafova, ali nije dokazano niti da je to NP-problem. Pretpostavlja se da ovaj problem ne pripada niti u Pkompletne niti u NP-kompletne, tako da se uvodi nova klasa kompleksnosti problema ­ izomorfizam-grafa-kompletni problemi.

Primjer 2:

?IsomorphicQ

[email protected], hD yields True if graphs g and h are isomorphic. This function takes an option Invariants -> 8f1, f2, ...<, where f1, f2, ... are functions that are used to compute vertex invariants. These functions are used in the order in which they are specified. The default value of Invariants is 8DegreesOf2Neighborhood, NumberOf2Paths, Distances<. More...

?Isomorphism

Metricki problemi u teoriji grafova

5

g=AddEdges[EmptyGraph[6],{{1,4},{1,5},{1,6},{2,5},{2,6},{3,6},{4,6},{5,6}}] Graph:< 8 , 6 , Undirected > h=AddEdges[EmptyGraph[6],{{4,1},{4,2},{4,3},{6,2},{6,3},{5,3},{1,3},{2,3}}] Graph:< 8 , 6 , Undirected > ShowGraphArray[{g,h}]

[email protected], hD gives an isomorphism between graphs g and h if one exists. [email protected], h, AllD gives all isomorphisms between graphs g and h. [email protected] gives the automorphism group of g. This function takes an option Invariants -> 8f1, f2, ...<, where f1, f2, ... are functions that are used to compute vertex invariants. These functions are used in the order in which they are specified. The default value of Invariants is 8DegreesOf2Neighborhood, NumberOf2Paths, Distances<. More...

GraphicsArray IsomorphicQ[g,h] True Isomorphism[g,h] {2,1,5,6,4,3}

Povezanost grafa

Matrica povezanosti (adjacency matrix) grafa A je kvadratna matrica ciji su stupci oznaceni sa cvorovima grafa, a elementi poprimaju vrijednosti 1 ili 0 na poziciji (vi,vj) ako su cvorovi vi i vj povezani ili ne.

Primjer 3:

?ToAdjacencyMatrix [email protected] constructs an adjacency matrix representation for graph g. An option Type that takes on values All or Simple can be used to affect the matrix constructed. Type -> All is the default, and Type -> Simple ignores any self-loops or multiple edges g may have. [email protected], EdgeWeightD returns edge weights as entries of the adjacency matrix with Infinity representing missing edges. More... ?MatrixForm [email protected] prints with the elements of list arranged in a regular array.

More...

MatrixForm[ToAdjacencyMatrix[g]]

Metricki problemi u teoriji grafova

6

Matrica povezanosti A neorijentiranog grafa je simetricna matrica, tj. A = At . Matrica povezanosti A orijentiranog grafa ima slijedee svojstvo:

i0 j j0 j j j j0 j j j j0 j j j j0 j j j j1 j j j j0 j j j k1

0 0 0 0 1 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 1 0 0 0

0 1 1 1 0 0 0 0

1 0 0 0 0 0 1 0

0 0 0 0 0 1 0 0

1y z z 0z z z z 0z z z z 0z z z z 0z z z z 0z z z z 0z z z 0{

(i, j {1,K, n}) aij

= 1 a ji = 0 (i j ) ................................................................... (3)

Put (path) duljine k je svaki niz grana koji ima slijedea svojstva:

1º grana e1 polazi iz proizvoljnog cvora, 2º grana ei (i = 2, ..., k) pocinje u onom cvoru u kojemu zavrsava grana ui-1.

Lanac duljine k je naizmjenicni niz cvorova i grana v1, e1, v2, e2,..., vk, ek, vk+1 takav da za svaki i=1, 2, ..., k cvorovi xi i xi+1 meusobno su razliciti i predstavljaju krajnje tocke grane ei.

Neorijentirani graf je povezan graf (connected graph) ako se svaka dva njegova cvora mogu povezati putem (ili lancem). Dva cvora neorijentiranog grafa kazemo da su susjedni cvorovi (adjacent vertices), ako su spojena granom. Stupanj cvora je broj susjednih cvorova. Neorijentiran graf je regularan (pravilan) stupnja r, ukoliko su stupnjevi svih cvorova jednaki r. Povezan graf stupnja 2 zove se ciklus, petlja ili kontura (circuit). Druga definicija ciklusa je zatvoreni put (put kojemu su isti pocetni i zavrsni cvor).

Eulerov ciklus je ciklus koji prolazi svakom granom tocno jedamput. Graf koji ima Eulerov ciklus zove se Eulerov graf (dokazuje se da je to ekvivalentno povezanom grafu kojemu su svi cvorovi parnog stupnja). Hamiltonov put je put koji sadrzi sve cvorove grafa, a Hamiltonov ciklus je ciklus koji sadrzi sve cvorove grafa.

Posebne vrste grafova

Graf bez ciklusa naziva se aciklicki graf (acyclic graph). Regularan graf sa n cvorova stupnja n-1 zove se potpun graf (complete graph). Kod njega su svi cvorovi meusobno povezani. Povezani graf koji ne sadrzi petlju zovemo stablo (tree). Broj grana stabla je n-1.

Metricki problemi u teoriji grafova

7

Zvijezda (star) je stablo sa n+1 cvorova koje ima tocno jedan cvor stupnja n i sve ostale stupnja 1.

Primjer 4:

?CompleteGraph [email protected] creates a complete graph on n vertices. An option Type that takes on the values Directed or Undirected is allowed. The default setting for this option is Type -> Undirected. [email protected], b, c,...D creates a complete k-partite graph of the prescribed shape. The use of CompleteGraph to create a complete k-partite graph is obsolete; use CompleteKPartiteGraph instead. More... ShowGraph[CompleteGraph[6],EdgeColorBlue]

Graphics ?RandomTree [email protected] constructs a random labeled tree on n vertices. More... ShowGraph[RandomTree[10],EdgeColorBlue]

Graphics ?Star [email protected] constructs a star on n vertices, which is a tree with one vertex of degree n-1. More... ShowGraphArray[Table[Star[n],{n,7}],VertexStyle->Disk[.1],EdgeColorBlue]

Metricki problemi u teoriji grafova

8

GraphicsArray

Komplement G grafa G je neorijentirani graf bez petlji, koji ima iste cvorove kao i graf G, pri cemu su dva, meusobno razlicita cvora, susjedna u G ako i samo ako nisu susjedna u G. Unija grafa i njegovog komplementa cini potpuni graf.

Graf G je samokomplementan (self-complementary) ako je izomorfan svom komplementu G .

Primjer 5:

g1 = RandomGraph[8,.3,EdgeColorRed] Graph:< 9 , 8 , Undirected > ?GraphComplement [email protected] gives the complement of graph g. More... g2 = GraphComplement[g1] Graph:< 17 , 8 , Undirected > ShowGraphArray[{ g1, SetGraphOptions[g2,EdgeColorBlue], SetGraphOptions[GraphSum[g1,g2], Join[Edges[g2],{EdgeColorBlue}]]},VertexStyleDisk[.05]]

GraphicsArray

Metricki problemi u teoriji grafova

9

Metrika grafa

S obzirom na povezanost cvorova povezanog neorjentiranog grafa G, mozemo definirati metriku na ovaj nacin: · d (vi , vi ) = 0 vi V (G ) · d (vi , v j ) = u vi , v j V (G ) vi v j , gdje je u duljina najkraeg puta od vi do vj. Lako je dokazati da ovako definrana metrika zadovoljava aksiome metrike: 1º d (vi , v j ) = 0 i = j

(jednoznacnost) (simetricnost) (nejednakost trokuta)

2º d (vi , v j ) = d (v j , vi ) 3º d (vi , vk ) + d (vk , v j ) d (vi , v j )

Mozemo prosiriti definiciju metrike i za nepovezane grafove. Za cvorove vi i vj koji nisu meusobno povezani, definiramo: d (vi , v j ) = + ................................................................................................................... (5)

Ekscentricnost cvora vi definiramo kao maksimalnu udaljenost svih cvorova grafa G od cvora vi: eks(vi ) = max {d (vi , v j ) v j V (G )}................................................................................. (6) Dijametar grafa G definiramo kao maksimalnu udaljenost dva cvora u grafu: d (G ) = max {eks(vi ) vi V (G )} ...................................................................................... (7)

Odnosno: d (G ) = max {d (vi , v j ) vi , v j V (G )} ............................................................................... (8)

Radijus grafa G definiramo kao minimalnu ekscentricnost svih cvorova grafa G: r (G ) = min {eks(vi ) vi V (G )} ....................................................................................... (8)

Krae pisemo: r (G ) = min max d (vi , v j ) .............................................................................................. (9)

viV ( G ) v j V ( G )

Primjer 6:

g1 = RandomGraph[12,.2] Graph:< 16 , 12 , Undirected > ShowGraph[g1,EdgeColorBlue]

Metricki problemi u teoriji grafova

10

Graphics ?Eccentricity [email protected] gives the eccentricity of each vertex v of graph g, the maximum length among all shortest paths from v. More... Eccentricity[g1] {4,4,3,3,4,3,3,3,4,5,5,5} Max[Eccentricity[g1]] 5 ?Diameter [email protected] gives the diameter of graph g, the maximum length, among all pairs of vertices in g, of a shortest path between each pair. More... Diameter[g1] 5 Min[Eccentricity[g1]] 3 ?Radius [email protected] gives the radius of graph g, the minimum eccentricity of any vertex of g.

More...

Radius[g1] 3

Tezinski grafovi

Ukoliko svakom bridu e E (G ) pridruzimo tezinu w(e), graf G, zajedno sa funkcijom w, zove se tezinski graf. Ukoliko su tezine pozitivni realni brojevi, a graf je bez petlji, mozemo definirati udaljenost kao metriku na slijedei nacin: · duljina puta je suma svih tezina na putu, · udaljenost cvorova je duljina minimalnog puta izmeu dva cvora, · udaljenost cvora od samog sebe je 0.

Ako postavimo sve tezine na 1, dobijamo metriku istuvjetnu kao i kod grafa bez tezina. Ako imamo cikluse ili negativne tezine, onda ovako definirana udaljenost nije metrika.

Primjer 7:

?SetEdgeWeights

Metricki problemi u teoriji grafova

11

g1=SetEdgeWeights[RandomGraph[8,.15],WeightingFunctionRandomInteger,WeightR ange{10,40}] Edges[g1,EdgeWeight] {{{1,3},14},{{1,4},28},{{3,6},24},{{2,7},35},{{4,8},27}} w1=Last/@Sort[Transpose[{Edges[g1],GetEdgeWeights[g1]}]] {14,11,21,32} ShowGraph[g1,EdgeLabelw1,VertexNumberTrue,EdgeColorBlue]

2

[email protected] assigns random real weights in the range @0, 1D to edges in g. SetEdgeWeights accepts options WeightingFunction and WeightRange. WeightingFunction can take values Random, RandomInteger, Euclidean, or [email protected] for nonnegative n, or any pure function that takes two arguments, each argument having the form 8Integer, 8Number, Number<<. WeightRange can be an integer range or a real range. The default value for WeightingFunction is Random and the default value for WeightRange is @0, 1D. [email protected], eD assigns edge weights to the edges in the edge list e. [email protected], wD assigns the weights in the weight list w to the edges of g. [email protected], e, wD assigns the weights in the weight list w to the edges in edge list e. More...

3

14

1

28 35 4 24 27 8

5

7

6

Graphics

Metricki problemi u teoriji grafova

12

Odreivanje najkraeg i najduzeg puta u grafu

Cesto se u primjeni teorije grafova treba odrediti najkrai put izmeu dva cvora u tezinskom grafu. Najcese primjene su u odreivanju najkrae rute izmeu dva grada (gdje se moze traziti i put sa najmanjom potrosnjom goriva ili slicno). Isto tako postoje i primjene gdje se trazi najduzi put izmeu dva cvora ­ tipicno kod odreivanja kriticnog puta u mreznom planiranju. Najpopularniji algoritam ovog tipa je Dijkstrin algoritam (Edsger Dijkstra, Nizozemska, 19302002).

Dijkstrin algoritam

Dijkstrin algoritam vrijedi i za orijentirane i za neorijentirane povezane grafove sa nenegativnim tezinama grana. Ovaj algoritam nam daje najkrai put od zadanog cvora do svih preostalih cvorova u grafu. Opisimo algoritam u pseudo-kodu.

Algoritam 1:

Dijkstra_najkrai_put(Graf g, Cvor v0) pocetak -- pocetno stanje za svaki vi iz Cvorovi(g) radi pocetak d[vi]:= p[vi]:=Ø kraj d[v0] := 0 ­- duljina puta od cvora v0 do cvora v0 je nula S := Ø -- inicijalno nismo odradili niti jedan cvor Q := Cvorovi(g) -- ostali su svi cvorovi za odraditi -- glavna petlja sve dok Q Ø radi pocetak izaberi u iz Q takav da je ­- naimo pivot cvor d[u] = min {d[vi]} za svaki vi iz Q S := S {u} ­- pivot cvor proglasimo odraeni Q := Q \{u} ­- pivot cvor izbacimo iz popisa neodraenih za svaki vi iz Q radi ­- svim preostalim cvorovima azuriraj udaljenosti ako je d[vi] > d[u]+w(u,vi) onda pocetak p[v i] := u -­ promijenio se prethodni cvor d[vi] := d[u]+w(u,vi) ­ promijenila se udaljenost kraj kraj kraj

Metricki problemi u teoriji grafova

13

Proceduri predajemo graf g i cvor v0 od kojeg zelimo nai sve najkrae putove. Kao rezultat algoritma u polju d dobivamo duljine najkraeg puta do pojedinog, a u polju p prethodnika pojedinog cvora u najkraim putovima. U polju S cuvamo rijesene, a u polju Q nerijesene cvorove. U varijabli u imamo trenutni cvor od kojega gledamo udaljenosti (pivot cvor). U inicijalizaciji postavljamo da je udaljenost do svakog cvora beskonacna (tako da prvi put do tog cvora bude krai od pocetne vrijednosti i da nema prethodnika), osim do pocetnog koja je trivijalno nula. Skup rijesenih cvorova pocetno je prazan (S := Ø), a skup nerijesenih svi ostali cvorovi (Q := Cvorovi(g)). U glavnoj petlji za slijedei pivot cvor, izaberemo cvor sa minimalnom evidentiranom udaljenosu (d[u] = min {d[vi]} za svaki vi iz Q) , dodajemo ga u skup rijesenih (S := S {u}) i izbacujemo iz skupa nerijesenih (Q := Q \{u}). Svakom cvoru vi iz Q koji je blizi cvoru u nego sto je za dati cvor evidentirano (ako je d[vi] > d[u]+w(u,vi) onda), pridruzimo cvor u kao prethodnika (p[v i] := u) i udaljenost od pocetnog cvora preko cvora u (d[vi] := d[u]+w(u,vi)). Ukoliko zelimo da Dijkstrin algoritam radi i za nepovezane grafove, onda trebamo dodati kontrolu u trazenju sljedeeg pivot cvora, da ukoliko su sve preostale evidentirane udaljenosti beskonacne, da se izae iz petlje. Kompleksnost Dijkstrinog algoritama moze se lako pronai. Vanjska glavna petlja je reda O(n), jer se svaki cvor tocno jednom uzima za pivota. Za svaki pivot cvor gledamo susjedne cvorove i odreujemo nove udaljenosti (kroz cijelu glavnu petlju radimo sve skupa m puta), tako da je kompleksnost sada O(n+m). Najvei posao je u odreivanju slijedeeg pivot cvora i kompleksnost ovisi o strukturi podataka koju koristimo za polje udaljenosti. Ako je polje jednostavna linearna struktura, onda je trazenje pivot cvora kompleksnosti O(n) i ukupna kompleksnost algoritma je O(n2). Ako je polje slozenije strukturu, (npr. red sa prioritetima, Fibonacci heap, gdje je kompleksnost trazenja pivot cvora O(ln(n)), konacna kompleksnost algoritma je O(m+n·ln(n)). Ako zelimo kompleksnost izraziti ovisnu samo o broju cvorova, moramo uzeti najtezi slucaj, a to je potpuni graf. Kompleksnost Dijkstrinog algoritama tada iznosi O(n2).

Bellman-Fordov algoritam

U slucaju kad imamo i grane sa negativnim tezinama, Dijkstrin algoritam moramo zamijeniti sa Bellman-Fordovim algoritmom.

Algoritam 2:

Bellman_Ford_najkrai_put(Graf g, Cvor v0) pocetak -- pocetno stanje za svaki vi iz Cvorovi(g) radi

Metricki problemi u teoriji grafova

14

pocetak d[vi]:= p[vi]:=Ø kraj d[v0] := 0 ­- duljina puta od cvora v0 do cvora v0 je nula Q := Cvorovi(g) -- ostali su svi cvorovi za odraditi -- glavna petlja za i od 1 do Broj_cvorova(g) radi pocetak za svaki ei(u,v) iz Grane(g) radi ako je d[v] > d[u]+w(u,v) onda pocetak p[v] := u -­ promijenio se prethodni cvor d[v] := d[u]+w(u,v) ­ promijenila se udaljenost kraj kraj za svaki ei(u,r) iz Grane(g) radi ako je d[r] > d[u]+w(u,r) onda vrati krivo ­ postoji ciklus sa negativnom tezinom kraj

Kompleksnost Bellman-Fordovog algoritma je O(m·n) (vanjska petlja se vrti n puta, a unutarnja m puta), a za najgori slucaj potpunog grafa ona iznosi O(n3). Primjena ovog algoritma je u RIP protokolu (Routing Information Protocol) koji omoguava routerima na Internetu dinamicko prilagoivanje promjenama mreznih veza.

A* algoritam

Ovaj heuristicki algoritam koristi se u slucajevima gdje imamo jako velik broj cvorova, ali u grafu postoji struktura koja nam daje sugestije u kojem je smjeru najvjerojatniji najkrai put (tipicno u planarnim grafovima). Ukoliko A* algoritam nikad ne pretpostavlja veu od stvarne udaljenosti od ciljnog cvora, onda on svojim heuristickim rjesenjem daje ujedno i optimalni put.

Algoritam 3:

A_zvijezda_najkrai_put(Graf g, Cvor v0, Cvor vx) pocetak -- pocetno stanje S := Ø -- inicijalno nismo odradili niti jedan cvor Q := {v0} -- kreemo od prvog cvora f[v0] := 0 -- glavna petlja sve dok Q Ø radi

Metricki problemi u teoriji grafova

15

pocetak izaberi u iz Q takav da je ­- naimo slijedei pivot cvor f[u] = min {f[vi]} za svaki vi iz Q Q := Q \{u} ­- pivot cvor izbacimo iz popisa neodraenih S := S {u} ­ ubacimo pivot cvor u popis odraenih ako je u = vx onda zavrsi za svaki vi povezan sa u radi pocetak h_t[vi] := Heuristicki(vi) -- procjena udaljenosti do ciljnog cvora g_t[vi] := g[u]+w(u,vi) f_t[vi] := g_t[vi]+g_t[vi] ako je vi iz Q i f_t[vi] < f[vi] onda ignoriraj ako je vi iz S i f_t[vi] < f[vi] onda ignoriraj inace Q := Q \{vi} S := S \{vi} h[vi] := h_t[vi] -- procjena udaljenosti do ciljnog cvora g[vi] := g_t[vi] f[vi] := f_t[vi] Q := Q {vi} p[vi] := u

kraj kraj

Primjer 8:

g=SetEdgeWeights[RandomGraph[8,.4],WeightingFunctionRandomInteger,WeightRan ge{1,20}] Graph:< 12 , 8 , Undirected > weights=Last/@Sort[Transpose[{Edges[g],GetEdgeWeights[g]}]] {18,6,14,2,11,9,20,15,19,4,4,4} ShowGraph[g,EdgeLabelweights, VertexNumberTrue]

Metricki problemi u teoriji grafova

16

2 3 11 18 19 2 4 9 20 4 4 5 4 6 7 15 6 8 14 1

Graphics ?ShortestPath [email protected], start, endD finds a shortest path between vertices start and end in graph g. An option Algorithm that takes on the values Automatic, Dijkstra, or BellmanFord is provided. This allows a choice between using Dijkstra's algorithm and the Bellman-Ford algorithm. The default is Algorithm -> Automatic. In this case, depending on whether edges have negative weights and depending on the density of the graph, the algorithm chooses between Bellman-Ford and Dijkstra. More... sp=ShortestPath[g,4,3] {4,1,7,5,3} edges=Partition[sp,2,1] {{4,1},{1,7},{7,5},{5,3}} ShowGraph[Highlight[g,{edges},HighlightedEdgeColors{Red}], EdgeLabelweights, VertexNumberTrue]

2

3 11 18 19 2 4 9 20 4 4 5 4 15

1

14

6

8

7

6

Graphics GetEdgeWeights[g,edges] {18,9,6,4} Total[GetEdgeWeights[g,edges]] 37

Metricki problemi u teoriji grafova

17

Stablo minimalne duljine

Razapinjujue stablo (spanning tree) nekog grafa G je svako stablo (podgraf grafa G) koji sadrzi sve cvorove iz G. Razapinjujue stablo minimalne duljine (minimum spanning tree) je razapinjujue stablo sa minimalnom sumom tezina na pripadajuim granama.

Algoritam za ovaj problem prvi je pronasao Otakar Borvka kao metodu za konstrukciju efikasne elektricne mreze u Ceskoj 1926. godine.

Prim-Jarnikov algoritam

Prim-Jarnikov algoritam je jedan od najpopularnijih algoritama koji odreuju stablo minimalne duljine.

Algoritam 4:

Prim_Jarnik_stablo_minimalne_duljine(Graf g) pocetak -- pocetno stanje Izaberi bilo koji v iz Cvorovi(g) d[v]:=0 za svaki vi iz Cvorovi(g)\{v} radi d[v]:= t := Ø Q := Heap(d, Cvorovi(g),{})--bez grana -- glavna petlja sve dok Q Ø radi pocetak izvuci minimalan (u,e) iz Q takav da je ­- naimo cvor d[u] = min {d[vi]} za svaki vi iz Q t := t (u,e) ­- dodajemo naeni cvor i granu u stablo Q := Q \{u} ­- cvor izbacimo iz popisa neodraenih za svaki vi iz Q povezan sa u radi ­- svim preostalim cvorovima azuriraj udaljenosti ako je d[vi] > w(u,vi) onda Azuriraj_heap(d[vi], vi,(u,vi)) ­ azuriraj heap kraj kraj

Koristei binarni heap, Prim-Jarnikov algoritam je kompleksnosti O((m+n) ·ln(n)), a koristei Fibonacci heap, kompleksnost algoritma je O(m+n·ln(n)). Sa potpunim grafom, u prvom slucaju kompleksnost je O(n2·ln(n)), a u drugom O(n2).

Metricki problemi u teoriji grafova

18

Kruskalov algoritam

Kruskalov algoritam je jos jedan od algoritama koji odreuju stablo minimalne duljine.

Algoritam 5:

Kruskalov_stablo_minimalne_duljine(Graf g) pocetak -- pocetno stanje za svaki vi iz Cvorovi(g) radi c[v]:={v} ­- skup pojedinacnih stabala t := Ø ­- izlazno stablo Q := Heap(w(Grane(g)), Grane(g)) -- glavna petlja sve dok Q Ø radi pocetak izvuci minimalan (u,v) iz Q takav da je ­- naimo cvor w(u,v) = min { w((u,v)i)} za svaku granu (u,v)i iz Q Q := Q \{(u,v)} ­- cvor izbacimo iz popisa neodraenih ako je c[v]c[u] onda pocetak t := t (u,e) ­- dodajemo naenu granu u stablo spoji pojedina stabla c[v],c[u] u jedno c[z] kraj kraj kraj

Kompleksnost Kruskalovog algoritama je O(m·ln(n)).

Usporedba algoritama

Osnovne razlike izmeu tri algoritama su u slijedeem: · Prim-Jarnikov algoritam u svakom koraku prosiruje oznaceno stablo sa najblizim cvorom, · Kruskalov algoritam u svakom koraku spaja dva najbliza stabla sa novom granom, · Borvkin algoritam u svakom koraku spaja sva najbliza stabla sa novom granom. Kruskalov i Borvkin algoritam se mogu unaprijediti tako da njihova kompleksnost bude O(m·(n)), gdje je inverzna Ackermanova funkcija.

Primjer 9:

Metricki problemi u teoriji grafova

19

g=SetEdgeWeights[RandomGraph[8,.4],WeightingFunctionRandomInteger, WeightRange{1,20}] Graph:< 12 , 8 , Undirected > weights=Last/@Sort[Transpose[{Edges[g],GetEdgeWeights[g]}]] {18,6,14,2,11,9,20,15,19,4,4,4} ShowGraph[g,EdgeLabelweights, VertexNumberTrue]

2 3 11 18 19 2 4 9 20 4 4 5 4 6 7 15 6 8 14 1

Graphics ?MinimumSpanningTree [email protected] uses Kruskal's algorithm to find a minimum spanning tree of graph g. More... st=MinimumSpanningTree[g] Graph:< 7 , 8 , Undirected > edges=Edges[st] {{2,7},{5,7},{5,8},{6,8},{1,7},{3,5},{1,4}} ShowGraph[Highlight[g,{edges},HighlightedEdgeColors{Red}],EdgeLabelweights , VertexNumberTrue]

2

3 11 18 19 2 4 9 20 4 4 5 4 15

1

14

6

8

7

6

Metricki problemi u teoriji grafova

20

Graphics GetEdgeWeights[g,edges] {18,9,6,2,4,4,4} Total[GetEdgeWeights[g,edges]] 47

Steinerov problem

Ukoliko je u sintezi stabla minimalne duljine dozvoljeno uvoenje novih cvorova, moze se dobiti i efikasnije rjesenje od stabla minimalne duljine. Problem odreivanja ovakve najkrae mreze zove se Steinerov problem. U praksi su najzanimljivije varijante Euklidskog Steinerovog problema i Rectlinear Steinerovog problema, gdje su u prvoj dozvoljene grane pod svim kutevima, a u drugoj samo grane pod pravim kutem (tzv. Manhattan metrika).

Slika 1:

Algoritmi za trazenje Steinerovog stabla su NP-kompletni i samim time dovelo je do razvoja raznih heuristickih algoritama koji daju aproksimativna rjesenja.

Metricki problemi u teoriji grafova

21

Ostali metricki problemi

Problem trgovackog putnika

Jos jedan od bitnih metrickih problema u teoriji grafova trazenje je optimalnog Hamiltonovog ciklusa. Ako se predstavi graf kao trgovacka mreza, grane kao mogue veze izmeu gradova, a tezine kao udaljenosti gradova, onda se ovaj problem moze predstaviti kao zelja trgovackog putnika, koji mora obii sve gradove, za trazenjem najkraeg puta. Koliko god izgledao jednostavan kao i prethodni, ovaj problem je NP-kompletan. Postoji veliki niz heuristickih algoritama koji se veinom vode na nalazenje neoptimalnog Hamiltonovog ciklusa i naknadno modificiranje u svrhu postizanja manje ukupne duljine. Sa druge strane razvilo se veliki broj paralelnih i distribuiranih algortama i sustava koje egzaktno rijesavaju ovaj problem. Trenutni rekord je rjesavanje problema na 24.978 gradova u Svedskoj 2004. godine, a prethodni rekord je postavljen na 15.112 gradova u Njemackoj 2001. godine. U toku je rjesavanje problema na 1.904.711 gradova na Zemlji. Na slici je dano jedno heuristicko rjesenje.

Slika 1

Metricki problemi u teoriji grafova

22

Na kompletnom grafu sa n cvorova (npr. n gradova na mapi) postoji (n-1)!/2 moguih Hamiltonovih ciklusa, tako da slozenost trivijalnog algoritma, koji provjerava sve mogue ture, na kompletnom grafu sa n cvorova (npr. n gradova na mapi) iznosi O(n!). Held i Karp su 1962. pronasli algoritam slozenosti O(n22n) i do danas nije pronaen algoritam manje slozenosti.

Primjer 10:

g=SetEdgeWeights[RandomGraph[7,.5],WeightingFunctionRandomInteger,WeightRan ge{10,40}] Graph:< 12 , 7 , Undirected > ?HamiltonianQ [email protected] yields True if there exists a Hamiltonian cycle in graph g, or in other words, if there exists a cycle that visits each vertex exactly once. More... HamiltonianQ[g] True ?TravelingSalesman [email protected] finds an optimal traveling salesman tour in graph g. More... t=TravelingSalesman[g] {1,5,2,4,6,3,7,1} edges=Partition[t,2,1] {{1,5},{5,2},{2,4},{4,6},{6,3},{3,7},{7,1}} ShowGraph[Highlight[g,{edges},HighlightedEdgeColors{Red}], VertexStyleDisk[.05]]

Graphics SetOptions[Arrow,HeadShapeAutomatic,HeadScalingAbsolute,HeadCenter.8] {HeadScalingAbsolute,HeadLengthAutomatic,HeadCenter0.8,HeadWidth0.5,Hea dShapeAutomatic,ZeroShapeAutomatic} weights=Last/@Sort[Transpose[{Edges[g],GetEdgeWeights[g]}]] {17,20,14,13,39,10,30,40,12,31,31,27} Show[GraphicsArray[ Block[{$DisplayFunction=Identity}, { ShowGraph[g,EdgeLabelweights,VertexColorBlack,VertexStyleDisk[.07]], Graphics[{PointSize[.06],ShowGraph[g,VertexColorBlack,VertexStyleDisk[.07] ][[1]],ShowGraph[FromOrderedPairs[edges],EdgeColorRed][[1]]/.Point[l_] {}}, AspectRatioAutomatic,PlotRangeAll] }

Metricki problemi u teoriji grafova

23

] ]]

17 10 30 40 31 27 20 31 14 13 12

39

GraphicsArray GetEdgeWeights[g,edges] {30,14,40,31,27,39,31} Total[GetEdgeWeights[g,edges]] 212

Problem kineskog postara

Kineski postar mora od postanskog ureda proi svakom ulicom i vratiti se u ured. U teoriji grafova ovaj problem se svodi na trazenje optimalnog ciklusa koji sadrzi sve grane grafa. Iza ovaj problem postoji veliki niz raznih algortama. Veina se svodi na rjesavanje problema u Eulerovom grafu koji se dobije konstrukcijom iz postojeeg grafa. Na takvom grafu trazi se Eulerov ciklus. I ovaj problem u opem slucaju je NP-kompletan, a kompleksnost jako ovisi o broju cvorova neparnog stupnja.

Metricki problemi u teoriji grafova

24

Zadaci

1. Zadatak

[8.4.2] Drvo sa n 3 cvorova ima dijametar 2 ako i samo ako je zvijezda.

Dokaz se provodi u dva smjera: 1º Svaka zvijezda je dijametra 2. Neka je v0 cvor stupnja n, a v1, ..., vn cvorovi stupnja 1 u zvijezdi T [ n +1] sa n+1 cvorova. d (v0 , vi ) = 1 i = 1, ..., n d (vi , v j ) = d (vi , v0 ) + d (v0 , v j ) = 2 i, j = 1, ..., n

0 i = j d (vi , v j ) = 1 i = 0 j = 1, ..., n i = 1, ..., n j = 0 2 i, j = 1, ..., n

d [G] = max d(vi, vj) = 2

2º Svako stablo dijametra 2 je zvijezda. Dokaz provodimo matematickom indukcijom. · n = 3, jedino stablo je ujedno i zvijezda, dijametra 2:

Zadatak 1:

g=RandomTree[3] Graph:< 2 , 3 , Undirected > ShowGraph[g,EdgeColorBlue,VertexStyleDisk[.08]]

Diameter[g] 2

·

Pretpostavimo da tvrdnja vrijedi za graf sa n cvorova, dokazimo da vrijedi za graf sa n+1 cvorova. Kako stablo T [ n +1] sa n+1 cvorova ima n grana, mozemo odabrati cvor xn koji je spojen sa ostatkom stabla sa samo jednom granom. Ukoliko iz stabla T izbacimo taj cvor sa pripadajuom granom dobijamo stablo T [ n ] koje je dijametra 2, a po pretpostavku indukcije T [ n ] je zvijezda. Neka je v0 cvor stupnja n, a v1, ..., vn-1 cvorovi stupnja 1 u zvijezdi T [ n ] . Da je cvor vn u stablu T [ n+1] povezan granom sa cvorom vi , i {1, ...., n - 1} , udaljenost d (vn , v j ) = 3 j = 1, ..., n j i , odnosno

Metricki problemi u teoriji grafova

25

d [T [ n+1] ] = 3 . Znaci cvor vn u stablu T [ n+1] povezan je granom sa cvorom v0 time je i T [ n+1] zvijezda.

QED

2. Zadatak

[8.4.3] Pokazi da samokomplementarni grafovi ( n > 1 ) imaju dijametar 2 ili 3.

1º 2º

Ako graf G ima dijametar 1, onda je onda je kompletan, a njegov komplement graf bez grana, tako da graf G nije samokomplementaran graf. Pokazimo samokomplementarne grafove sa dijametrom 2 i 3:

Zadatak 2:

g5=Select[Graphs[5],SelfComplementaryQ] { Graph:< 5 , 5 , Undirected > , Graph:< 5 , ShowGraphArray[g5] 5 , Undirected > }

GraphicsArray Map[Diameter,g5] {3,2} g8=Select[Graphs[8],SelfComplementaryQ] { Graph:< 14 , 8 , Undirected > , Graph:< 14 , 8 , Undirected > , Graph:< 14 , 8 , Undirected > , Graph:< 14 , 8 , Undirected > , Graph:< 14 , 8 , Undirected > , Graph:< 14 , 8 , Undirected > , Graph:< 14 , 8 , Undirected > , Graph:< 14 , 8 , Undirected > , Graph:< 14 , 8 , Undirected > , Graph:< 14 , 8 , Undirected > } ShowGraphArray[Take[g8,3]]

GraphicsArray Map[Diameter,g8] {3,3,3,2,3,3,3,3,2,3}

Dokazimo da ako je d (G ) 3 d (G ) 3

Metricki problemi u teoriji grafova

26

Ako vrijedi d (G ) 3 , postoje cvorovi vi i vj izmeu kojih je udaljenost minimalno 3 d (vi , v j ) 3 . U komplementarnom grafu G ova dva cvora su susjedna

d (vi , v j ) = 1 (kako u grafu G nije grana (vi, vj), onda je u grafu G ). Gledajmo sada ostale

cvorove. Niti jedan preostali cvor vk ne smije biti povezan sa oba cvora vi i vj (jer bi postojao put vi, vk, vj duljine 2 sto se kosi sa pretpostavkom d (vi , v j ) 3 ). Znaci da je i u komplementarnom grafu G , vk povezan barem sa jednim od cvorova vi , v j . Neka je skup Vi skup cvorova povezanih sa vi , a V j skup cvorova povezanih sa v j . Vrijedi da je skup svih cvorova komplementarnog grafa G V = Vi V j {v i , v j } Za udaljenosti cvorova u komplementarnom grafu imamo:

· · · · · ·

d (vl , vm ) = 1 za l = i i m = j d (vl , vm ) = 1 za l = i i m Vi d (vl , vm ) 2 za l = i i m V j , jer postoji put vm , v j , vi d (vl , vm ) = 1 za l = j i m V j d (vl , vm ) 2 za l = j i m Vi , jer postoji put vm , vi , v j d (vl , vm ) 3 za l Vi i m V j , jer postoji put vm , vi , v j , vm

Kako smo ovime pokrili sve kombinacije cvorova, slijedi da je i d (G ) 3 . 4º 5º Kada je G samokomplementaran graf, grafovi G i G su izomorfni, tako da vrijedi d (G ) = d (G ) . Kako sa druge strane vrijedi tvrdnja 3º, slijedi da d (G ) 3 Iz tocki 1º, 2º i 4º slijedi da je dijametar samokomplementarnog grafa 2 ili 3. QED

3. Zadatak

[8.4.8] Dokazati da u proizvoljno orijentiranom potpunom grafu (turniru) postoji cvor iz kojeg su svi cvorovi grafa dostupni putem ne duzim od 2.

Dokaz provodimo matematickom indukcijom. 1º 2º Tvrdnja vrijedi za turnir TU [ 2 ] TU[2] sa brojem cvorova n = 2. Pretpostavimo da tvrdnja vrijedi za svaki turnir TU[n] sa n cvorova. Dokazimo da tvrdnja vrijedi za turnir TU[n+1] sa n+1 cvorova. Izdvojimo cvor vn+1 i pripadajue grane. Preostali podgraf TU[n] je turnir sa n cvorova. Prema pretpostavci matematicke indukcije u podgrafu TU[n] postoji cvor (oznacimo ga sa v0) koji ima svojstvo:

d (v0 , vi ) 2 i = 1, ..., n

Metricki problemi u teoriji grafova

27

Podijelimo ostale cvorove u T[n] na cvorove koji su od v0 udaljeni 1 (skup V1) i one koji su udaljeni 2 (skup V2). Put duljine 2 od v0 do svakog cvora iz V2 vodi preko nekog cvora iz V1, znaci za svaki cvor v j V2 postoji cvor vi V1 za kojeg je d (vi , v j ) = 1 . U ovisnosti od usmjerenja grana prema cvoru vn+1 imamo slijedea 3 slucaja: 1. Grana ev0 ,vn +1 od cvora v0 je usmjerena prema cvoru vn+1. U ovom slucaju d(v0,vn+1) = 1, tj. d (v0 , vk ) 2 k = 1, ..., n, n + 1 . Znaci da je cvor v0 cvor sa trazenim svojstvom. 2. Grana ev0 ,vn +1 od cvora vn+1 je usmjerena prema cvoru v0 i postoji cvor vi V1 kod kojeg je grana evi ,vn +1 usmjerena prema cvoru vn+1. Onda je:

d (v0 , vn+1 ) = d (v0 , vi ) + d (vi , vn+1 ) = 1 + 1 = 2 , tj. d (v0 , vk ) 2 k = 1, ..., n, n + 1 . Znaci da je cvor v0 cvor sa trazenim svojstvom.

3. Grana ev0 ,vn +1 od cvora vn+1 je usmjerena prema cvoru v0 i za sve cvorove vi V1 grana evi ,vn +1 je usmjerena prema cvoru vi. Znaci da je:

d (vn+1 , v0 ) = 1 d (vn+1 , vi ) = 1 vi V1

Kako za svaki cvor v j V2 postoji cvor vi V1 za kojeg je d (vi , v j ) = 1 slijedi:

d (vn+1 , v j ) = d (vn+1 , vi ) + d (vi , v j ) = 1 + 1 = 2 v j V2 , odnosno d (vn+1 , vk ) 2 k = 0, ..., n Znaci da je cvor vn+1 cvor sa trazenim svojstvom.

Kako smo sa ove tri varijante pokrili sve mogue slucaje i u svakom nasli cvor sa trazenim svojstvom (u 1. i 2. slucaju v0, a u 3. slucaju vn+1), ovim smo dokazali teorem i za korak matematicke indukcije. QED

Zadatak 3:

Tournaments[n_]:=Select[ListGraphs[n,Binomial[n,2],Directed],CompleteQ[MakeU ndirected[#]]&] TournamentQ[g_Graph]:=OrientedQ[g]&&CompleteQ[MakeUndirected[g]] TO=OrientGraph[CompleteGraph[6]] Graph:< 15 , 6 , Directed > SetOptions[Arrow,HeadShapeAutomatic,HeadCenter1,HeadScalingAutomatic]; ShowGraph[TO,EdgeColorBlue,VertexStyleDisk[.03]]

Metricki problemi u teoriji grafova

28

Graphics dist=Map[BreadthFirstTraversal[TO,#,Level]&,Range[1,V[TO]]] {{0,2,4,1,3,2},{1,0,3,2,2,1},{1,1,0,1,2,1},{2,1,3,0,2,1},{1,1,1,1,0,2},{1,2, 2,2,1,0}} Max/@dist {4,3,2,3,2,2}

4. Zadatak

[8.4.9] Na jednom turniru svaki igrac je igrao protiv svakog i nijedna utakmica (partija) nije zavrsena nerijeseno. Dokazati da postoji ucesnik, koji e da spomene sve ostale takmicare, ako spomene one koje je pobijedio, kao i one koji su bili pobijeeni od strane takmicara koje je on pobijedio.

Postavimo graf kojemu su cvorovi ucesnici turnira a grane partije usmjerene od strane pobjednika prema porazenom. Dobijemo orijentirani potpuni graf ­ turnir. Prema prethodnom zadatku u turniru postoji cvor iz kojeg su svi cvorovi grafa dostupni putem ne duzim od 2. To znaci da postoji ucesnik koji je pobijedio neke ucesnike (najkrai put u grafu jednak 1), a sve ostale ucesnike su pobijedili ucesnici koje je on pobijedio (najkrai put u grafu jednak 2).

5. Zadatak

[8.4.11] Zelimo da izgradimo vodovodnu mrezu bez kontura izmeu odreenog broja gradova. Za izgradnju mreze konkurise vei proj preduzea. Posao moze da radi i vei broj preduzea u kooperaciji ali izmeu svaka dva grada mora da radi samo jedno preduzee. Zato od svih konkurenata trazimo plan sa naznakom troskova izgradnje pojedinih veza. Na osnovu predatih planova sastaviti najekonomicniji plan izgradnje.

Postavimo graf G kojemu su cvorovi gradovi, a grane ponude svakog poduzea za izgradnju dionice izmeu dva cvora (grada) koje veze grana. Za tezinu pojedine grane postavimo cijenu izgradnje te dionice (ukoliko postoji ponuda od vise poduzea za pojedinu dionicu, ostavimo granu sa najmanjom tezinom). Najekonomicniji plan nam daje razapinjue stablo grafa G, minimalne duljine.

Zadatak 5:

Metricki problemi u teoriji grafova

29

g = SetEdgeWeights[RandomGraph[8,.3], WeightingFunctionRandomInteger,WeightRange{20,40}] Graph:< 12 , 8 , Undirected > g=SetGraphOptions[g,Append[Edges[g],EdgeColorRed]] Graph:< 12 , 8 , Undirected > Edges[g,EdgeWeight] {{{1,3},23},{{3,4},36},{{1,6},33},{{5,6},24},{{2,7},27},{{5,7},34},{{6,7},37 },{{2,8},31},{{3,8},28},{{4,8},31},{{5,8},25},{{7,8},30}} gw=Last/@Sort[Transpose[{Edges[g],GetEdgeWeights[g]}]] {23,33,27,31,36,28,31,24,34,25,37,30} ShowGraph[g,EdgeLabelgw,VertexStyleDisk[Large],VertexNumberColorWhite,Ver texNumberTrue,VertexNumberPositionCenter]

2 3 1 31 36 28 27 4 31 33 25 30 8

23

5 24

34 37 6

7

Graphics h = SetGraphOptions[SetEdgeWeights[RandomGraph[8,.3], WeightingFunctionRandomInteger,WeightRange{10,80}]] Graph:< 9 , 8 , Undirected > h=SetGraphOptions[h,Append[Edges[h],EdgeColorBlue]] Graph:< 9 , 8 , Undirected > Edges[h,EdgeWeight] {{{4,5},31},{{1,6},24},{{3,6},36},{{4,6},67},{{2,7},37},{{3,7},76},{{5,7},67 },{{6,7},42},{{3,8},39}} hw=Last/@Sort[Transpose[{Edges[h],GetEdgeWeights[h]}]] {24,37,36,76,39,31,67,67,42} ShowGraph[h,EdgeLabelhw,VertexStyleDisk[Large],VertexNumberColorWhite,Ver texNumberTrue,VertexNumberPositionCenter]

2 3 1

39 37 4 36 31 67 5 67 42 6 7 76 24 8

Metricki problemi u teoriji grafova

30

Graphics i = SetEdgeWeights[RandomGraph[8,.3],WeightingFunctionRandomInteger,WeightRange {1,90}] Graph:< 8 , 8 , Undirected > i=SetGraphOptions[i,Append[Edges[i],EdgeColorGreen]] Graph:< 8 , 8 , Undirected > Edges[i,EdgeWeight] {{{1,3},25},{{2,5},3},{{3,5},58},{{1,6},11},{{3,6},59},{{4,6},65},{{5,6},32} ,{{1,7},87}} iw=Last/@Sort[Transpose[{Edges[i],GetEdgeWeights[i]}]] {25,11,87,3,58,59,65,32} ShowGraph[i,EdgeLabeliw,VertexStyleDisk[Large],VertexNumberColorWhite,Ver texNumberTrue,VertexNumberPositionCenter]

2 3 1

25

3 4 58 59 11 87 8

65 5 32 6 7

Graphics j=GraphSum[g,h,i] Graph:< 29 , 8 , Undirected > Edges[j,EdgeWeight] {{{1,3},23},{{3,4},36},{{1,6},33},{{5,6},24},{{2,7},27},{{5,7},34},{{6,7},37 },{{2,8},31},{{3,8},28},{{4,8},31},{{5,8},25},{{7,8},30},{{4,5},31},{{1,6},2 4},{{3,6},36},{{4,6},67},{{2,7},37},{{3,7},76},{{5,7},67},{{6,7},42},{{3,8}, 39},{{1,3},25},{{2,5},3},{{3,5},58},{{1,6},11},{{3,6},59},{{4,6},65},{{5,6}, 32},{{1,7},87}} jw=Last/@Sort[Transpose[{Edges[j],GetEdgeWeights[j]}]] {23,25,11,24,33,87,3,27,37,31,36,58,36,59,76,28,39,31,65,67,31,24,32,34,67,2 5,37,42,30} ShowGraph[j,EdgeLabeljw,VertexStyleDisk[Large],VertexNumberColorWhite,Ver texNumberTrue,VertexNumberPositionCenter]

Metricki problemi u teoriji grafova

31

2

3

25 23 31

1

36 3 4 58 59 36 31 67 65 5 32 24 6 67 34 31 76

39 28 37 27 87 33 24 11 25 30 8

7 42 37

Graphics AlenRemoveMultipleEdges[g_Graph]:=ChangeEdges[g,Map[First,Split[Sort[Edges[g ,All]],(First[#1] First[#2])&]]] j=AlenRemoveMultipleEdges[j] Graph:< 19 , 8 , Undirected > Edges[j,EdgeWeight] {{{1,3},23},{{1,6},11},{{1,7},87},{{2,5},3},{{2,7},27},{{2,8},31},{{3,4},36} ,{{3,5},58},{{3,6},36},{{3,7},76},{{3,8},28},{{4,5},31},{{4,6},65},{{4,8},31 },{{5,6},24},{{5,7},34},{{5,8},25},{{6,7},37},{{7,8},30}} jw=Last/@Sort[Transpose[{Edges[j],GetEdgeWeights[j]}]] {23,11,87,3,27,31,36,58,36,76,28,31,65,31,24,34,25,37,30} ShowGraph[j,EdgeLabeljw,VertexStyleDisk[Large],VertexNumberColorWhite,Ver texNumberTrue,VertexNumberPositionCenter]

2

3

23 31

1

36 3 4 58 36 31 65 5 24 6 34 31 76

28 27 87 11 25 30 8

7 37

Graphics

Metricki problemi u teoriji grafova

32

k=MinimumSpanningTree[Edges[j,EdgeWeight],j] Graph:< 7 , 8 , Undirected > Edges[k,EdgeWeight] {{{2,5},1},{{1,6},1},{{1,3},1},{{5,6},1},{{5,8},1},{{2,7},1},{{4,5},1}} ShowGraph[k,VertexStyleDisk[Large],VertexNumberColorWhite,VertexNumberTru e,VertexNumberPositionCenter]

2 3 1

4

8

5 6

7

Graphics l=GraphIntersection[j,k] Graph:< 7 , 8 , Undirected > Edges[l,EdgeWeight] {{{1,3},23},{{1,6},11},{{2,5},3},{{2,7},27},{{4,5},31},{{5,6},24},{{5,8},25} } lw=Last/@Sort[Transpose[{Edges[l],GetEdgeWeights[l]}]] {23,11,3,27,31,24,25} ShowGraph[l,EdgeLabellw,VertexStyleDisk[Large],VertexNumberColorWhite,Ver texNumberTrue,VertexNumberPositionCenter]

2

3

23

1

3 4

27 8 11

31

25

5 24 6

7

Graphics Total[GetEdgeWeights[l]] 144

Metricki problemi u teoriji grafova

33

6. Zadatak

[8.4.1] Date su tri posude: prva, cija zapremina iznosi 8 litara, napunjena je tecnosu, druga i trea koje imaju 5 odnosno 3 litra su prazne. Presipajui tecnost iz jedne u drugu od ovih posuda, postii na najbrzi nacin da se u prvoj posudi nalazi 4 litra i u drugoj takoe 4 litra tecnosti.

Postavimo usmjereni graf kojemu su cvorovi stanja u posudama, a usmjerene grane dozvoljene kombinacije presipavanja. Ako cvorove oznacimo sa stanjima posuda (x, y, z), onda je trazeno rjesenje minimalan put izmeu cvora (8, 0, 0) i (4, 4, 0).

Zadatak 6:

a=8; b=5;c=3; a_poc=8; b_poc=0; c_poc=0 0 ?GridGraph

g=GridGraph[b+1,c+1] Graph:< 38 , 24 , Undirected > cs=Quotient[Range[0,(b+1) (c+1)-1],b+1] {0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3} bs=Mod[Range[0,(b+1) (c+1)-1],b+1] {0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5} as=8-cs-bs {8,7,6,5,4,3,7,6,5,4,3,2,6,5,4,3,2,1,5,4,3,2,1,0} s=100 as+10 bs+cs

[email protected], mD constructs an n m grid graph, the product of paths on n and m vertices. [email protected], q, rD constructs a pqr grid graph, the product of [email protected], qD and a path of length r. More...

{800,710,620,530,440,350,701,611,521,431,341,251,602,512,422,332,242,152,503 ,413,323,233,143,53} Stanje[ul_Integer]:=Block[ {cx=Quotient[ul-1,b+1],bx=Mod[ul-1,b+1],ax=8-cx-bx},100 ax+10 bx+cx] Cvor[ul_Integer]:= Block[ { at=Quotient[ul,100],bt=Quotient[ul-at*100,10],ct=ul-100*at-10*bt}, bt+ct*6+1 ] Stanje/@Cvor/@s {800,710,620,530,440,350,701,611,521,431,341,251,602,512,422,332,242,152,503 ,413,323,233,143,53} g=OrientGraph[SetVertexLabels[g,s]] Graph:< 38 , 24 , Directed > g=DeleteEdges[g,Edges[g]] Graph:< 0 , 24 , Directed > Potez[ul_Integer]:= Block[ { at=Quotient[ul,100],bt=Quotient[ul-at*100,10],ct=ul-100*at-10*bt}, {If[at>0, If[bt<b, If[at>=b-bt,{100*at+10*bt+ct,100*( at-(bbt))+10*b+ct},{100*at+10*bt+ct,100*0+10*(at+b)+ct}]]], If[at>0, If[ct<c, If[at>=c-ct,{100*at+10*bt+ct,100*( at-(cct))+10*bt+c},{100*at+10*bt+ct,100*0+10*bt+at+ct}]]],

Metricki problemi u teoriji grafova

34

If[bt>0, If[at<a, If[bt>=a-at,{100*at+10*bt+ct,100*a+10*(bt-(aat))+ct},{100*at+10*bt+ct,100*(at+bt)+10*0+ct}]]], If[bt>0, If[ct<c, If[bt>=c-ct,{100*at+10*bt+ct,100*at+10*(bt-(cct))+c},{100*at+10*bt+ct,100*at+10*0+bt+ct}]]], If[ct>0, If[at<a, If[ct>=a-at,{100*at+10*bt+ct,100*a+10*bt+(ct-(aat))},{100*at+10*bt+ct,100*(at+ct)+10*bt+0}]]], If[ct>0, If[bt<b, If[ct>=b-bt,{100*at+10*bt+ct,100*at+10*b+(ct-(bbt))},{100*at+10*bt+ct,100*at+10*(bt+ct)+0}]]] }] potezi=DeleteCases[Flatten[Map[Potez,s],1],Null] {{800,350},{800,503},{710,350},{710,413},{710,800},{710,701},{620,350},{620, 323},{620,800},{620,602},{530,350},{530,233},{530,800},{530,503},{440,350},{ 440,143},{440,800},{440,413},{350,53},{350,800},{350,323},{701,251},{701,503 },{701,800},{701,710},{611,251},{611,413},{611,701},{611,602},{611,710},{611 ,620},{521,251},{521,323},{521,701},{521,503},{521,620},{521,530},{431,251}, {431,233},{431,701},{431,413},{431,530},{431,440},{341,251},{341,143},{341,7 01},{341,323},{341,440},{341,350},{251,53},{251,701},{251,233},{251,350},{60 2,152},{602,503},{602,800},{602,620},{512,152},{512,413},{512,602},{512,503} ,{512,710},{512,530},{422,152},{422,323},{422,602},{422,413},{422,620},{422, 440},{332,152},{332,233},{332,602},{332,323},{332,530},{332,350},{242,152},{ 242,143},{242,602},{242,233},{242,440},{242,251},{152,53},{152,602},{152,143 },{152,350},{503,53},{503,800},{503,530},{413,53},{413,503},{413,710},{413,4 40},{323,53},{323,503},{323,620},{323,350},{233,53},{233,503},{233,530},{233 ,251},{143,53},{143,503},{143,440},{143,152},{53,503},{53,350}} putevi=Map[{Cvor[First[#]],Cvor[Last[#]]}&,potezi] {{1,6},{1,19},{2,6},{2,20},{2,1},{2,7},{3,6},{3,21},{3,1},{3,13},{4,6},{4,22 },{4,1},{4,19},{5,6},{5,23},{5,1},{5,20},{6,24},{6,1},{6,21},{7,12},{7,19},{ 7,1},{7,2},{8,12},{8,20},{8,7},{8,13},{8,2},{8,3},{9,12},{9,21},{9,7},{9,19} ,{9,3},{9,4},{10,12},{10,22},{10,7},{10,20},{10,4},{10,5},{11,12},{11,23},{1 1,7},{11,21},{11,5},{11,6},{12,24},{12,7},{12,22},{12,6},{13,18},{13,19},{13 ,1},{13,3},{14,18},{14,20},{14,13},{14,19},{14,2},{14,4},{15,18},{15,21},{15 ,13},{15,20},{15,3},{15,5},{16,18},{16,22},{16,13},{16,21},{16,4},{16,6},{17 ,18},{17,23},{17,13},{17,22},{17,5},{17,12},{18,24},{18,13},{18,23},{18,6},{ 19,24},{19,1},{19,4},{20,24},{20,19},{20,2},{20,5},{21,24},{21,19},{21,3},{2 1,6},{22,24},{22,19},{22,4},{22,12},{23,24},{23,19},{23,5},{23,18},{24,19},{ 24,6}} e=AddEdges[g,putevi] Graph:< 106 , 24 , Directed > SetOptions[Arrow,HeadShapeAutomatic,HeadScalingAbsolute,HeadCenter.8]; ShowGraph[e,VertexStyleDisk[.04],VertexLabelColorWhite,VertexLabelPosition Center, EdgeColorBlue]

Metricki problemi u teoriji grafova

35

503

413

323

233

143

53

602

512

422

332

242

152

701

611

521

431

341

251

800

710

620

530

440

350

Graphics stanjeput=Map[Stanje,ShortestPath[e,Cvor[800],Cvor[440]]] {800,350,323,620,602,152,143,440} cvorput=Cvor/@stanjeput {1,6,21,3,13,18,23,5} tura=Partition[stanjeput,2,1] {{800,350},{350,323},{323,620},{620,602},{602,152},{152,143},{143,440}} cvortura=Partition[cvorput,2,1] {{1,6},{6,21},{21,3},{3,13},{13,18},{18,23},{23,5}} ShowGraph[Highlight[e,{cvortura},HighlightedEdgeColors{Red}],VertexStyleDi sk[.04],VertexLabelColorWhite,VertexLabelPositionCenter, EdgeColorBlue]

503 413 323 233 143 53

602

512

422

332

242

152

701

611

521

431

341

251

800

710

620

530

440

350

Graphics f=DeleteVertices[DeleteEdges[e,Complement[Edges[e],cvortura]],Complement[Ran ge[1,(b+1) (c+1)],cvorput]]

Metricki problemi u teoriji grafova

36

Graph:< 7 ,

8 ,

Directed >

ShowGraph[f,VertexStyleDisk[.04],VertexLabelColorWhite,VertexLabelPosition Center, EdgeColorBlue]

323 143

602

152

800

620

440

350

Graphics

Metricki problemi u teoriji grafova

37

Literatura i ostali izvori

[1] Dragos Cvetkovi, Mirko Mili: Teorija grafova i njene primene, Naucna knjiga, Beograd, 1977 [2] www.wikipedia.com [3] www.mathworld.wolfram.com [4] www.diku.dk/geosteiner [5] Darko Veljan; Kombinatorika sa teorijom grafova, Skolska knjiga, Zagreb, 1989 [6] Bernard Chazelle: A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, 1999 Original ovog dokumenta i pripadajua Mathematica biljeznica nalazi se na: · www.selimbegovic.com/alen.html

Metricki problemi u teoriji grafova

38

Information

Microsoft Word - Metricki problemi u teoriji grafova.doc

38 pages

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

509111


You might also be interested in

BETA
Microsoft Word - Metricki problemi u teoriji grafova.doc