Mikä on graafiteoria ja miten graafi määritellään sellaiseksi?

Vuonna 1736 sveitsiläisen fyysikko-matemaatikon Leonhard Eulerin (1707-1783) työhön perustuen havaittiin, että peräkkäinen pisteitä määrittelee polku, mutta jos mainittu polku koostuu eri pisteistä ilman toistuvia reunoja, sitä kutsutaan poluksi tai poluksi eulerian; jos lisäksi saavumme aloituspisteeseen ylittäen kunkin reunan vain kerran, niin meillä on Eulerin sykli (piiri).

Lainaus (APA)

Aleksanteri Barraza | heinäkuuta 2022
Fysiikan tutkinto

Määrittelemme puolestaan ​​graafin järjestetyksi pariksi (MENE) missä v ilmaisee graafin kaikkien kärkien tai solmujen (ei tyhjän) joukon, while A määrittää joukon (se voi olla tyhjä) kaikista graafin kärkipisteitä yhdistävistä reunoista tai viivoista. Sarjan elementit A voidaan nimetä järjestämättömäksi pariksi {v, w}, jossa v ja w ovat elementtejä (solmuja tai pisteitä) v, tällä tavalla sanotaan sitten, että v ja w ovat vierekkäisiä pisteitä (niitä yhdistää reuna).

Graafiteoria syntyy Eulerin antamasta vastauksesta yleisen kekseliäisyyden ongelmaan, joka pohti, kuinka ylittää seitsemän siltaa, jotka liittyi kahteen Königsbergin yhteisön saareen (silloin osa Saksaa ja nykyään Kaliningrad Venäjällä), niiden väliin ja mantereen kanssa käyttämättä kahta kertaa sama silta ja saapuminen lähtöpisteeseen (sijaitsee mantereella), mikä se sitten onkin, mikä määrittää, että tässä tapauksessa lopulta ei voisi.

Königsbergin seitsemän sillan ongelma

Euler mallinsi Königsbergin kaaviona, jossa jokainen piste (kärkipiste tai solmu) edustaa siltaa ja jokainen viiva (reuna) polkua maassa:

Mikä on ratkaisu tähän ongelmaan?

ei ole yhtä ratkaisu joka täyttää asetetut ehdot, koska, kuten Euler osoitti, kärjet eivät ole parillisen asteisia, eli parillinen määrä viivoja ei vaikuta jokaiseen pisteeseen _[3]. Ei näytä siltä, ​​että voimme tehdä paljoakaan näin yksinkertaisesti määritellyllä rakenteella, kuten usein tapahtuu matematiikka, Joskus asiat eivät ole sitä miltä ne näyttävät. Siten yksi tuotteliaimmista, poikittaisimmista ja monitieteisimmistä aloista _[4] ihmistieto, graafiteoria.

Eulerin graafit vai Euler-rata?

Kaikilla seuraavilla kaavioilla on Eulerin polut _[5]. Onko niillä kaikilla Euler-syklit?

Otetaan kolmas kaavio:

Numeroidaan kärjet:

Näemme sitten, että sekvenssin {3,4,6,2,1,3,7,6,5,4,2} määrittelemä polku on Eulerin polku, koska se kulkee koko graafin läpi ilman toistuvia reunoja, mutta se ei ole Eulerin sykli, koska se ei saavuta aloituspistettä. Mitä olisi tapahtunut, jos olisimme numeroineet kärjet eri tavalla? Ei paljon, paitsi että nyt polun määrittäisi erilainen peräkkäisyys. Mitä olisi tapahtunut, jos olisimme seuranneet eri polkuja kuin alkuperäisessä ratkaisussamme ehdotettiin? Tähän kysymykseen on hieman monimutkaisempi vastata, ja se sisältää algoritmeja, joista ohjelmistosuunnittelijat ovat yleensä iloisia. ohjelmointi.

Tarkemman todisteen saamiseksi siitä, mitä täällä paljastetaan, meidän on viitattava seuraavaan tulokseen:

"Olla G yhdistetty graafi _[6]. Sitten kyllä G on a piiri Euler, kunkin kärjen aste on parillinen, kun taas jos G on Eulerin polku, G: llä on täsmälleen kaksi parittoman asteen kärkeä _[7] (täsmälleen pisteet, joissa polku alkaa ja päättyy)".

Voimme sitten varmistaa, että itse asiassa ottamassamme graafissa vain kärjeillä 3 ja 6 on pariton aste (tämä tapahtuisi vaikka kärkien numerointi olisi ollut erilainen), siksi mainitulla graafilla on polku eulerian _[8]. Muiden kaavioiden kohdalla voimme edetä analogisella tavalla ja tarkistaa, onko niillä todella polkuja ja Eulerin syklit, tai toisin sanoen, voimmeko piirtää tällaisia ​​kaavioita nostamatta kynää ja toistamatta linjat? Vastaus tähän kysymykseen voidaan päätellä siitä, mitä on jo selitetty tähän mennessä, mutta se on harjoittelua Mielenkiintoinen hienomotoristen taitojen, kekseliäisyyden ja kärsivällisyyden kannalta, kehotan lukijaa etsimään ja piirtämään kaavioita, joissa on 6 tai enemmän kärjet kanssa lentorata Eulerian.

Onko olemassa muita kaavioita? Onko graafiteorialla sovelluksia "todellisessa" maailmassa?

Nämä graafit, joita olemme tarkastelleet hyvin lyhyesti, ovat vain yksi monista graafityypeistä, joita löydämme graafiteoriassa. Voimme myös löytää kaavioita, kuten puita, erittäin edustavia joukoissa, joissa niiden elementit voidaan luokitella hierarkioihin ja laskenta- ja laskutoimituksiin. todennäköisyys_[9], digrafit, Hamiltonin graafit _[10], jne.

Kuva graafisista malleista ja verkoista in Psycho., kirjoittanut Ruiz, Ana María.

Näillä arvoituksilla, jos niitä niin halutaan kutsua, on valtava käyttökelpoisuus nykymaailmassa niinkin erilaisissa tilanteissa kuin: biologia molekyylinen _[11], tietojenkäsittelyä_[12], tietoliikenne _[13] ja verkkoanalyysi _[14]. Silloin kannattaa kysyä: Eikö olekin vähintäänkin uteliasta, että ongelma on melkein banaali tulee olemaan yksi matematiikan mielenkiintoisimmista ja näkyvimmistä tuloksista? Ehkä tätä varten tarvittiin yhden ihmiskunnan maineikkaamman mielen panos.