Урок за дискретна математика
Именно с проблемите, поставени и решени в този раздел, започна теорията на графовете. Философът Имануел Кант, разхождайки се из град Кьонигсберг (сега този град се нарича Калининград), поставя проблем (1736), известен в математиката като проблем на седем моста на Кьонигсберг: възможно ли е да се преминат през всички тези мостове и едновременно връщане на времето към началната точка, така че всеки мост трябва да бъде преминат само веднъж. Нашият известен петербургски математик от швейцарски произход Леонард Ойлер реши блестящо този проблем. На фиг. 2 показва диаграма на седем моста на Кьонигсберг (имайте предвид, че сега са останали само два от тях), както и мултиграф, съответстващ на тази диаграма (при изграждането на графиката се приема, че всеки речен бряг и остров са върховете на графика, а мостовете са нейните ръбове; можете да видите, че в този случай имаме мултиграф без цикли).
В съответствие с проблема, поставен от Кант (и решен от Ойлер), могат да се дадат следните определения:
Графика (или мултиграф без контури) се нарича Ойлер, ако има цикъл без повтарящи се ръбове (такъв цикъл се нарича Ойлер), който пресича всички върхове на графиката. Графика се нарича полу-Ойлер, ако има маршрут без повтарящи се ръбове (път на Ойлер), който пресича всички ръбове на графиката точно веднъж. На фиг. 3 показва: a - графика на Ойлер, b - полу-ейлерова графика и c - графика, която не е нито eulerian, нито полу-eulerian (хората от по-старото поколение знаят, че в училищата е имало много загадки като "възможно ли е да нарисувате тази фигура, без да вдигате писалката от хартията ", което съответства на графика на Ойлер или полу-Ойлер).
Теорема (Ойлер). За даден свързан граф (не диграф, но евентуално мултиграф без контури) да бъде Ойлер, е необходимо и достатъчно градусите на всички върхове да са четни. Даден свързан граф ще бъде полу-Ойлер, ако и само ако градусите от два върха са нечетни, а градусите на останалите върхове са четни.
Започваме доказателството на тази теорема с така наречената лема за ръкостискане. Името на тази лема се дължи на факта, че тази лема отговаря на следния въпрос: Имате няколко гости. Някои от тях се поздравяват, като се ръкуват. Какви свойства има броят на такива хора? Отговорът се дава от следната доста проста лема.
Лема за ръкостискане. Броят на върховете в графика (или мултиграф без цикли) с нечетна степен е четен.
Доказателство за лемата. Имайте предвид, че сумата от градусите на всички върхове в графика (или мултиграф без контури) трябва да бъде четна. Това следва от факта, че ако вземем върхове, които изобщо не са свързани помежду си, тогава сумата от градусите на тези върхове е равна на нула. Чрез добавяне на всеки ръб, който свързва два върха, увеличаваме сумата на всички градуси с 2 единици. По този начин сумата от всички степени на върховете е четна. Премахвайки градусите на четните върхове от тази сума, получаваме, че сумата от градусите на нечетните върхове трябва да е четна. Това означава, че самият брой на тези върхове трябва да е четен. Лемата е доказана.
От гледна точка на проблема с ръкостискането, това означава, че броят на гостите, които са се ръкували нечетен брой пъти, трябва да е четен. Нека да преминем към доказателството на теоремата на Ойлер.
А) Нека графиката да е Ойлер. Тогава в него има цикъл на Ойлер, който трябва да стигне до върха по единия ръб и да го напусне по другия, тъй като всеки ръб трябва да се използва само веднъж (т.е. всеки „влизащ“ и „напускащ“ върха дава 2 градуса върхове). По този начин сумата от градусите на всички върхове трябва да бъде четна (и е равна на удвоения брой „вписвания“ в този връх при преминаване на цикъла на Ойлер).
Б) Нека в дадена свързана графика (или мултиграф без цикли) степента на всеки връх е четна (т.е. степента е по-голяма или равна на 2, тъй като нулевата степен води до несвързана графика). Нека докажем, че съдържа цикъл на Ойлер. Доказателството е чрез индукция на броя на върховете. В случая, когато в свързана графика има само 2 върха и двата имат четна степен (в случая имаме мултиграф, единият от които е показан на фиг. 4), е ясно, че в този случай има цикъл на Ойлер (за всяка четна степен на тези два върха).