top


Konspektai.com > Matematika > Klasikiniai grafų teorijos uždaviniai, jų sprendimas, algoritmai. Paieška ir ribojimų tenkinimas (search and constraint satisfacion). Taikymai uždaviniams spręsti
Konspektai kursiniai referatai diplominiai

Klasikiniai grafų teorijos uždaviniai, jų sprendimas, algoritmai. Paieška ir ribojimų tenkinimas (search and constraint satisfacion). Taikymai uždaviniams spręsti. Referatas

(Matematika. Referatas, 9 puslapiai, 167kB)
Darbe esantys žodžiai: Turinys. Įvadas. Artimiausio kaimyno metodas. Viršūnių įterpimo metodas. Euristiniai algoritmai. Taikymai. Literatūra. Grafų teorija – matematikos sritis, nagrinėjanti grafus. Grafas yra sudarytas iš lankais (briaunomis) sujungtų viršūnių, kurį galima įsivaizduoti kaip figūrą. Jei grafo briaunos turi kryptį - tai orientuotas grafas. Jei grafas turi tik vieną viršūnę ir nei vienos briaunos - tai trivialus grafas. Grafas be briaunų – tuščias grafas, o be viršūnių ir be briaunų – nulinis grafas. 1736 m. buvo nagrinėtas pirmasis grafų teorijos uždavinys. Uždavinys buvo apie Karaliaučiaus (Kionigsbergo) tiltus. Šį uždavinį sėkmingai išsprendė L.Oileris. 1852 m. A.De Morgano iškėlė keturių spalvų hipotezę. Ši keturių spalvų hipotezė 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
Vardas: Rugilė
Darbo pavadinimas: Klasikiniai grafų teorijos uždaviniai, jų sprendimas, algoritmai. Paieška ir ribojimų tenkinimas (search and constraint satisfacion). Taikymai uždaviniams spręsti
Kategorija: Matematika
Darbo tipas: Referatas
Puslapių skaičius: 9 [?]
Referato dalykas: Matematikos referatas
Parsisiųsta: 0 kartų.
Archyvo dydis: 167 kB
Bylos pavadinimas: klasikiniai_grafu_teorijos.zip
klasikiniai_grafu_teorijos.zip
Norėdami parsisiųsti bylą siųskite SMS trumpuoju numeriu 1679 su raktažodžiu DJP. Tai jums kainuos 0.87 EUR. Gautą į telefoną SMS raktą įrašykite į auščiau esantį laukelį.
Atsiskaitant per banką spauskite: čia.
Jei norite parsisiųsti nemokamai spauskite čia.

0
0
Pranešti apie netikslumus Pranešti apie netikslumus
Su darbu susiję žodžiai: artimiausio kaimyn.

Paieška


bottom

Warning: session_write_close(): write failed: Disk quota exceeded (122) in /home/konspek1/domains/konspektai.com/public_html/libraries/joomla/session/session.php on line 557

Warning: session_write_close(): Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/home/konspek1/tmp) in /home/konspek1/domains/konspektai.com/public_html/libraries/joomla/session/session.php on line 557