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

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

{(xi, Xs), (Xi, Xs)} и {{хз, x), (x, x)}- В остальной части этой главы, а также в следующей главе мы будем использовать слово разрез для обозначения правильного разреза, если только не оговорено противное.

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

Разрез был определен выше для неориентированного графа. Если граф G = (Х, А) - ориентированный, то разрез графа G определяется как множество дуг, соответствующих ребрам неориентированного дубликата G графа G. Некоторые из дуг разреза графа G будут ориентированы из Хо в Хо, и множество этих дуг будет записываться как (Хо Хо), в то время как множество дуг, ориентированных из вершин множества Хо в вершины множества Хо, будет записываться как (Хд Хо). Поэтому разрез (Хо, Хо), состоящий из дуг ориентированного графа, определяется как объединение (Хо Хо) U (Хо Хо).

Например для графа на рис. 9.5 множество дуг {(х^, х^), (х^, Xs), {xs, Хз), (xi, Xs), (хт, Xt,)} является разрезом, разделяющим множества вершин Хд = {xi, х^, Хз, х, и Zo = {х^, х^, Хт. Xg}.


Рис. 9.5. Ориентированные разрезы.



Этот разрез образован дугами подмножеств (Хо Хо) = {(ж, в),

{Xi, Xs), ( 4. Xs)} и (Хо Хо) = {{Xs, Хз), (х„ Xi)}.

Множество фундаментальных циклов неориентированного графа G было определено в предыдущем разделе как множество V (G) циклов, каждый из которых получается путем добавления какого-нибудь ребра, не принадлежащего остову Т, к ребрам этого остова. Аналогичным образом, имея в виду отмеченную выше двойственность между разрезами и остовами, фундаментальные разрезы относительно остова Т определяются как и - 1 раэревов, каждый из которых содержит одно, и только одно ребро, нринад-iteжaщee дереву Т.

Следующая теорема устанавливает связь между фундаментальными разрезами и фундаментальными циклами и дает способ аостроения фундаментальных разрезов.

Теорема 1. Если Т - остов неориентировантго врафа G, то фундаментлльный разрез, определяемый ребром па Т, образован at и теми ребрами иа G, не принадлежащими Т, квтфрые после добавления к Т дают фундаментальные циклы, содержащие а^

Доказательство. Если из остова Т удалить ребро а|, то Т распадается на два поддерева Ti и (см. рис. 9.6). Любое ребро, дна концевая вершина которого лежит в Г], а другая в Т^, цолжно принадлежать фундаментальному разрезу, так как добавление любого такого ребра к ребрам из Ti и приводит я обра-аованию другого остова графа G и, следовательно, любое множе-.>,тво, не содержащее таких ребер, не будет разрезом. Множество гакиж ребер вместе с ребром Uf является разрезом, так как их

2 -

/----

1 1 1

L

\ /

X /

X X /

X ж 1

X X /

Х ✓ / Х X / 1

// / /

/ 1 / / / 1

h>

V

Рис. 9.6. Фундаментальные циклы, содержащие ребро а^.



ф = Фз

<2

удаление разбивает граф на два подграфа, один из которых имеет множеством своих вершин Т^, а другой - Т^. Значит, этот разрез является фундаментальным разрезом. Более того, так как ребро Ui является единственным ребром, через которое проходят цепи остова Г, начинающиеся в вершинах из Тх и оканчивающиеся в вершинах из Т^, то единственными ребрами, замыкающими фундаментальные циклы, содержащие ребро а^, будут те, одна концевая вершина которых лежит в Тх, а другая в Т^ (таковы, например, ребра Oj, и ад в графе на рис. 9.6). Это доказывает теорему.

4. Матрицы циклов и разрезов

Пусть Т - остов неориентированного графа. Матрицей фундаментальных циклов графа G называется матрица Ф = [фг], состоящая из v (G) строк и т. столбцов, в которой равно 1, если ребро Uj принадлежит циклу Ф^, и равно О в противном случае. Если ребра, не принадлежащие дереву Т, пронумеровать последовательно от 1 до V (G), а ребра дерева Т пронумеровать от V (G) -f 1 до т, то матрица циклов Ф будет иметь вид

Ф = (1Ф12),

где I - единичная матрица. Это объясняется тем, что каждый цикл Ф; содержит одно, и только одно ребро, не принадлежащее остову Т, и циклы всегда можно пронумеровать по числу принадлежащих им внеостовных ребер, вследствие чего все единицы в первой (v (G) X V (С))-подматрице матрицы Ф лежат на диагонали.

Матрица фундаментальных разрезов К = \кц\ определяется аналогично - как матрица era - 1 строками и т столбцами, где kij есть 1, если ребро а/ принадлежит разрезу Ki, и О в противном случае. При той же самой нумерации ребер, что и выше, матрица К имеет зид

к=(Ки!1),

так как теперь каждый фундаментальный разрез содержит одно, и только одно ребро из ребер дерева Т.

В графе на рис. 9.7 возьмем остов, изображенный жирными линиями. Тогда матрица фундаментальных циклов равна



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