Шта је теорија графова и како се граф дефинише као такав?

Године 1736, на основу рада швајцарског физичара-математичара Леонхарда Ојлера (1707-1783), примећено је да низ врхова дефинише путања, међутим, ако се наведена путања састоји од различитих врхова без понављања ивица, назива се путања или путања еулериан; ако додатно дођемо до почетне тачке, прелазећи сваку ивицу само једном, онда имамо Ојлеров циклус (коло).

Цитат (АПА)

алекандер барраза | јул. 2022
Диплома из физике

Са своје стране, дефинишемо граф као уређени пар (ИДЕ) где в означава (непразан) скуп свих врхова или чворова графа, док А означава скуп (може бити празан) свих ивица или линија које спајају врхове графа. Елементи скупа А може се означити као неуређени пар {в, в} где су в и в елементи (чворови или врхови) в, на овај начин се онда каже да су в и в суседни врхови (они су спојени ивицом).

Теорија графова произилази из Ојлеровог одговора на проблем популарне генијалности који се питао како да пређе седам мостова који спојила два острва заједнице Кенигсберг (у то време део Немачке, а тренутно Калињинград, у Русији), између њих и са копном без коришћења два пута исти мост и долазак на почетну тачку (која се налази на копну) шта год да је, утврђујући да у овом случају, на крају, не могао.

Проблем седам Кенигсбершких мостова

Ојлер је моделирао Кенигсберг као график где свака тачка (темен или чвор) представља мост, а свака линија (ивица) пут на копну:

Шта је решење за овај проблем?

нема ни једног решење који испуњава наметнуте услове, пошто, како је показао Ојлер, врхови нису парног степена, односно паран број правих не утиче на сваку тачку _[3]. Међутим, не изгледа да можемо много да урадимо са овако једноставно дефинисаном структуром, као што је то често случај у матх, Понекад ствари нису онакве какве изгледају. Дакле, једно од најплоднијих, трансверзалних и интердисциплинарних области _[4] људског знања, теорија графова.

Ојлерови графови или са Еулеровом путањом?

Сви следећи графови имају Ојлерове путање _[5]. Да ли сви имају Еулерове циклусе?

Узмимо трећи графикон:

Хајде да нумеришемо врхове:

Тада видимо да је путања дефинисана низом {3,4,6,2,1,3,7,6,5,4,2} Ојлерова путања, пошто пролази кроз цео граф без понављања ивица, али није Ојлеров циклус, пошто не стиже до почетне тачке. Шта би се десило да смо врхове нумерисали другачије? Не много, осим што би сада пут био дефинисан другачијим сукцесијом. Шта би се десило да смо ишли другачијим путевима од оног који је предложен у нашем почетном решењу? Одговор на ово питање је мало сложенији и укључује алгоритме којима су софтверски инжењери обично одушевљени. програмирање.

За ригорознији доказ онога што је овде изложено, морамо се позвати на следећи резултат:

"Буди Г повезани граф _[6]. Онда да Г имају струјно коло Ојлер, степен сваког темена је паран, док је ако Г има Ојлерову путању, Г има тачно два темена непарног степена _[7] (тачно врхови где путања почиње и завршава се)".

Тада можемо потврдити да, у ствари, у графу који узимамо, само врхови 3 и 6 имају непаран степен (ово десио би се чак и да је нумерисање темена било другачије), стога наведени граф има путању еулериан _[8]. За преостале графове можемо наставити на аналоган начин и проверити да ли заиста имају путање и Ојлерови циклуси, или другачије речено, можемо ли нацртати такве графиконе без подизања оловке и понављања линије? Одговор на ово питање може се закључити из онога што је до сада већ објашњено, међутим, он представља вежбу занимљиво у смислу фине моторике, домишљатости и стрпљења, позивам читаоца да пронађе и нацрта графиконе од 6 или више темена са путања Еулериан.

Постоје ли друге врсте графикона? Да ли теорија графова има примену у „стварном“ свету?

Ови графови које смо врло кратко прегледали су само један од многих типова графова које налазимо у теорији графова. Такође можемо пронаћи графове као што су стабла, веома репрезентативни у скуповима где се њихови елементи могу класификовати у хијерархије и рачунања и вероватноћа_[9], диграфи, Хамилтонови графови _[10], итд.

Слика графичких модела и мрежа у Психо., Руиз, Ана Марија.

Ове енигме, ако желимо да их тако назовемо, имају огромну применљивост у данашњем свету, у различитим ситуацијама као што су: биологија молекуларни _[11], рад на рачунару_[12], телекомуникације _[13] и анализа мреже _[14]. Вреди се онда запитати: није ли барем чудно да је проблем од скоро баналан да ли ће на крају бити један од најзанимљивијих и најупадљивијих резултата математике? Можда је за то био неопходан допринос једног од најславнијих умова човечанства.