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

I 1736, baseret på den schweiziske fysiker-matematiker Leonhard Eulers (1707-1783) arbejde, blev det observeret, at en række hjørner definerer en sti, men hvis denne sti består af forskellige hjørner uden gentagne kanter, kaldes den en sti eller sti eulerian; hvis vi derudover ankommer til udgangspunktet og krydser hver kant kun én gang, så har vi en Eulersk cyklus (kredsløb).

Citat (APA)

alexander barraza | jul. 2022
Grad i fysik

For sin del definerer vi en graf som et ordnet par (GOES) hvor v angiver det (ikke-tomme) sæt af alle knudepunkter eller knudepunkter i en graf, mens EN angiver sættet (det kan være tomt) af alle de kanter eller linjer, der forbinder hjørnerne af en graf. Elementerne i sættet EN kan betegnes som et uordnet par {v, w} hvor v og w er elementer (knuder eller hjørner) af v, på denne måde siger man så, at v og w er tilstødende hjørner (de er forbundet med en kant).

Grafteori udspringer af Eulers svar på et problem med populær opfindsomhed, der spekulerede på, hvordan man krydser de syv broer, der sluttede sig til to øer i samfundet Königsberg (en del af Tyskland på det tidspunkt, og i øjeblikket Kaliningrad, i Rusland), mellem dem og med fastlandet uden at bruge to gange den samme bro og ankommer til startpunktet (placeret på fastlandet), hvad det end måtte være, hvilket bestemmer, at i dette tilfælde i sidste ende ikke kunne.

Problemet med de syv broer i Königsberg

Euler modellerede Königsberg som en graf, hvor hvert punkt (top eller knude) repræsenterer en bro og hver linje (kant) en sti på land:

Hvad er løsningen på dette problem?

der er ikke en løsning som opfylder de pålagte betingelser, da, som Euler viste, hjørnerne ikke er af lige grad, det vil sige, at et lige antal linjer ikke påvirker hvert punkt _[3]. Det ser dog ikke ud til, at vi kan gøre meget med en struktur defineret så simpelt som denne, som det ofte er tilfældet i matematik, Nogle gange er tingene ikke, som de ser ud til. Således et af de mest produktive, tværgående og tværfaglige områder _[4] af menneskelig viden, grafteori.

Eulerske grafer eller med Eulersk bane?

De følgende grafer har alle Eulerske stier _[5]. Har de alle Euleriske cyklusser?

Lad os tage den tredje graf:

Lad os nummerere hjørnerne:

Vi ser da, at stien defineret af sekvensen {3,4,6,2,1,3,7,6,5,4,2} er en Eulersk vej, da den går gennem hele grafen uden at gentage kanter, men det er ikke en Eulersk cyklus, da den ikke når startpunktet. Hvad ville der være sket, hvis vi nummererede hjørnerne anderledes? Ikke meget, bortset fra at nu ville stien blive defineret af en anden rækkefølge. Hvad ville der være sket, hvis vi fulgte andre veje end den, der blev foreslået i vores oprindelige løsning? Dette spørgsmål er lidt mere komplekst at besvare, og det involverer algoritmer, som softwareingeniører normalt er glade for. programmering.

For et mere stringent bevis på, hvad der er afsløret her, skal vi henvise til følgende resultat:

"Være G en forbundet graf _[6]. Så ja G have en kredsløb Euler, graden af ​​hvert toppunkt er lige, mens if G har en Euler-sti, G har præcis to hjørner af ulige grad _[7] (nøjagtig de hjørner, hvor stien starter og slutter)".

Vi kan så verificere, at i den graf, vi tager, faktisk kun toppunkter 3 og 6 har en ulige grad (dette ville forekomme, selvom nummereringen af ​​toppunkter havde været anderledes), derfor har nævnte graf en sti eulerian _[8]. For de resterende grafer kan vi fortsætte på en analog måde og kontrollere, om de faktisk har stier og Euleriske cyklusser, eller sagt på en anden måde, kan vi tegne sådanne grafer uden at tage blyanten op og gentage linjer? Svaret på dette spørgsmål kan udledes af det, der allerede er blevet forklaret indtil videre, men det er en øvelse interessant med hensyn til finmotorik, opfindsomhed og tålmodighed, jeg inviterer læseren til at finde og tegne grafer med 6 eller flere hjørner med bane Eulerian.

Findes der andre typer grafer? Har grafteori anvendelse i den 'virkelige' verden?

Disse grafer, som vi har gennemgået meget kort, er blot en af ​​de mange typer grafer, som vi finder i grafteori. Vi kan også finde grafer som træer, meget repræsentative i sæt, hvor deres elementer kan klassificeres i hierarkier og i tælleberegninger og sandsynlighed_[9], digrafer, Hamiltonske grafer _[10], etc.

Billede af grafiske modeller og netværk i psyko., af Ruiz, Ana María.

Disse gåder, hvis vi vil kalde dem det, har enorm anvendelighed i nutidens verden, i situationer så forskellige som: biologi molekylær _[11], edb_[12], telekommunikation _[13] og netværksanalyse _[14]. Det er da værd at spørge: Er det ikke i det mindste mærkeligt, at et problem af en næsten banal vil ende med at blive et af de mest interessante og iøjnefaldende resultater af matematik? Måske var bidraget fra et af menneskehedens mest berømte hjerner nødvendigt til dette.