Какво е теория на графите и как се дефинира графика като такава?

През 1736 г., въз основа на работата на швейцарския физик-математик Леонхард Ойлер (1707-1783), се наблюдава, че последователност от върхове определя път, обаче, ако споменатият път се състои от различни върхове без повтарящи се ръбове, той се нарича път или път ойлеров; ако освен това стигнем до началната точка, пресичайки всеки ръб само веднъж, тогава имаме Ойлеров цикъл (верига).

Цитат (APA)

Александър Бараза | юли 2022
Диплома по физика

От своя страна ние дефинираме графика като подредена двойка (отива) където v обозначава (непразното) множество от всички върхове или възли на графика, докато А обозначава множеството (може да е празно) от всички ръбове или линии, които свързват върховете на графика. Елементите на комплекта А може да се обозначи като неподредена двойка {v, w}, където v и w са елементи (възли или върхове) на v, по този начин тогава се казва, че v и w са съседни върхове (те са свързани с ребро).

Теорията на графите възниква от отговора, даден от Ойлер на проблем на популярна изобретателност, която се чуди как да пресече седемте моста, които присъедини два острова от общността на Кьонигсберг (част от Германия по това време, а в момента Калининград, в Русия), между тях и с континента, без да използва два пъти един и същ мост и пристигане в началната точка (разположена на континента), каквато и да е тя, определяйки, че в този случай в крайна сметка не бих могъл.

Проблемът със седемте моста на Кьонигсберг

Ойлер моделира Кьонигсберг като графика, където всяка точка (върх или възел) представлява мост, а всяка линия (ръб) път на сушата:

Какво е решението на този проблем?

няма такъв решение който отговаря на наложените условия, тъй като, както показа Ойлер, върховете не са с четна степен, тоест четен брой линии не засяга всяка точка _[3]. Не изглежда, че можем да направим много със структура, дефинирана толкова просто като тази, както често се случва в математика, Понякога нещата не са такива, каквито изглеждат. По този начин, една от най-плодотворните, трансверсални и интердисциплинарни области _[4] на човешкото познание, теория на графите.

Ойлерови графики или с Ойлерова траектория?

Следните графики имат всички ойлерови пътища _[5]. Всички ли имат Ойлерови цикли?

Нека вземем третата графика:

Нека номерираме върховете:

Тогава виждаме, че пътят, определен от последователността {3,4,6,2,1,3,7,6,5,4,2} е ойлеров път, тъй като преминава през цялата графика без повтарящи се ръбове, но не е ойлеров цикъл, тъй като не достига началната точка. Какво би станало, ако номерирахме върховете по различен начин? Не много, освен че сега пътят ще бъде определен от различна последователност. Какво щеше да се случи, ако следвахме пътища, различни от предложените в нашето първоначално решение? Този въпрос е малко по-сложен за отговор и включва алгоритми, от които софтуерните инженери обикновено са възхитени. програмиране.

За по-строго доказателство на това, което е изложено тук, трябва да се позовем на следния резултат:

"Бъда Ж свързана графа _[6]. Тогава да Ж има верига Ойлер, степента на всеки връх е четна, докато if Ж има път на Ойлер, G има точно два върха с нечетна степен _[7] (точно върховете, където пътят започва и свършва)".

След това можем да проверим, че всъщност в графиката, която вземаме, само върховете 3 и 6 имат нечетна степен (това би се случило дори ако номерирането на върховете е било различно), следователно споменатият график има път ойлеров _[8]. За останалите графики можем да продължим по аналогичен начин и да проверим дали наистина имат пътища и Ойлерови цикли, или казано по друг начин, можем ли да начертаем такива графики, без да вземем молива и да повтаряме линии? Отговорът на този въпрос може да бъде извлечен от вече обясненото досега, но това представлява упражнение интересен от гледна точка на фини двигателни умения, изобретателност и търпение, каня читателя да намери и начертае графики от 6 или повече върхове с траектория Ойлеров.

Има ли други видове графики? Има ли приложение теорията на графите в „реалния“ свят?

Тези графики, които разгледахме много накратко, са само един от многото видове графики, които срещаме в теорията на графите. Можем също да намерим графики като дървета, много представителни в набори, където техните елементи могат да бъдат класифицирани в йерархии и при преброяване на изчисления и вероятност_[9], диграфи, хамилтонови графики _[10]и т.н.

Изображение на графични модели и мрежи в Psycho., от Ruiz, Ana María.

Тези енигми, ако искаме да ги наречем така, имат огромна приложимост в днешния свят, в толкова различни ситуации като: биология молекулярно _[11], изчисления_[12], телекомуникации _[13] и мрежов анализ _[14]. Тогава си струва да се запитаме: не е ли поне любопитно, че проблемът на почти банално ще се окаже един от най-интересните и забележителни резултати на математиката? Може би за това беше необходим приносът на един от най-известните умове на човечеството.