Kas yra grafų teorija ir kaip apibrėžiamas grafikas?

1736 m., remiantis šveicarų fiziko matematiko Leonhardo Eulerio (1707-1783) darbais, buvo pastebėta, kad viršūnių seka apibrėžia kelias, tačiau jei minėtas kelias susideda iš skirtingų viršūnių be pasikartojančių briaunų, jis vadinamas keliu arba keliu eulerio; jei papildomai atvykstame į pradinį tašką, kiekvieną briauną kirsdami tik vieną kartą, tai turime Eulerio ciklą (grandinę).

Citata (APA)

Aleksandras Barraza | liepos mėn. 2022
Fizikos laipsnis

Savo ruožtu mes apibrėžiame grafiką kaip sutvarkytą porą (GOES) kur v žymi (netuščią) visų grafo viršūnių arba mazgų rinkinį, while A žymi visų kraštinių arba linijų, jungiančių grafo viršūnes, aibę (ji gali būti tuščia). Rinkinio elementai A gali būti pažymėta kaip nesutvarkyta pora {v, w}, kur v ir w yra elementai (mazgai arba viršūnės) v, tokiu būdu tada sakoma, kad v ir w yra gretimos viršūnės (jos sujungtos briauna).

Grafų teorija kyla iš Eulerio atsakymo į populiaraus išradingumo problemą, kuri galvojo, kaip pereiti septynis tiltus. prisijungė prie dviejų Karaliaučiaus bendruomenės salų (tuo metu priklausė Vokietijai, o šiuo metu Kaliningradas, Rusijoje), tarp jų ir su žemynu, nenaudodamas dviejų kartų tą patį tiltą ir atvykus į pradinį tašką (esantį žemyne), kad ir koks jis būtų, nustatant, kad šiuo atveju galiausiai ne galėtų.

Septynių Karaliaučiaus tiltų problema

Euleris sumodeliavo Karaliaučių kaip grafiką, kuriame kiekvienas taškas (viršūnė arba mazgas) žymi tiltą, o kiekviena linija (kraštas) – kelią sausumoje:

Koks šios problemos sprendimas?

nėra nei vieno sprendimas kuris atitinka nustatytas sąlygas, nes, kaip parodė Euleris, viršūnės nėra lyginio laipsnio, tai yra, lyginis eilučių skaičius neturi įtakos kiekvienam taškui _[3]. Neatrodo, kad galėtume daug nuveikti su struktūra, apibrėžta taip paprastai, tačiau, kaip dažnai būna matematika, Kartais viskas nėra taip, kaip atrodo. Taigi, viena produktyviausių, transversiškiausių ir tarpdiscipliniškiausių sričių _[4] apie žmogaus žinias, grafų teoriją.

Eulerio grafikai ar su Eulerio trajektorija?

Visi šie grafikai turi Eulerio kelius _[5]. Ar jie visi turi Eulerio ciklus?

Paimkime trečią grafiką:

Suskaičiuokime viršūnes:

Tada matome, kad kelias, apibrėžtas sekos {3,4,6,2,1,3,7,6,5,4,2}, yra Eulerio kelias, nes jis eina per visą grafiką be pasikartojančių briaunų, bet tai nėra Eulerio ciklas, nes nepasiekia pradžios taško. Kas būtų nutikę, jei viršūnes sunumeruotume kitaip? Nedaug, išskyrus tai, kad dabar kelias būtų apibrėžtas kitokia seka. Kas būtų nutikę, jei eitume kitokiais keliais, nei buvo pasiūlyta pirminiame sprendime? Į šį klausimą atsakyti yra šiek tiek sudėtingiau ir jis apima algoritmus, kuriais programinės įrangos inžinieriai paprastai džiaugiasi. programavimas.

Norėdami tiksliau įrodyti, kas čia atskleista, turime remtis tokiu rezultatu:

"Būk G sujungtas grafikas _[6]. Tada taip G turėk grandinė Eulerio, kiekvienos viršūnės laipsnis yra lyginis, o jei G turi Eulerio kelią, G turi lygiai dvi nelyginio laipsnio viršūnes _[7] (tiksliai viršūnės, kur kelias prasideda ir baigiasi)".

Tada galime patikrinti, ar iš tikrųjų mūsų paimtame grafike tik 3 ir 6 viršūnės turi nelyginį laipsnį (tai atsirastų net jei viršūnių numeracija būtų buvusi kitokia), todėl minėtas grafikas turi kelią eulerio _[8]. Likusius grafikus galime atlikti analogišku būdu ir patikrinti, ar jie tikrai turi kelius ir Eulerio ciklai, kitaip tariant, ar galime nubraižyti tokius grafikus nepaėmę pieštuko ir nekartodami linijos? Atsakymą į šį klausimą galima spręsti iš to, kas jau buvo paaiškinta iki šiol, tačiau tai yra pratimas įdomios smulkiosios motorikos, išradingumo ir kantrybės požiūriu, kviečiu skaitytoją surasti ir nupiešti 6 ar daugiau grafikus viršūnės su trajektorija Euleris.

Ar yra kitų grafikų tipų? Ar grafų teorija turi pritaikymų „realiame“ pasaulyje?

Šie grafikai, kuriuos apžvelgėme labai trumpai, yra tik vienas iš daugelio grafų tipų, kuriuos randame grafų teorijoje. Taip pat galime rasti grafikus, pvz., medžius, labai reprezentatyvius rinkiniuose, kur jų elementus galima klasifikuoti pagal hierarchijas ir skaičiavimus bei tikimybė_[9], dviženkliai, Hamiltono grafikai _[10]ir kt.

Grafinių modelių ir tinklų vaizdas Psycho., Ruiz, Ana María.

Šios mįslės, jei norime jas taip pavadinti, yra labai pritaikomos šiuolaikiniame pasaulyje, tokiose įvairiose situacijose kaip: biologija molekulinės _[11], kompiuterija_[12], telekomunikacijos _[13] ir tinklo analizė _[14]. Tuomet verta paklausti: ar bent jau smalsu, kad beveik problema banalus galų gale bus vienas įdomiausių ir ryškiausių matematikos rezultatų? Galbūt tam prireikė vieno žymiausių žmonijos protų indėlio.