Pagal knygą:  Paul Helman, Robert Veroff, Frank R. Carrano, Intermediate Problem Solving and Data Structures, Walls and Mirrors, The Benjamin/Cummings Publishing Company, 1991

 

Grafai (2 paskaita)

 

Aprėpties medžiai (Spanning Trees)

Medis yra jungus neorientuotas grafas be ciklų.

Grafo G aprėpties medis yra grafo G pografis G, turintis visas grafo G viršūnes ir pakankamai briaunų medžiui.

Grafui gali egzistuoti keli aprėpties medžiai.

Jei jungiame neorientuotame grafe išnaikinsime ciklus, gausime aprėpties medį.

Neorientuoto grafo savybės:

1.      Jungus neorientuotas grafas su N viršūnių turi ne mažiau kaip N-1 briauną.

Reikia prisiminti, kad jungiame grafe egzistuoja kelias tarp bet kurių dviejų viršūnių. Tarkime, pasirenkame viršūnę ir sujungiame ją briauna su kita viršūne - 2 viršūnės 1 briauna; jei pridedame dar vieną viršūnę, būtina ir papildoma briauna jai prijungti prie bet kurios kitos grafo viršūnės.

2.      Jungus neorientuotas grafas su N viršūnių ir N-1 briauna negali turėti ciklų.

Pagal ankstesnę savybę orientuotas grafas su N viršūnių privalo turėti ne mažiau kaip N-1 briauną, kad būtų jungus. Jei jungus grafas turi ciklą, galima pašalinti bet kurią briauną iš ciklo ir grafas liks jungus. Taigi, jei grafas su N viršūnių ir N-1 briauna turės ciklą, galima bus pašalinti vieną briauną ir gautas grafas su N-2 briauna turi likti jungus, kas prieštarauja ankstesnei savybei.

3.      Jungus neorientuotas grafas su N viršūnių ir daugiau kaip N-1 briauna turi bent vieną ciklą.

Paimkime jungų neorientuotą grafą su N viršūnių ir N-1 briauna. Pasirinkime bet kokią porą viršūnių X ir Y ir pridėkime naują briauną B, jungiančią viršūnes X ir Y. Kadangi pradinis grafas buvo jungus, tai jame egzistavo kelias iš viršūnės X į viršūnę Y. Pridėjus prie šio kelio naują briauną B, gauname ciklą, t.y. kelią iš viršūnės X į ją pačią.

Taigi patikrinti, ar jungus neorientuotas grafas turi ciklų, galima paprasčiausiai suskaičiuojant jo viršūnes ir briaunas.

Iš to seka, kad grafo G su N viršūnių aprėpties medis turi N-1 briauną.

Du aprėpties medžio konstravimo algoritmai, remiasi anksčiau nagrinėtomis medžio apėjimo strategijomis: paieškos į gylį (DFS) ir paieškos į plotį (BFS). Bendru atveju šie algoritmai sukonstruos skirtingus aprėpties medžius, kuriuos toliau sąlyginai vadinsime DFS ir BFS aprėpties medžiais atitinkamai.

 

DFS aprėpties medis

Vienas iš būdų sukonstruoti aprėpties medį jungiam neorientuotam grafui yra apeiti grafo viršūnes, naudojant paieškos į gylį algoritmą. Apėjimo metu žymimos briaunos, kuriomis einama. Baigus apėjimą, pažymėtos briaunos sudarys paieškos į gylį aprėpties medį (DFS spanning tree). Tereikia nežymiai modifikuoti paieškos į gylį algoritmą (iteracinį ar rekursinį), kad apėjimo metu žymėtų briaunas. Rekursinis algoritmas galėtų būti toks:

DFSmedis(V)

{ Suformuoja aprėpties medį, pradėdamas nuo viršūnės V ir naudodamas paieškos į gylį metodą }

Pažymėti viršūnę V kaip aplankytą

for kiekvienai neaplankytai viršūnei U kaimyninei su V do

begin

Pažymėti briauną iš V į U kaip aplankytą

DFSmedis(U)

end

 

BFS aprėpties medis

Kitas būdas sukonstruoti aprėpties medį jungiam neorientuotam grafui yra apeiti grafo viršūnes, naudojant paieškos į plotį algoritmą. Apėjimo metu žymimos briaunos, kuriomis einama. Baigus apėjimą, pažymėtos briaunos sudarys paieškos į plotį aprėpties medį (BFS spanning tree). Tam reikia modifikuoti paieškos į plotį algoritmą taip, kad jis pažymėtų briauną iš viršūnės W į viršūnę U, prieš pridėdamas viršūnę U į eilę.

 

Minimalūs aprėpties medžiai (Minimum Spanning Trees)

Tarkime, kad reikia suprojektuoti telefonų linijų sistemą, leidžiančią visiems miestams kalbėtis tarpusavyje. Akivaizdus sprendimas nutiesti telefonų linijas tarp bet kurių dviejų miestų. Tačiau sujungti kai kurias poras miestų gali būti neįmanoma, pavyzdžiui, dėl kalnų. Ištyrus galimybes, rezultate buvo gautas jungus neorientuotas grafas su svoriais, kuriame briauna reiškia, kad nuriesti telefono liniją galima, ir briaunos svoris reiškia linijos nutiesimo kainą. Akivaizdu, kad norime nutiesti linijų sistemą kuo pigiau. Jei briaunos būtų be svorių (arba visų briaunų svoriai būtų vienodi), tereiktų surasti gautam grafui aprėpties medį. Bendra linijų nutiesimo kaina yra aprėpties medžio kaina. Kadangi gali egzistuoti ne vienas aprėpties medis ir jų kaina gali būti skirtinga, uždavinio sprendimas yra pasirinkti medį su mažiausia kaina. Toks medis vadinamas minimaliu aprėpties medžiu. Toks medis gali būti ne vienintelis, bet visų jų kainos yra lygios.

Vienas iš paprastų minimalaus aprėpties medžio radimo algoritmų yra Primo algoritmas: pradedama nuo bet kurios viršūnės ir einama į neaplankytą viršūnę briauna su mažiausiu svoriu; kiekviename žingsnyje algoritmas išrenka briauną su mažiausiu svoriu, jungiančią neaplankytą viršūnę ir aplankytą viršūnę. Algoritmo pseudokodas:

MST (V)

{ Suformuoja minimalų aprėpties medį, pradėdamas nuo viršūnės V }

Pažymėti viršūnę V kaip aplankytą ir įtraukti ją į medį

while yra neaplankytų viršūnių do

begin

Rasti briauną su mažiausia kaina iš V į U, kur V aplankyta viršūnė, U neaplankyta viršūnė

Pažymėti viršūnę U kaip aplankytą

Įtraukti į medį viršūnę U ir  pasirinktą briauną iš V į U

end

Bendru atveju (nagrinėjant bet kokį algoritmą), briaunos su mažiausia kaina pasirinkimas dar negarantuoja, kad gautas sprendinys bus optimalus. Tačiau šis algoritmas sukonstruoja minimalų aprėpties medį ir tai galima įrodyti (įrodymo čia nepateiksime).

 

Trumpiausi keliai (Shortest Paths)

Tarkime, kad orientuotas grafas su svoriais vaizduoja lėktuvų maršrutus: viršūnės – miestai, briaunos – egzistuojantys skrydžiai, o svoriai – atstumai (neneigiami).

Dažnai orientuotam grafui su svoriais reikia sužinoti trumpiausią kelią tarp kažkurių dviejų viršūnių. Trumpiausias kelias yra kelias, kurio svoris (jį sudarančių briaunų svorių suma) yra minimalus. Nors tradiciškai vartojama sąvoka trumpiausias kelias, bet svoriai nebūtinai turi būti atstumai, jie gali išreikšti ir, pavyzdžiui, kainą, skrydžio laiką.

Trumpiausio kelio grafe radimo algoritmas priskiriamas E.Dijkstra. Patogumui pažymėkime pradinę viršūnę, iš kurios ieškome kelio, 1, o visas likusias grafo viršūnes - nuo 2 iki N. Pastebėkime, kad algoritmas randa trumpiausius kelius tarp pradinės viršūnės ir visų kitų grafo viršūnių.

Algoritmas naudoja pasirinktų viršūnių aibę S ir masyvą W, kur W[v] yra svoris trumpiausio (pigiausio) kelio iš viršūnės 1 į viršūnę v, einančio per aibės S viršūnes. Jei v priklauso aibei S, tai kelias eina tik per aibės S viršūnes. Jei v nepriklauso aibei S, tai yra vienintelė viršūnė, priklausanti keliui, bet nepriklausanti S, t.y. kelias baigiasi briauna, jungiančia viršūnę iš S ir viršūnę v. Pradžioje aibėje S yra tik viršūnė 1 ir masyve W yra tik svoriai kelių, sudarytų iš vienos briaunos tarp viršūnės 1 ir kitų viršūnių, kitaip sakant masyvas W yra pirma kaimynystės matricos A eilutė.

Po inicializavimo žingsnio pasirenkamos viršūnės, nepriklausančios aibei S, ir atitinkamai koreguojamas masyvas W. Pasirenkama viršūnė v, nepriklausanti aibei S, tokia, kad W[v] yra minimalus. Pridėjus viršūnę v į aibę S, reikia patikrinti reikšmes W[u] visoms viršūnėms u, nepriklausančioms S, tam, kad užtikrinti, jog šios reikšmės iš tikrųjų yra minimalios. Kitais žodžiais, reikia patikrinti, ar galima sumažinti  W[u] kelią nuo viršūnės 1 iki viršūnės u – einant per naujai pasirinktą viršūnę v. Tam kelią nuo viršūnės 1 iki viršūnės u galima suskaidyti į 2 dalis ir rasti jų svorius:

W[v] = svoris trumpiausio kelio nuo 1 iki v

A[v, u] = svoris briaunos iš v į u

Tada reikia palyginti dabartinį W[u] su W[v]+ A[v, u] ir pakeisti W[u], jei nauja reikšmė mažesnė. Trumpiausio kelio radimo algoritmo pseudokodas:

ShortestPath(G, W)

{ Randa trumpiausius kelius tarp viršūnes 1 ir visų kitų viršūnių orientuotame grafe G su N viršūnių }

{ žingsnis 1: Inicializavimas }

S := [1];

for v := 1 to N do

W[v] := A[1, v]

 

{ žingsniai 2-N }

{ Ciklo invariantas:

 v nepriklausančiai S,

  W[v] yra trumpiausias kelias iš 1 į v, einantis tik per viršūnes iš S iki v;

 v priklausančiai S,

  W[v] yra trumpiausias iš visų kelių (įskaitant ir išorinius) iš 1 į v, einantis tik per S viršūnes

}

for Step := 2 to N do

begin

Rasti mažiausią W[v], kur v nepriklauso S

S := S + [v];

 

{ Patikrinti W[u] visoms u, nepriklausančioms S }

for visoms u nepriklausančioms S do

if W[u] > W[v] + A[v, u]

then W[u] := W[v] + A[v, u]

end { for }

Ciklo invariantas teigia, kad jei v yra įtraukta į S, W[v] yra absoliučiai trumpiausias kelias ir nesikeis. Algoritmas tikrai randa trumpiausią kelią, jei ciklo invariantas yra teisingas. Tai galima įrodyti indukcijos pagal žingsnius būdu.

 

Kelios sudėtingos problemos

Prekybos agento uždavinys. Grandinė (circuit) yra kelias, kuris prasideda viršūnėje v, apeina visas grafo viršūnes ir baigiasi viršūnėje v. Akivaizdu, kad nejungiame grafe negali būti grandinės. Tačiau nustatyti ar duotame grafe egzistuoja grandinė gali būti sudėtinga. Gerai žinomas šio uždavinio variantas – prekybos agento uždavinys: grafas su svoriais vaizduoja kelių žemėlapį, briaunų svoriai išreiškia atstumus tarp miestų (arba laiką); prekybos agentas turi pradėti kelionę duotame mieste, aplankyti kiekvieną miestą vienintelį kartą ir grįžti į pradinį miestą, tačiau grandinė, kuria keliauja prekybos agentas, turi būti pigiausia. Žinoma, šio prekybos agento uždavinio sprendimas yra ne paprastesnis nei nustatymas, ar grandinė egzistuoja.

 

Trijų komunalinių paslaugų uždavinys. Tarkime, yra 3 namai A, B ir C bei 3 komunalinės paslaugos X, Y ir Z (pavyzdžiui, telefonas, vanduo ir elektra). Jei namai ir komunalinės paslaugos yra grafo viršūnės, ar galima sujungti kiekvieną namą su kiekviena komunaline paslauga taip, kad briaunos nepersikirstų. Atsakymas – ne.

Grafas yra planarinis, jei jį galima nupiešti plokštumoje (bent vienu būdu) taip, kad nė viena pora briaunų nepersikirstų. Trijų komunalinių paslaugų uždavinio apibendrinimas – nustatyti, ar duotas grafas yra planarinis. Ši grafo savybė yra svarbi daugelyje taikymų. Pavyzdžiui, grafas gali vaizduoti elektrinę grandinę, kur viršūnės atitinka elementus, o briaunos ryšius tarp elementų. Ar galima suprojektuoti elektrinę grandinę taip, kad ryšiai nesikirstų?

 

Keturių spalvų uždavinys. Ar duotą planarinį grafą galima nuspalvinti ne daugiau kaip 4 spalvomis taip, kad nebūtų vienos spalvos kaimyninių viršūnių? Atsakymas į šį klausimą – taip, bet tai įrodyti sudėtinga. Iš tikrųjų, šis uždavinys buvo suformuluotas daugiau kaip prieš 100 metų, o įrodytas 1970-aisiais panaudojus kompiuterius.