Co je to teorie grafů a jak je graf jako takový definován?

V roce 1736 bylo na základě práce švýcarského fyzika-matematika Leonharda Eulera (1707-1783) pozorováno, že posloupnost vrcholů definuje cesta, pokud se však tato cesta skládá z různých vrcholů bez opakujících se hran, nazývá se cesta nebo cesta eulerovský; pokud navíc dorazíme do výchozího bodu a každou hranu projdeme pouze jednou, pak máme eulerovský cyklus (obvod).

Citace (APA)

alexander barraza | července 2022
Titul z fyziky

Graf definujeme jako uspořádanou dvojici (JDE) kde proti označuje (neprázdnou) množinu všech vrcholů nebo uzlů grafu, while A označuje množinu (může být prázdná) všech hran nebo čar, které spojují vrcholy grafu. Prvky sady A lze označit jako neuspořádanou dvojici {v, w}, kde v a w jsou prvky (uzly nebo vrcholy) proti, tímto způsobem se pak říká, že v a w jsou sousední vrcholy (jsou spojeny hranou).

Teorie grafů vychází z odpovědi dané Eulerem na problém lidové vynalézavosti, která přemýšlela, jak překonat sedm mostů, které spojil dva ostrovy komunity Königsberg (tehdejší část Německa a v současnosti Kaliningrad v Rusku), mezi nimi as pevninou bez použití dvou krát stejný most a přijíždějící do výchozího bodu (nacházejícího se na pevnině), ať už je jakýkoli, což určuje, že v tomto případě nakonec ne mohl.

Problém sedmi mostů v Königsbergu

Euler modeloval Königsberg jako graf, kde každý bod (vrchol nebo uzel) představuje most a každá čára (hrana) cestu na zemi:

Jaké je řešení tohoto problému?

žádný není řešení který splňuje stanovené podmínky, protože, jak ukázal Euler, vrcholy nejsou sudého stupně, to znamená, že sudý počet čar neovlivňuje každý bod _[3]. Nezdá se, že bychom mohli udělat mnoho s takto jednoduše definovanou strukturou, jak je tomu často v matematika, Někdy věci nejsou takové, jak se zdají. Jedná se tedy o jednu z nejplodnějších, průřezových a interdisciplinárních oblastí _[4] lidského poznání, teorie grafů.

Eulerovské grafy nebo s eulerovskou trajektorií?

Všechny následující grafy mají eulerovské dráhy _[5]. Mají všichni eulerovské cykly?

Vezměme si třetí graf:

Očíslujme vrcholy:

Vidíme tedy, že cesta definovaná sekvencí {3,4,6,2,1,3,7,6,5,4,2} je eulerovská cesta, protože prochází celým grafem bez opakujících se hran, ale není to eulerovský cyklus, protože nedosahuje výchozího bodu. Co by se stalo, kdybychom očíslovali vrcholy jinak? Nic moc, až na to, že nyní by byla cesta definována jinou posloupností. Co by se stalo, kdybychom šli jinou cestou, než jaká byla navržena v našem původním řešení? Odpověď na tuto otázku je o něco složitější a zahrnuje algoritmy, se kterými jsou softwaroví inženýři obvykle spokojeni. programování.

Pro přesnější důkaz toho, co je zde vystaveno, musíme odkázat na následující výsledek:

"Být G spojený graf _[6]. Pak ano G mít obvod Euler, stupeň každého vrcholu je sudý, zatímco if G má Eulerovu cestu, G má právě dva vrcholy lichého stupně _[7] (přesně ty vrcholy, kde cesta začíná a končí)".

Můžeme si pak ověřit, že ve skutečnosti v námi pořízeném grafu mají pouze vrcholy 3 a 6 lichý stupeň (toto by nastal, i kdyby číslování vrcholů bylo jiné), proto má uvedený graf cestu eulerovský _[8]. U zbývajících grafů můžeme postupovat analogicky a ověřit, zda skutečně mají cesty a Eulerovské cykly, nebo jinak řečeno, můžeme kreslit takové grafy, aniž bychom zvedli tužku a opakovali linky? Odpověď na tuto otázku lze odvodit z toho, co již bylo vysvětleno, jde však o cvičení zajímavé z hlediska jemné motoriky, vynalézavosti a trpělivosti, vyzývám čtenáře, aby našel a nakreslil grafy 6 a více vrcholy s trajektorie eulerovský.

Existují i ​​jiné typy grafů? Má teorie grafů aplikace v „reálném“ světě?

Tyto grafy, které jsme probrali velmi stručně, jsou jen jedním z mnoha typů grafů, které najdeme v teorii grafů. Můžeme také najít grafy, jako jsou stromy, velmi reprezentativní v množinách, kde lze jejich prvky klasifikovat v hierarchiích a v počítacích výpočtech a pravděpodobnost_[9], digrafy, hamiltonovské grafy _[10], atd.

Obrázek grafických modelů a sítí v psycho., Ruiz, Ana María.

Tyto záhady, pokud je tak chceme nazvat, mají v dnešním světě obrovskou použitelnost v situacích tak různorodých, jako jsou: biologie molekulární _[11], výpočetní_[12], telekomunikace _[13] a síťová analýza _[14]. Stojí za to se ptát: Není to přinejmenším zvláštní, že jde o téměř problém banální bude nakonec jedním z nejzajímavějších a nejnápadnějších výsledků matematiky? Možná k tomu byl nezbytný příspěvek jedné z nejproslulejších myslí lidstva.