Kaj je teorija grafov in kako je graf definiran kot tak?

Leta 1736 je bilo na podlagi dela švicarskega fizika in matematika Leonharda Eulerja (1707-1783) ugotovljeno, da zaporedje vozlišč določa pot, če pa je omenjena pot sestavljena iz različnih oglišč brez ponavljajočih se robov, se imenuje pot ali pot eulerjev; če poleg tega pridemo na začetno točko in prečkamo vsak rob samo enkrat, potem imamo Eulerjev cikel (krog).

Citat (APA)

aleksander barraza | jul. 2022
Diploma iz fizike

S svoje strani definiramo graf kot urejen par (GRE) kje v označuje (neprazno) množico vseh vozlišč ali vozlišč grafa, medtem ko A označuje množico (lahko je prazna) vseh robov ali črt, ki povezujejo oglišča grafa. Elementi kompleta A lahko označimo kot neurejen par {v, w}, kjer sta v in w elementa (vozlišča ali oglišča) v, na ta način potem rečemo, da sta v in w sosednji točki (združuje ju rob).

Teorija grafov izhaja iz odgovora, ki ga je dal Euler na problem ljudske iznajdljivosti, ki se je spraševala, kako prečkati sedem mostov, združil dva otoka skupnosti Königsberg (takrat del Nemčije in trenutno Kaliningrad v Rusiji), med njima in s celino brez uporabe dveh krat isti most in prihod na izhodiščno točko (ki se nahaja na celini), karkoli že je, pri čemer ugotavljamo, da v tem primeru na koncu ne lahko.

Problem sedmih mostov Königsberga

Euler je Königsberg modeliral kot graf, kjer vsaka točka (vozlišče ali vozlišče) predstavlja most in vsaka črta (rob) pot na kopnem:

Kakšna je rešitev tega problema?

ni enega rešitev ki ustreza zahtevanim pogojem, saj, kot je pokazal Euler, oglišča niso sode stopnje, kar pomeni, da sodo število premic ne vpliva na vsako točko _[3]. Zdi se, da s tako preprosto definirano strukturo ne moremo storiti veliko, kot je pogosto v matematika, Včasih stvari niso takšne, kot se zdijo. Tako eno najbolj plodovitih, transverzalnih in interdisciplinarnih področij _[4] človeškega znanja, teorija grafov.

Eulerjevi grafi ali z Eulerjevo trajektorijo?

Vsi naslednji grafi imajo Eulerjeve poti _[5]. Ali imajo vsi Eulerjeve cikle?

Vzemimo tretji graf:

Oštevilčimo oglišča:

Vidimo torej, da je pot, definirana z zaporedjem {3,4,6,2,1,3,7,6,5,4,2} Eulerjeva pot, saj gre skozi celoten graf brez ponavljajočih se robov, vendar ni Eulerjev cikel, saj ne doseže začetne točke. Kaj bi se zgodilo, če bi vozlišča oštevilčili drugače? Ne veliko, le da bi zdaj pot začrtala drugačna sukcesija. Kaj bi se zgodilo, če bi sledili drugačni poti od tiste, ki je bila predlagana v naši začetni rešitvi? Odgovor na to vprašanje je nekoliko bolj zapleten in vključuje algoritme, nad katerimi so programski inženirji običajno navdušeni. programiranje.

Za bolj strog dokaz tega, kar je tukaj izpostavljeno, se moramo sklicevati na naslednji rezultat:

"bodi G povezan graf _[6]. Potem ja G imeti a vezje Eulerja je stopnja vsakega vozlišča soda, medtem ko je če G ima Eulerjevo pot, ima G natanko dve točki lihe stopnje _[7] (točno točke, kjer se pot začne in konča)".

Nato lahko preverimo, da imata v grafu, ki ga vzamemo, le točki 3 in 6 liho stopnjo (to zgodil tudi, če bi bilo oštevilčenje vozlišč drugačno), zato ima omenjeni graf pot Eulerian _[8]. Za preostale grafe lahko nadaljujemo na podoben način in preverimo, ali res imajo poti in Eulerjevi cikli, ali drugače povedano, ali lahko narišemo takšne grafe, ne da bi vzeli svinčnik in ponavljali črte? Odgovor na to vprašanje je mogoče razbrati iz tega, kar je bilo do sedaj pojasnjeno, vendar predstavlja vajo zanimivo z vidika fine motorike, iznajdljivosti in potrpežljivosti, vabim bralca, da poišče in nariše grafe 6 ali več oglišča z trajektorija Eulerjev.

Ali obstajajo druge vrste grafov? Ali ima teorija grafov aplikacije v 'resničnem' svetu?

Ti grafi, ki smo jih zelo na kratko pregledali, so samo ena od mnogih vrst grafov, ki jih najdemo v teoriji grafov. Najdemo lahko tudi grafe, kot so drevesa, ki so zelo reprezentativni v množicah, kjer je mogoče njihove elemente razvrstiti v hierarhije in pri štetju izračunov in verjetnost_[9], digrafi, Hamiltonovi grafi _[10]itd.

Podoba grafičnih modelov in omrežij v psihologiji, Ruiz, Ana María.

Te enigme, če jih tako imenujemo, imajo izjemno uporabnost v današnjem svetu, v tako različnih situacijah, kot so: biologija molekularni _[11], računalništvo_[12], telekomunikacije _[13] in analizo omrežja _[14]. Vredno se je torej vprašati: ali ni vsaj čudno, da je problem skoraj banalno bo na koncu postal eden najbolj zanimivih in vidnih rezultatov matematike? Morda je bil za to potreben prispevek enega najslavnejših umov človeštva.