ГА́МИЛЬТОНОВ ЦИКЛ

ГА́МИЛЬТОНОВ ЦИКЛ в гра­фе, про­стой цикл, со­дер­жа­щий все вер­ши­ны гра­фа. Про­стым на­зы­ва­ет­ся цикл, в по­сле­до­ватель­но­сти вер­шин ко­то­ро­го все вер­ши­ны встре­ча­ют­ся ров­но один раз (см. Гра­фов тео­рия). Граф, имею­щий Г. ц., на­зы­ва­ет­ся га­миль­то­но­вым. Га­миль­то­нов граф дву­свя­зен. Од­но из дос­та­точ­ных ус­ло­вий су­ще­ст­во­ва­ния Г. ц. со­сто­ит в том, что ес­ли в гра­фе $G$ с $p$ вер­ши­на­ми $p⩾3$, для лю­бо­го $n, 1⩽n⩽(p-1)/2$, чис­ло вер­шин со сте­пе­ня­ми, не пре­вос­хо­дя­щи­ми $n$, мень­ше $n$ и, при не­чёт­ном $p$, чис­ло вер­шин сте­пе­ни ($p-1)/2$ не пре­вос­хо­дит $(p-1)/2$, то граф $G$ име­ет Г. ц. За­да­ча на­хо­ж­де­ния эф­фек­тив­но­го опи­са­ния га­миль­то­но­вых гра­фов ос­та­ёт­ся ак­ту­аль­ной.

Г. ц. по­лу­чи­ли своё на­зва­ние в свя­зи с тем, что пер­вая за­да­ча о та­ких цик­лах бы­ла пред­ло­же­на У. Га­миль­то­ном (1859), это бы­ла за­да­ча-го­ло­во­лом­ка о кру­го­свет­ном пу­те­ше­ст­вии, со­стоя­щая в том, что­бы най­ти замк­ну­тый путь, иду­щий по рёб­рам до­де­ка­эд­ра (изо­бра­жаю­ще­го Зем­лю) и про­хо­дя­щий че­рез ка­ж­дую из его два­дца­ти вер­шин (го­ро­дов) ров­но один раз.

Цикл, со­дер­жа­щий по од­но­му ра­зу все рёб­ра гра­фа, на­зы­ва­ет­ся эй­ле­ро­вым. Пер­вая пуб­ли­ка­ция по тео­рии гра­фов поя­ви­лась (1736) в свя­зи с ре­ше­ни­ем Л. Эй­ле­ром за­да­чи о кё­нигс­берг­ских мос­тах, со­стоя­щей в до­ка­за­тель­ст­ве от­сут­ст­вия та­ко­го цик­ла в гра­фе, опи­сы­ваю­щем рас­по­ло­же­ние этих мос­тов. Граф, имею­щий эй­ле­ров цикл, на­зы­ва­ет­ся эй­ле­ро­вым.

Га­миль­то­но­вы и эй­ле­ро­вы гра­фы и цик­лы на­хо­дят при­ме­не­ние при по­строе­нии и ана­ли­зе ин­фор­ма­ци­он­ных и транс­порт­ных се­тей, а так­же в разл. тео­ре­тич. за­да­чах ком­би­на­тор­но­го ана­ли­за.