Što je teorija grafova i kako se graf definira kao takav?

Godine 1736., na temelju rada švicarskog fizičara-matematičara Leonharda Eulera (1707-1783), uočeno je da niz vrhova definira put, međutim, ako se navedeni put sastoji od različitih vrhova bez ponavljajućih bridova, naziva se put ili put Eulerov; ako dodatno dođemo do početne točke, prolazeći svaki rub samo jednom, tada imamo Eulerov ciklus (krug).

Citat (APA)

alexander barraza | srp. 2022
Diploma iz fizike

Sa svoje strane, mi definiramo graf kao uređeni par (IDE) gdje v označava (neprazan) skup svih vrhova ili čvorova grafa, dok A označava skup (može biti prazan) svih bridova ili linija koje spajaju vrhove grafa. Elementi skupa A može se označiti kao neuređeni par {v, w} gdje su v i w elementi (čvorovi ili vrhovi) v, na taj način se onda kaže da su v i w susjedni vrhovi (spojeni su bridom).

Teorija grafova proizlazi iz odgovora koji je Euler dao na problem popularne domišljatosti koja se pitala kako prijeći sedam mostova koji spojio dva otoka zajednice Königsberg (dio Njemačke u to vrijeme, a trenutno Kalinjingrad, u Rusiji), između njih i s kopnom bez korištenja dva puta isti most i dolazak na početnu točku (koja se nalazi na kopnu) kakva god ona bila, utvrđujući da u ovom slučaju, u konačnici, ne mogao.

Problem sedam mostova Königsberga

Euler je modelirao Königsberg kao graf gdje svaka točka (vrh ili čvor) predstavlja most, a svaka linija (rub) put na kopnu:

Koje je rješenje za ovaj problem?

ne postoji ni jedan riješenje koji zadovoljava nametnute uvjete, jer, kao što je pokazao Euler, vrhovi nisu parnog stupnja, odnosno paran broj linija ne utječe na svaku točku _[3]. Međutim, ne čini se da možemo učiniti mnogo s tako jednostavno definiranom strukturom, kao što je to često slučaj u matematika, Ponekad stvari nisu onakve kakvima se čine. Dakle, jedno od najplodnijih, transverzalnih i interdisciplinarnih područja _[4] ljudskog znanja, teorija grafova.

Eulerovi grafovi ili s Eulerovom putanjom?

Svi sljedeći grafovi imaju Eulerove staze _[5]. Imaju li svi Eulerove cikluse?

Uzmimo treći graf:

Označimo vrhove brojevima:

Vidimo dakle da je put definiran nizom {3,4,6,2,1,3,7,6,5,4,2} Eulerov put, jer prolazi kroz cijeli graf bez ponavljanja bridova, ali nije Eulerov ciklus, budući da ne doseže početnu točku. Što bi se dogodilo da smo vrhove drugačije numerirali? Ne puno, osim što bi sada put bio definiran drugačijim sukcesijom. Što bi se dogodilo da smo slijedili putove drugačije od onih predloženih u našem početnom rješenju? Ovo je pitanje malo složenije za odgovoriti, a uključuje algoritme s kojima su softverski inženjeri obično oduševljeni. programiranje.

Za rigorozniji dokaz onoga što je ovdje izloženo, moramo se pozvati na sljedeći rezultat:

"Biti G povezani graf _[6]. Onda da G imati strujni krug Euler, stupanj svakog vrha je paran, dok je if G ima Eulerov put, G ima točno dva vrha neparnog stupnja _[7] (točno vrhovi gdje staza počinje i završava)".

Zatim možemo potvrditi da, zapravo, u grafu koji uzmemo, samo vrhovi 3 i 6 imaju neparan stupanj (ovo dogodio čak i da je numeriranje vrhova bilo drugačije), stoga navedeni graf ima put Eulerov _[8]. Za preostale grafove možemo nastaviti na analogan način i provjeriti imaju li doista staze i Eulerovi ciklusi, ili drugačije rečeno, možemo li crtati takve grafove bez uzimanja olovke i ponavljanja linije? Odgovor na ovo pitanje može se zaključiti iz onoga što je već objašnjeno do sada, međutim, on predstavlja vježbu zanimljiv u smislu fine motorike, domišljatosti i strpljenja, pozivam čitatelja da pronađe i nacrta grafikone od 6 ili više vrhovi sa putanja Eulerov.

Postoje li druge vrste grafikona? Ima li teorija grafova primjenu u 'stvarnom' svijetu?

Ovi grafovi koje smo vrlo kratko pregledali samo su jedan od mnogih tipova grafova koje nalazimo u teoriji grafova. Također možemo pronaći grafove kao što su stabla, vrlo reprezentativna u skupovima gdje se njihovi elementi mogu klasificirati u hijerarhije i u izračunima brojanja i vjerojatnost_[9], digrafovi, Hamiltonovi grafovi _[10]itd.

Slika grafičkih modela i mreža u psihologiji, Ruiz, Ana María.

Ove enigme, ako ih želimo tako nazvati, imaju ogromnu primjenjivost u današnjem svijetu, u različitim situacijama kao što su: biologija molekularni _[11], računalstvo_[12], telekomunikacije _[13] i analiza mreže _[14]. Vrijedno je onda zapitati se: Nije li u najmanju ruku čudno da problem gotovo banalno će na kraju biti jedan od najzanimljivijih i najuočljivijih rezultata matematike? Možda je za to bio neophodan doprinos jednog od najslavnijih umova čovječanstva.