Hva er grafteori, og hvordan defineres en graf som sådan?

I 1736, basert på arbeidet til den sveitsiske fysikeren-matematikeren Leonhard Euler (1707-1783), ble det observert at en rekke hjørner definerer en bane, men hvis nevnte bane består av forskjellige hjørner uten repeterende kanter, kalles den en bane eller bane eulerian; hvis vi i tillegg kommer til startpunktet, krysser hver kant bare én gang, så har vi en Eulerisk syklus (krets).

Sitat (APA)

alexander barraza | jul. 2022
Grad i fysikk

På sin side definerer vi en graf som et ordnet par (GÅR) hvor v angir det (ikke-tomme) settet med alle toppunkter eller noder i en graf, mens EN angir settet (det kan være tomt) av alle kantene eller linjene som forbinder toppunktene til en graf. Elementene i settet EN kan betegnes som et uordnet par {v, w} der v og w er elementer (noder eller hjørner) av v, på denne måten sies det da at v og w er tilstøtende hjørner (de er forbundet med en kant).

Grafteori oppstår fra svaret gitt av Euler på et problem med populær oppfinnsomhet som lurte på hvordan man krysser de syv broene som sluttet seg til to øyer i samfunnet Königsberg (en del av Tyskland på den tiden, og for tiden Kaliningrad, i Russland), mellom dem og med fastlandet uten å bruke to ganger den samme broen og ankommer startpunktet (plassert på fastlandet) uansett hva det måtte være, og fastslår at i dette tilfellet til slutt, ingen kunne.

Problemet med de syv broene i Königsberg

Euler modellerte Königsberg som en graf der hvert punkt (top eller node) representerer en bro og hver linje (kant) en bane på land:

Hva er løsningen på dette problemet?

det er ikke en løsning som oppfyller de pålagte betingelsene, siden, som Euler viste, toppunktene ikke er av jevn grad, det vil si at et jevnt antall linjer ikke påvirker hvert punkt _[3]. Det virker imidlertid ikke som om vi kan gjøre mye med en struktur definert så enkelt som dette, som ofte er tilfelle i matte, Noen ganger er ikke ting som de ser ut til. Dermed et av de mest produktive, tverrfaglige og tverrfaglige områdene _[4] av menneskelig kunnskap, grafteori.

Euleriske grafer eller med Eulersk bane?

De følgende grafene har alle Eulerske baner _[5]. Har de alle Euleriske sykluser?

La oss ta den tredje grafen:

La oss nummerere toppunktene:

Vi ser da at banen definert av sekvensen {3,4,6,2,1,3,7,6,5,4,2} er en Eulersk bane, siden den går gjennom hele grafen uten å gjenta kanter, men det er ikke en Eulerisk syklus, siden den ikke når startpunktet. Hva ville ha skjedd hvis vi nummererte toppunktene annerledes? Ikke mye, bortsett fra at nå ville banen bli definert av en annen rekkefølge. Hva ville ha skjedd hvis vi fulgte andre veier enn den som ble foreslått i vår første løsning? Dette spørsmålet er litt mer komplekst å svare på, og det involverer algoritmer som programvareingeniører vanligvis er fornøyd med. programmering.

For et mer strengt bevis på det som er eksponert her, må vi referere til følgende resultat:

"Være G en tilkoblet graf _[6]. Så ja G ha en krets Euler, graden av hvert toppunkt er jevn, mens if G har en Euler-bane, G har nøyaktig to hjørner av oddetall _[7] (nøyaktig toppunktene der banen starter og slutter)".

Vi kan da bekrefte at faktisk, i grafen vi tar, er det bare toppunktene 3 og 6 som har en odde grad (dette ville forekomme selv om nummereringen av toppunktene hadde vært annerledes), derfor har nevnte graf en bane eulerian _[8]. For de resterende grafene kan vi fortsette på en analog måte og verifisere om de faktisk har stier og Euleriske sykluser, eller sagt på en annen måte, kan vi tegne slike grafer uten å ta opp blyanten og gjenta linjer? Svaret på dette spørsmålet kan utledes fra det som allerede er forklart så langt, men det utgjør en øvelse interessant med tanke på finmotorikk, oppfinnsomhet og tålmodighet, jeg inviterer leseren til å finne og tegne grafer på 6 eller flere hjørner med bane Eulerian.

Finnes det andre typer grafer? Har grafteori applikasjoner i den 'virkelige' verden?

Disse grafene som vi har gjennomgått veldig kort, er bare en av mange typer grafer som vi finner i grafteori. Vi kan også finne grafer som trær, veldig representative i sett der elementene deres kan klassifiseres i hierarkier og i telleberegninger og sannsynlighet_[9], digrafer, Hamiltonske grafer _[10], etc.

Bilde av grafiske modeller og nettverk i psyko., av Ruiz, Ana María.

Disse gåtene, hvis vi vil kalle dem det, har enorm anvendelighet i dagens verden, i så forskjellige situasjoner som: biologi molekylær _[11], databehandling_[12], telekommunikasjon _[13] og nettverksanalyse _[14]. Det er verdt å spørre da: Er det ikke i det minste merkelig at et problem av en nesten banal vil ende opp med å bli et av de mest interessante og iøynefallende resultatene av matematikk? For dette var kanskje bidraget fra et av menneskehetens mest berømte sinn nødvendig.