Хамилтонови графики
пъзел от Уилям Хамилтън за околосветско пътешествие, където се изисква да се обиколят 20 върха на размахване на тетраедър и да се върне към началната точка (Фигура 3.26). В негова чест беше кръстен цикълът, съдържащ всички върхове на графиката точно веднъж Хамилтонов цикъл, и графика, съдържаща такъв цикъл, - Хамилтонова графика.
Теорема на Дирак. Всеки брой G с поне три върха (стр³3) и минималната степен на върха д(v) ³стр/ 2 има хамилтонов цикъл.
Математикът Оре доказа по-обща теорема, от която като следствие следва теоремата на Дирак. Но първо, ние отбелязваме, че заедно с концепцията за верига на Ойлер съществува и концепцията за хамилтонова верига. Хамилтън е проста верига, съдържаща всички върхове на графиката точно веднъж.
Теорема на Оре. Ако графиката G за която и да е двойка върхове u, v удовлетворява условието r(u)+r(v) ³стр-1, тогава графиката има хамилтонова верига. Ако r(u)+r(v) ³стр, тогава графиката има хамилтонов цикъл.
Ясно е, че това е доста строго условие, тъй като обхваща само графики с много голям брой ръбове. В пъзела Хамилтън всички върхове са от степен 3, но има хамилтонов цикъл. Можете сами да се уверите.
Сто години след появата на пъзела на Хамилтън математикът Тут, изучавайки свойствата на хамилтоновите графики, получил в момента „най-слабото“ достатъчно условие за съществуването на хамилтонов цикъл. Тоест, описвайки най-широкия клас хамилтонови графики.
Тук трябва да си припомним свойството на планарност, за което някога говорихме. Равнинен наречена графика, която може да се разложи на равнина, без да се пресичат ръбове.
Също така си припомняме какво представлява k-свързана графика. Номер на връзката на връх графиката се определя като минимален брой върхове, премахването на които води до увеличаване на броя на свързаните компоненти.
Теорема на Тут. Всяка 4-свързана равнинна графика има хамилтонов цикъл.
Обърнете внимание, че точно това условие е изпълнено от графиката, предложена от Хамилтън.
Извиква се върхът на графиката, чието премахване води до увеличаване на броя на свързаните компоненти в графиката артикулационна точка.
Следното е вярно теорема, което ще разгледаме тук без доказателство.
Нека бъде - v0 - точка на свързване на свързана графика G. Тогава (и само ако) следните твърдения са верни.
1. Има два такива върха u, vÎG, че всеки път между u и v преминава през върха v0.
2. Има два такива подграфа G1 и G2, че пътят от единия към другия преминава през върха v0.
Сега нека разгледаме графиката на фигура 3.9.
Ако в тази графика премахнем ръба д, тогава графиката също се разделя на два свързани компонента. Извиква се ръб, чието премахване от графиката води до увеличаване на броя на свързаните компоненти мост.
Нека да анализираме резултата от премахването на този ръб и да видим как той се различава от премахването на точката на артикулация.
Първо, премахването на ръба не може да доведе до повече от два нови компонента за свързване. Но в същото време изтриване на който и да е от инцидентните върхове u или v води до премахването на този ръб. Следователно, и двата върха, падащи на моста, са артикулационни точки. Но ако в графиката имаше цикъл, минаващ през ръба д, тогава изтриването му няма да наруши връзката.
Свойствата на моста също могат да бъдат формулирани като теореми.
Нека в свързана графика G ръб, край д е мост. Тогава (и само ако) следните твърдения са верни.
1. Има два такива върха u, vÎG, че всеки път между u и v минава през реброто д.