Grafų teorija: Medžiai

Grafų teorijos pradžia, kaip matematinė disciplina, buvo pradėta nagrinėti 1736m. Pirmasis grafų teorijos uždavinys, kurį sėkmingai išsprendė mokslininkas L.Oileris, buvo apie Karaliaučiaus tiltus. Jis ne tik, kad šį uždavinį išsprendė, bet ir suformulavo būtinas ir pakankamas sąlygas, kurias tenkinant grafas turi specialų maršrutą, kuris dabar vadinamas Oilerio ciklu (grandine).
Tačiau pratęsti grafų teorijos uždavinių sprendimus jau „reikalavo“ tiksliosios mokslo disciplinos: chemija, fizika, matematika, biologija. Juk 100 metų laikotarpyje šio uždavinio sprendinys buvo vienintelis grafų teorijos rezultatas. Pirmasis iš žymesnių mokslininkų, elektrikas Kirchgofas pritaikė medžių teoriją elektrinėms grandinėms nagrinėti. Nuo jo daug neatsiliko ir matematikas A.Keli. Jis tyrė trijų tipų medžius, norėdamas apskaičiuoti organinių junginių izomerų skaičių, kristalų modelius, molekulių struktūras. Vėliau matematikas Žordanas juos pradėjo tirti kaip grynai matematinius objektus. Formaliosios logikos vystymasis privertė atkreipti dėmesį į binarinių sąryšių formas grafų teorijoje. Dauguma populiarių galvosūkių (uždaviniai apie: šachmatų valdovę (žirgus), 15 – a mergaičių, sargybinių uždavinys, penkių valdovių uždavinys ir kt.) reikalavo tikslių sprendimo žingsnių ir tai suvesdavo į grafų teorijos formas, kuriose panaudojant grafus, galima išspręsti konkretų uždavinį.
Pakilimas, vystant grafų teoriją buvo 1852m., A.De Morgano iškelta keturių spalvų hipotezė. Ji grafų teorijos vystymesi suvaidino tokį pat vaidmenį, kaip ir didžioji Ferma teorema skaičių teorijoje. Keturių spalvų hipotezė buvo įrodyta 1976m. Visi pilnai sutaria, kad grafų teorijos, kaip atskiros matematikos šakos gimimas yra 1936m. Tada matematikas D.Kionigas išleido monografiją „Baigtinių ir begalinių grafų teorija“. Jis pirmasis vietoje įvairiuose moksluose naudojamų skirtingų schemų pavadinimų: sociogramos, simpleksai, grandinės, diagramos, ryšių tinklai, vandentiekio tinklai, genealoginiai medžiai ir kitų, pasiūlė vartoti vieną terminą – grafas. Šis faktas rodo, kad grafai įra įvairiausios fizinės prigimties reiškinių matematiniai modeliai. Tai ir lemia grafų teorijos, kaip savarankiškos matematikos šakos, audringą vystimąsi ir plačias taikymo galimybes.
Šiame referate apžvelgsiu populiarią grafų teorijos sritį – medžių teoriją.
Medžiai
APIBRĖŽIMAS
Jei vienas jungiųjų grafų ribinis atvejis yra pilnieji grafai t,y. jungieji grafai, turintys didžiausią briaunų...

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!