Čo je teória grafov a ako sa definuje graf ako taký?

V roku 1736 sa na základe práce švajčiarskeho fyzika-matematika Leonharda Eulera (1707-1783) zistilo, že postupnosť vrcholov definuje cesta, ak však uvedená cesta pozostáva z rôznych vrcholov bez opakujúcich sa hrán, nazýva sa to cesta alebo cesta eulerovský; ak sa dodatočne dostaneme do začiatočného bodu, pričom každú hranu prejdeme iba raz, potom máme eulerovský cyklus (okruh).

Cenová ponuka (APA)

alexander barraza | júl 2022
Titul z fyziky

Graf definujeme ako usporiadanú dvojicu (IDE) kde v označuje (neprázdnu) množinu všetkých vrcholov alebo uzlov grafu, pričom A označuje množinu (môže byť prázdna) všetkých hrán alebo čiar, ktoré spájajú vrcholy grafu. Prvky súpravy A možno označiť ako neusporiadaný pár {v, w}, kde v a w sú prvky (uzly alebo vrcholy) v, takto sa potom hovorí, že v a w sú susedné vrcholy (sú spojené hranou).

Teória grafov vychádza z odpovede, ktorú dal Euler na problém ľudovej vynaliezavosti, ktorá sa pýtala, ako prejsť cez sedem mostov, ktoré spojil dva ostrovy komunity Königsberg (v tom čase časť Nemecka a v súčasnosti Kaliningrad v Rusku), medzi nimi as pevninou bez použitia dvoch krát ten istý most a dorazí do východiskového bodu (nachádza sa na pevnine), nech už je akýkoľvek, čo určuje, že v tomto prípade v konečnom dôsledku nie mohol.

Problém siedmich mostov Königsbergu

Euler modeloval Königsberg ako graf, kde každý bod (vrchol alebo uzol) predstavuje most a každá čiara (hrana) cestu na zemi:

Aké je riešenie tohto problému?

nie je ani jeden Riešenie ktorý spĺňa stanovené podmienky, pretože, ako ukázal Euler, vrcholy nie sú párneho stupňa, to znamená, že párny počet čiar neovplyvňuje každý bod _[3]. Zdá sa však, že s takto jednoducho definovanou štruktúrou nemôžeme veľa urobiť, ako je to často v matematika, Niekedy veci nie sú také, ako sa zdajú. Ide teda o jednu z najplodnejších, prierezových a interdisciplinárnych oblastí _[4] ľudského poznania, teória grafov.

Eulerovské grafy alebo s eulerovskou trajektóriou?

Všetky nasledujúce grafy majú eulerovské dráhy _[5]. Majú všetky eulerovské cykly?

Zoberme si tretí graf:

Očíslujme vrcholy:

Vidíme teda, že cesta definovaná sekvenciou {3,4,6,2,1,3,7,6,5,4,2} je eulerovská cesta, pretože prechádza celým grafom bez opakujúcich sa hrán, ale nie je to eulerovský cyklus, pretože nedosahuje počiatočný bod. Čo by sa stalo, keby sme vrcholy očíslovali inak? Nie veľa, až na to, že teraz by bola cesta definovaná inou postupnosťou. Čo by sa stalo, keby sme išli inými cestami, ako je tá, ktorá bola navrhnutá v našom pôvodnom riešení? Odpoveď na túto otázku je o niečo zložitejšia a zahŕňa algoritmy, s ktorými sú softvéroví inžinieri zvyčajne spokojní. programovanie.

Pre dôkladnejší dôkaz toho, čo je tu odhalené, musíme odkázať na nasledujúci výsledok:

"Buď G spojený graf _[6]. Potom áno G mať obvod Euler, stupeň každého vrcholu je párny, kým ak G má Eulerovu cestu, G má práve dva vrcholy nepárneho stupňa _[7] (presne vrcholy, kde cesta začína a končí)".

Potom môžeme overiť, že v skutočnosti v grafe, ktorý urobíme, majú iba vrcholy 3 a 6 nepárny stupeň (toto by nastala, aj keby číslovanie vrcholov bolo iné), preto uvedený graf má cestu eulerovský _[8]. Pre zvyšné grafy môžeme postupovať analogicky a overiť, či skutočne majú cesty a Eulerovské cykly, alebo inak povedané, môžeme kresliť takéto grafy bez toho, aby sme zobrali ceruzku a opakovali linky? Odpoveď na túto otázku možno vyvodiť z toho, čo už bolo vysvetlené, ide však o cvičenie zaujímavé z hľadiska jemnej motoriky, vynaliezavosti a trpezlivosti, vyzývam čitateľa, aby našiel a nakreslil grafy 6 a viac vrcholy s trajektórie eulerovský.

Existujú aj iné typy grafov? Má teória grafov uplatnenie v „reálnom“ svete?

Tieto grafy, ktoré sme veľmi stručne zhodnotili, sú len jedným z mnohých typov grafov, ktoré nájdeme v teórii grafov. Môžeme tiež nájsť grafy, ako sú stromy, veľmi reprezentatívne v množinách, kde ich prvky možno klasifikovať v hierarchiách a pri počítacích výpočtoch a pravdepodobnosť_[9], digrafy, hamiltonovské grafy _[10], atď.

Obrázok grafických modelov a sietí v psycho., Ruiz, Ana María.

Tieto záhady, ak ich tak chceme nazvať, majú obrovskú použiteľnosť v dnešnom svete, v tak rôznorodých situáciách, ako sú: biológia molekulárne _[11], výpočtový_[12], telekomunikácie _[13] a sieťovú analýzu _[14]. Potom sa oplatí položiť otázku: Nie je to prinajmenšom zvláštne, že ide o problém takmer banálne bude nakoniec jedným z najzaujímavejších a najnápadnejších výsledkov matematiky? Možno na to bol potrebný príspevok jednej z najslávnejších myslí ľudstva.