Meniu
- Anglų kalba
- Aplinka
- Apskaita
- Astronomija
- Biologija
- Chemija
- Dailė
- Edukologija
- Ekonomika
- Elektronika
- Ergonomika
- Etika
- Filosofija
- Fizika
- Geografija
- Informatika
- Istorija
- Kalbos kultūra
- Kita
- Lietuvių kalba
- Logika
- Lotynų kalba
- Matematika
- Mechanika
- Medicina
- Menai
- Muzika
- Pedagogika
- Politologija
- Psichologija
- Raštvedyba
- Religija
- Sauga
- Sociologija
- Sportas
- Statyba
- Teisė
- Transportas
- Užsienio lit.
- Vadyba
- Vokiečių kalba
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) Pranešti apie netikslumus 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
 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. 
 Su darbu susiję žodžiai: artimiausio kaimyn. | ||
Paieška
Įvertinimų top
Naujos paieškos
Reklama
