Klasikiniai grafų teorijos uždaviniai, jų sprendimas, algoritmai

grafas.
Karaliaučiaus (Kionigsbergo) tiltus. Šį uždavinį sėkmingai išsprendė L.Oileris.
buvo įrodyta 1976 m. Buvo pilnai perrinkti kai kurie grafų variantai ir tam sunaudota 1200
kompiuterinio laiko valandų.
1936 m. matematikas D.Kionigas išleido monografiją "Baigtinių ir begalinių grafų
teorija". Jis pirmasis pasiūlė naudoti vieną terminą "grafas" vietoje įvairiuose moksluose
naudojamų skirtingų schemų pavadinimų: simpleksai (topologija), grandinės (fizika),
diagramos (ekonomika), sociogramos (pcichologija) ir t.t.
Hamiltono maršrutai
Jei kiekviena grafo viršūnė jungima briaunomis su visomis likusiomis
viršūnėmis, tai toks grafas yra pilnasis grafas.
Maršrutas (kelias) apeinantis visas grafo viršūnes po vieną kartą vadinamas Hamiltono
maršrutu.
Maršrutas: 1,5,3,2,4
Jei pradinė ir galinė maršruto viršūnės sutampa, tai šis maršrutas vadinamas Hamiltono ciklu.
4
Ciklas: 1,4,2,3,5,1 ; Maršrutas: 5,3,2,1,4
Jei pradinė ir galinė maršruto viršūnės nesutampa, tai šis maršrutas vadinamas Hamiltono
grandine.
Grafas turintis Hamiltono maršrutą vadinamas Hamiltono grafu.
Grafas, kuris yra pilnasis, jis yra Hamiltono grafas.
Artimiausio kaimyno metodas
Keliaujančio pirklio (komivojažieriaus) uždavinys – grafų teorijoje sprendžiamas
uždavinys, formuluojamas taip: Turint tam tikrą kiekį miestų, taip pat kelionės iš vieno
miesto į kitą kainas, reikia rasti pigiausią maršrutą, kad aplankius kiekvieną miestą maršrutas
baigtųsi pradiniame mieste. Grafų teorijoje galima uždavinį performuluoti – kaip rasti
mažiausio svorio Hamiltono ciklą grafe su svoriais.
Pradėdami nuo kažkurios grafo viršūnės, pastoviai renkamės iš neaplankytų viršūnių pačią
„artimiausią“ (su kuo mažesniu briaunos svoriu). Kai nebelieka neaplankytų viršūnių –
grįžtame į pradinę.
Pavaizuosime paieškų medį gilyn su grįžimu perrinkti maršrutai. Raide “H” pažymėti
Hamiltono ciklai.
Turime aplankyti kiekvieną viršūnę po vieną kartą ir grįžti į pirmąją viršūnę. Koks
turi būti maršrutas, kad jo ilgis būtų trumpiausias? Šio grafo trumpiausio Hamiltono ciklo
paieška galima dviem supaprastintais sprendimo būdais:
artimiausios viršūnės metodas ir
viršūnių įterpimo metodas.
Artimiausios viršūnės metodas
5
1. Apskaičiuosime trumpiausią Hamiltono ciklą artimiausios viršūnės metodu, esant tokiai
grafo atstumų matricai:
024845
2073104
470753
837062
4105601
54321
=C
Iš pirmosios viršūnės eisime į 5-ąją viršūnę, nes 1),0/(min 115115 ≠≠=
≤≤
jccc jjj
. Iš atstumų
matricos pašalinę 1-ąją eilutę ir 5-ąjį stulpelį, gausime:
24845
073104
70753
37062
4321
=C
Dabar, iš 5-osios viršūnės keliausime į 3-iąją, nes )0/(min 55153 ≠=
≠ jjj
ccc . Iš perskaičiuotos
atstumų matricos pašaliname 5-ąją eilutę ir 3-iąjį stulpelį. Gauname:
03104
7753
3062
421
=C
Toliau iš 3-iosio viršūnės eisime į 4-ąją viršūnę, nes...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!