Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 [ 4 ] 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

в х, Т. е.

Таким образом, когда слова длина , стоимость , цена и вес применяются к дугам, то они эквивалентны по содержанию, и в каждом конкретном случае выбирается такое слово, которое

Рис. 1.3.

ближе подходит по смыслу и совпадает с принятым в литературе ).

Длиной (или мощностью) пути р. называется число дуг, входящих в него 2).

3. Петли, ориентированные циклы и циклы

Петлей называется дуга, начальная и конечная вершины которой совпадают. На рис. 1.3, например, дуги и являются петлями.

Путь 1, , называется замкнутым, если в нем начальная вершина дуги совпадает с конечной вершиной дуги а,.

1) В данном переводе мы применяем термин длина только в том случае, когда все дуги, входящие в путь ц, имеют веса, равные 1, т. е. когда вес пути совпадает с его длиной {мощностью).- Прим. ред.

2) Каждая дуга считается столько раз, сколько она входит в данный путь.- Прим. ред.



Яю, 1,3, 04. fli-flia (1.11)

являются замкнутыми маршрутами.

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

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

2 Н. Кристофидес

Так, например, в графе, приведенном на рис. 1.3, последовательности дуг

аз,ав,ац, (1.7)

aii,aз,a,a,a,a2 a2, (1.8)

03,04,07,010,09111 (1-9)

являются замкнутыми путями.

Пути (1.7) и (1.9) являются замкнутыми простыми орцепями {контурами, или простыми орциклами), поскольку в них одна и та же вершина используется только один раз (за исключением начальной и конечной вершин, которые совпадают), а путь (1.8) не является контуром, так как вершина Xi используется в нем дважды ). Контур, проходящий через все вершины графа, имеет особое значение и называется гамилътоновым контуром ). Конечно, не все графы обладают гамильтоновыми контурами. Так, например, контур (1.9) является гамильтоновым контуром графа, приведенного на рис. 1.3, а граф на рис. 1.2 не имеет гамильтоно-вых контуров, поскольку не существует такой дуги, для которой

была бы конечной вершиной.

Замкнутый маршрут является неориентированным двойником замкнутого пути. Таким образом, замкнутый маршрут является маршрутом х^, . , Хц, в котором совпадают начальная и конечная вершины, т. е. в котором = Xq.

На рис. 1.3 маршруты

ai,ai2.aio (1.10)



4. Степени вершины

Число дуг, которые имеют вершину своей начальной вершиной, называется полустепенъю исхода вершины Xj, и, аналогично, число дуг, которые имеют Xi своей конечной вершиной, называется полустепенъю захода вершины Xf.

Таким образом, на рис. 1.3 полустепень исхода вершины Хд, обозначаемая через (xg), равна Г (х^) = 2, и полустепень захода вершины х^, обозначаемая через dt (xg), равна (же) = = 1.

Совершенно очевидно, что сумма полустепеней захода всех вершин графа, а также сумма нолустененей исхода всех вершин равны общему числу дуг графа G, т. е.

п п

do{xt)=dt{Xi) = m, (1.12)

t=l i=l

где п - число вершин и пг - число дуг графа G.

Для неориентированного графа G = {X, Г) степенъ вершины Xi определяется аналогично - с помощью соотношения d (xi) = = 1 Г (xi) I, и когда не может возникнуть недоразумений, мы будем обозначать степень вершины xt через dj.

5. Подграфы

Пусть дан граф G = {X, А). Остовным подграфом ) Gp графа G называется граф {X, Ар), для которого Ар а А. Таким образом, остовный подграф имеет то же самое множество вершин, что и граф G, но множество дуг подграфа Gp является подмножеством множества дуг исходного графа.

Граф на рис. 1.4(6) - остовный подграф Gp графа G, изображенного на рис. 1.4(a).

Пусть дан граф G = {X, Г). Порожденным подграфом *) G, называется граф (Xg, Т,), для которого Xg а X ж для каждой вершины Xi 6 Xg, Tg (xi) = Г {xi) f) Xg. Таким образом, порожденный подграф состоит из подмножества вершин Xg множества вершин исходного графа и всех таких дуг графа G, у которых конечные и начальные вершины принадлежат подмножеству Xg. Часто бывает удобно обозначать подграф Gg просто символом (Xg); мы будем в дальнейшем использовать такое обозначение, если нет опасности внесения путаницы.

На рис. 1.4(b) показан порожденный подграф графа, приведенного на рис. 1.4(a), содержащий только вершины Xi, х^, Хд и х^ и дуги, которые их связывают.

) Автор применяет термин частичный граф*.- Прим. ред. 2) Автор использует термин подграф .- Прим. ред.



1 2 3 [ 4 ] 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95