Турниры

Гамильтонов цикл

Определение. Граф называется гамильтоновым, если в нем имеется цикл, содержащий каждую вершину этого графа.

Уильям Роуэн Гамильтон выпустил головоломку, суть которой состояла в построении пути, который через каждую вершину проходит по одному разу. Задача похожа на задачу о нахождении эйлеровой линии, однако до сих пор не найдены необходимые и достаточные условия существования в графе гамильтоновых линий.

Похожа на данную и задача о коммивояжере, которая тоже состоит в построении цикла, проходящего по всем городам по одному разу, но при этом требуется минимизировать транспортные расходы. Алгоритма решения данной задачи тоже не существует.

Некоторые головоломки типа как перевезти волка, козу и капусту тоже сводятся к поиску гамильтоновой линии на некотором графе, изображающем все возможные перевозки. Известна также задача о нахождении пути коня на шахматной доске, при котором он побывает на каждом поле по одному разу (вариант – и вернется на исходное поле последним ходом), которая тоже является частным случаем задачи о нахождении гамильтоновой линии.

Например, на рисунках 18 и 22 – изображены гамильтоновы графы, а на рисунках 21 и 23 графы, не являющиеся гамильтоновыми.

Определение. Граф называется полугамильтоновым, если существует маршрут, содержащий каждую его вершину ровно один раз.

Определение. Турнир (полный ориентированный граф) – орграф, в котором любые его две вершины соединены ровно одной дугой.

Этот класс графов получил свое название в связи со спортивными турнирами без ничьих, проводимых по круговой системе. Результаты встреч можно описать орграфом, вершины которого соответствуют участникам соревнований, а дуга (v,w) есть в графе, если участник, соответствующий вершине v, выиграл у участника, соответствующего вершине w.

На рисунке 24 изображен не сильносвязный турнир, а на рисунке 25 – сильносвязный.

Теорема. Любой турнир полугамильтонов.

Доказательство (метод математической индукции по количеству вершин). Если турнир имеет меньше четырех вершин, то утверждение, очевидно, верно. Проведем индукцию по числу вершин. Предположим, что любой турнир с n вершинами полугамильтонов. Пусть Т — турнир с n+1 вершинами, и пусть турнир Т’ с n вершинами получен из Т удалением некоторой вершины о вместе со всеми инцидентными ей дугами. Тогда но предположению индукции Т’ обладает полугамильтоновым маршрутом

Рассмотрим три случая.

(1) Если {v, v₁) — дуга в T, то искомой простой орцепью является

(2) Если (v, v₁) не является дугой в Т (это означает, что дугой является (v₁, v)) и если существует такое i, что (v, v_i) -дуга в T, то, выбирая первое i с таким свойством (см. рис. 26), получим, что искомым маршрутом является

Рис. 26

(3) Если в Т не существует дуги вида (v,v_i), то искомым маршрутом является

Теорема. Любой сильно связный турнир гамильтонов.

Доказательство (метод математической индукции по длине цикла). Докажем белее сильный результат,состоящий в том, что сильно связный турнир Т с n вершинами содержит циклы длины 3, 4, … n.

Докажем, что существует цикл длины три. Пусть Т – сильно связный турнир. Тогда для любой вершины v из Т все множество дуг ей инцидентных можно разделить на два не пересекающихся подмножества W – множество дуг для которых вершина v является концом и Z – множество дуг для которых вершина v является началом. Так как Т сильно связен, то оба этих множества не пусты, следовательно найдутся вершины w принадлежащая W и z принадлежащая Z, тогда имеем цикл v, w, z, v длины три.

Предположим, что существуют циклы длины меньшей или равной k – v₁, v₂, …,v_k. Докажем, что существует цикл длины к. Возможны два случая:

1. Существует вершина v, у которой есть инцидентные дуги, направленные к циклу и направленные из цикла. Тогда находим первую дугу, направленную к циклу, пусть это будет дуга (v, vi). Тогда искомый цикл имеет вид: v₁, v₂, …v_i-1, v, v_i,…,v_k.

2. Для любой вершины графа все дуги направлены либо к циклу, либо из цикла. Тогда все множество вершин, не входящих в цикл можно разделить на два непересекающихся подмножества W – множество вершин у которых все дуги направлены к циклу и Z – множество вершин у которых все дуги направлены из цикла. Так как Т сильно связен, то оба этих множества не пусты, следовательно найдутся вершины w’ принадлежащая W и z’ принадлежащая Z, тогда имеем цикл v₁, w',z',v₃, …,v_k. длины k+1 (см. рис. 27).

Рис. 27

Деревья

Определение. Лесом называют граф без циклов.

Определение. Деревом называют произвольный связный граф без циклов.

Таким образом, лесом называетсянесвязныйграф, представляющийобъединениедеревьев. На рисунке 28, представленном ниже, изображен лес с четырьмя компонентами связности, каждая из которых представляет собой дерево.

Рис. 28

Удобно считать, что граф, состоящий из одной изолированной вершины, тоже является деревом.

Определение. Вершина дерева, степень которой равна единице, называется висячей вершиной или листом.

Дата добавления: 2014-12-29