Графи и вериги - Ойлеров цикъл
Граф ще наричаме Ойлеров, ако можем да намерим път, който преминава през всяко ребро по веднъж започвайки от някоя точка. Mожем ли да намерим такъв за дадения граф?
Можем да изберем "Оцветяване верига" от падащото меню и да опитаме:
С няколко опита се вижда, че е невъзможно. Ако граф е Ойлеров, то ако разгънем пътя който го образува ще изглежда по следния начин (като начупена линия):
Някои от точките в оригиналния граф участват по повече от един път, като точките от начупената линия се поставят една върху друга:
Ако поставим две вътрешни точки за веригата една върху друга се получава "четна точка" (от нея излизат четен брой ребра):
Ако поставим някой от двата края на пътя върху вътрешна точка се получава "нечетна точка":
Ако поставим двата края един върху друг се получава "четна точка":
Тогава, ако граф има Ойлеров път, броят на "нечетните" точки не може да бъде повече от 2 (нечетна точка може да се образува само от някой от двата края на пътя). Също така можем да кажем, че броят на нечетните точки е или 0 или 2, тъй като сумата от ребрата, които излизат от всяка от точките трябва да е четно число. Също така е вярно и обратното твърдение - ако граф има 0 или 2 нечетни върха и е свързан (т.е. от всяка точка може да се достигне до всяка друга), то в него има Ойлеров път.
Например следния граф няма Ойлеров път, понеже има 4 нечетни точки:
а следния има:
Нека да разгледаме необходими условия, при които граф може да се разбие на няколко пътя с дадена дължина.
Можете да изследвате в обучителната тема "Сгъната верига - Ойлеров цикъл" в Графи и вериги:
Може ли следния граф да се разбие на няколко пътя с дължина 8?
Можете да опитате сами, като изберете "Оцветяване верига" и "8" от падащото меню, което дава възможност да правите пътища с големина точно 8.
Точка може да бъде нечетна само ако е край на някой от пътищата - т.е. броят на краищата на пътищата трябва да е не по-малък от броя на нечетните точки. Броят на нечетните точки е 12. Броят на ребрата е 2.4.5=40 т.е. имаме 5 пътя с дължина 8, които имат общо 10 края, което е противоречие - не съществуват такива пътища с дължина 8.
Може ли следния граф да се разбие на няколко пътя с дължина 9?
Броят на ребрата е 45 т.е. ни трябват 45 : 9 = 5 пътя. Броят на "нечетните" точки е 10. Това означава, че всеки път, трябва да има два различни края, които са нечетни точки и никои два пътя да нямат общ край. Така намираме пътищата:
Можете да изследвате в обучителната тема "Повече от една верига" в Графи и вериги:
Copyright: Mladen Valkov