Vad är grafteori och hur definieras en graf som sådan?

År 1736, baserat på den schweiziske fysikern-matematikern Leonhard Eulers (1707-1783) arbete, observerades att en följd av hörn definierar en bana, men om nämnda bana består av olika hörn utan upprepade kanter, kallas den en bana eller bana eulerian; om vi dessutom kommer till startpunkten och korsar varje kant bara en gång, så har vi en Eulerisk cykel (krets).

Citat (APA)

alexander barraza | jul. 2022
Examen i fysik

För sin del definierar vi en graf som ett ordnat par (GÅR) var v betecknar den (icke tomma) uppsättningen av alla hörn eller noder i en graf, medan A betecknar mängden (den kan vara tom) av alla kanter eller linjer som förenar hörn av en graf. Elementen i uppsättningen A kan betecknas som ett oordnat par {v, w} där v och w är element (noder eller hörn) av v, på detta sätt sägs det då att v och w är angränsande hörn (de är sammanfogade av en kant).

Grafteori uppstår från svaret som Euler gav på ett problem med populär uppfinningsrikedom som undrade hur man korsar de sju broarna som gick samman med två öar i samhället Königsberg (en del av Tyskland vid den tiden, och för närvarande Kaliningrad, i Ryssland), mellan dem och med fastlandet utan att använda två gånger samma bro och anländer till startpunkten (belägen på fastlandet) vad det än må vara, vilket bestämmer att i det här fallet, i slutändan, skulle kunna.

Problemet med de sju broarna i Königsberg

Euler modellerade Königsberg som en graf där varje punkt (vertex eller nod) representerar en bro och varje linje (kant) en bana på land:

Vad är lösningen på detta problem?

det finns ingen lösning som uppfyller de uppställda villkoren, eftersom, som Euler visade, hörn inte är av jämn grad, det vill säga ett jämnt antal linjer påverkar inte varje punkt _[3]. Det verkar inte som att vi kan göra mycket med en struktur definierad så enkelt som denna, men som ofta är fallet i matematik, Ibland är saker och ting inte som de verkar. Alltså ett av de mest produktiva, tvärgående och tvärvetenskapliga områdena _[4] av mänsklig kunskap, grafteori.

Euleriska grafer eller med Eulerisk bana?

Följande grafer har alla Euleriska banor _[5]. Har de alla Euleriska cykler?

Låt oss ta den tredje grafen:

Låt oss numrera hörnen:

Vi ser då att den väg som definieras av sekvensen {3,4,6,2,1,3,7,6,5,4,2} är en Eulerisk väg, eftersom den går igenom hela grafen utan att upprepa kanter, men det är inte en Eulerisk cykel, eftersom den inte når startpunkten. Vad skulle ha hänt om vi numrerade hörnen annorlunda? Inte mycket, förutom att nu skulle vägen definieras av en annan följd. Vad skulle ha hänt om vi följde andra vägar än den som föreslogs i vår ursprungliga lösning? Den här frågan är lite mer komplex att besvara, och den involverar algoritmer som mjukvaruingenjörer vanligtvis är nöjda med. programmering.

För ett mer rigoröst bevis på vad som exponeras här måste vi hänvisa till följande resultat:

"Vara G en sammankopplad graf _[6]. I så fall, ja G ha en krets Euler, graden av varje vertex är jämn, medan if G har en Euler-bana, G har exakt två hörn av udda grad _[7] (exakt de hörn där banan börjar och slutar)".

Vi kan då verifiera att i själva verket i grafen vi tar, bara hörn 3 och 6 har en udda grad (denna skulle inträffa även om numreringen av hörn hade varit annorlunda), därför har nämnda graf en väg eulerian _[8]. För de återstående graferna kan vi gå vidare på ett analogt sätt och verifiera om de verkligen har vägar och Euleriska cykler, eller uttryckt på annat sätt, kan vi rita sådana grafer utan att ta upp pennan och upprepa rader? Svaret på denna fråga kan härledas från vad som redan har förklarats hittills, men det utgör en övning intressant när det gäller finmotorik, uppfinningsrikedom och tålamod, jag uppmanar läsaren att hitta och rita grafer på 6 eller fler hörn med bana Eulerian.

Finns det andra typer av grafer? Har grafteori tillämpningar i den "verkliga" världen?

Dessa grafer som vi har granskat mycket kort, är bara en av de många typer av grafer som vi hittar inom grafteorin. Vi kan också hitta grafer som träd, mycket representativa i mängder där deras element kan klassificeras i hierarkier och i räkneberäkningar och sannolikhet_[9], digrafer, Hamiltonska grafer _[10], etc.

Bild av grafiska modeller och nätverk i psyko., av Ruiz, Ana María.

Dessa gåtor, om vi vill kalla dem så, har enorm tillämpbarhet i dagens värld, i så olika situationer som: biologi molekyl- _[11], datoranvändning_[12], telekommunikation _[13] och nätverksanalys _[14]. Det är värt att fråga då: Är det inte åtminstone konstigt att ett problem av en nästan banal kommer att bli ett av matematikens mest intressanta och iögonfallande resultat? För detta var kanske bidraget från ett av mänsklighetens mest berömda sinnen nödvändigt.