Mi az a gráfelmélet, és hogyan definiálható a gráf?

1736-ban Leonhard Euler (1707-1783) svájci fizikus-matematikus munkája alapján megfigyelték, hogy a csúcsok egymásutánja határozza meg út, azonban ha az említett útvonal különböző csúcsokból áll, ismétlődő élek nélkül, akkor azt útvonalnak vagy útvonalnak nevezzük eulerianus; ha ezen felül a kiindulási ponthoz érünk, minden élt csak egyszer járunk át, akkor Euler-ciklusunk (áramkörünk) van.

Idézet (APA)

Sándor barraza | július 2022
Fizikus végzettség

A gráfot a maga részéről rendezett párként definiáljuk (MEGY) ahol v a gráf összes csúcsának vagy csomópontjának (nem üres) halmazát jelöli, míg A jelöli a gráf csúcsait összekötő összes él vagy vonal halmazát (lehet üres is). A készlet elemei A egy rendezetlen {v, w} párként jelölhető, ahol v és w elemei (csomópontjai vagy csúcsai) v, ilyen módon azt mondják, hogy v és w szomszédos csúcsok (egy él köti össze őket).

A gráfelmélet abból a válaszból ered, amelyet Euler adott egy népi találékonyság problémájára, amely azon töprengett, hogyan lehet átkelni a hét hídon, Königsberg közösség két szigetéhez csatlakozott (akkor Németországhoz tartozott, jelenleg pedig Kalinyingrádhoz Oroszországban), köztük és a szárazfölddel anélkül, hogy két szigetet használt volna. ugyanannak a hídnak a megérkezése és a kiindulási pont megérkezése (a szárazföldön található), bármi legyen is az, ami meghatározza, hogy ebben az esetben végső soron nem tudott.

Königsberg hét hídjának problémája

Euler Königsberget egy gráfként modellezte, ahol minden pont (csúcs vagy csomópont) egy hidat, és minden vonal (él) egy utat jelent a szárazföldön:

Mi a megoldás erre a problémára?

nincs egy sem megoldás ami teljesíti a felállított feltételeket, hiszen ahogy Euler megmutatta, a csúcsok nem páros fokúak, vagyis a páros számú egyenes nem befolyásolja az egyes pontokat _[3]. Úgy tűnik azonban, hogy egy ilyen egyszerűen definiált struktúrával nem sokat tehetünk, ahogy az gyakran előfordul matematika, Néha a dolgok nem azok, aminek látszanak. Így az egyik legtermékenyebb, transzverzális és interdiszciplináris terület _[4] az emberi tudás, gráfelmélet.

Euler-gráfok vagy Euler-pálya?

A következő gráfok mindegyike rendelkezik Euler-útvonallal _[5]. Mindegyiknek van Euler-ciklusa?

Vegyük a harmadik grafikont:

Számozzuk meg a csúcsokat:

Látjuk tehát, hogy a {3,4,6,2,1,3,7,6,5,4,2} sorozat által meghatározott út egy Euler-féle út, mivel ismétlődő élek nélkül végigmegy a teljes gráfon, de nem Euler-ciklus, mivel nem éri el a kezdőpontot. Mi lett volna, ha másként számozzuk a csúcsokat? Nem sok, kivéve, hogy az utat most egy másik egymásutániság határozná meg. Mi történt volna, ha az eredeti megoldásunkban javasolttól eltérő utakat követünk? Erre a kérdésre egy kicsit bonyolultabb a válasz, és olyan algoritmusokat tartalmaz, amelyeknek a szoftvermérnökök általában elégedettek. programozás.

Az itt leírtak pontosabb bizonyításához a következő eredményre kell hivatkoznunk:

"Lenni G összefüggő gráf _[6]. Akkor igen G Van egy áramkör Euler, minden csúcs foka páros, míg ha G Euler-útvonala van, G-nek pontosan két páratlan fokú csúcsa van _[7] (pontosan azok a csúcsok, ahol az út kezdődik és végződik)".

Ezután ellenőrizhetjük, hogy az általunk felvett gráfban csak a 3. és 6. csúcsnak van páratlan foka (ez akkor is előfordulna, ha a csúcsok számozása eltérő lett volna), ezért az említett gráfnak van útvonala euleriánus _[8]. A többi gráf esetében hasonló módon járhatunk el, és ellenőrizhetjük, hogy valóban vannak-e utak és Euler-ciklusok, vagy másképpen fogalmazva, rajzolhatunk-e ilyen grafikonokat anélkül, hogy felvennénk a ceruzát és megismételnénk vonalak? A válasz erre a kérdésre az eddig kifejtettek alapján levezethető, azonban gyakorlatnak minősül A finommotorikus készségek, a találékonyság és a türelem szempontjából érdekes, arra kérem az olvasót, hogy találjon és rajzoljon 6 vagy több grafikont csúcsok -val röppálya Eulerianus.

Vannak más típusú grafikonok? Van-e alkalmazása a gráfelméletnek a „valós” világban?

Ezek a grafikonok, amelyeket nagyon röviden áttekintettünk, csak egy a gráfelméletben megtalálható sokféle gráf közül. Találhatunk olyan gráfokat is, mint például a fák, amelyek nagyon reprezentatívak azokban a halmazokban, ahol az elemeik hierarchiákba sorolhatók, és a számolási számítások során valószínűség_[9], digráfok, Hamilton-gráfok _[10]stb.

Grafikus modellek és hálózatok képe a Psycho.-ban, Ruiz, Ana María.

Ezek a rejtélyek, ha így akarjuk nevezni őket, rendkívül alkalmazhatóak a mai világban, olyan sokféle helyzetekben, mint: biológia molekuláris _[11], számítástechnika_[12], távközlés _[13] és hálózatelemzés _[14]. Érdemes ilyenkor megkérdezni: Ugye legalább érdekes, hogy egy majdnem probléma banális végül a matematika egyik legérdekesebb és legszembetűnőbb eredménye lesz? Talán ehhez az emberiség egyik legkiválóbb elméjének közreműködésére volt szükség.