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

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

(iii) для каждой помеченной вершины все вершины из множества Г (xi) уже помечены, но существуют другие, еще не помеченные вершины.

В случае (i) все вершины, помеченные знаком + , отнесем к множеству Х', а помеченные знаком - - к множеству Х'. Поскольку все ребра соединяют вершины, помеченные противоположными знаками, то граф является двудольным.

В случае (ii) вершина ж,- должна быть помечена знаком + на некотором маршруте (например, p,j), состоящем из вершин Xi, Xi, . . ., Xi; причем знаки + и - , приписываемые этим вершинам при движении по маршруту р. (от вершины к вершине Ж(), должны образовывать чередующуюся последовательност! (вида +, -,+,... или -, +, -, ) Аналогично знаком - вершина Xt помечается вдоль некоторого маршрута ц^. Пусть X* - предпоследняя (последней является Xi) общая вершина маршрутов р, и fig. Если вершина х* помечена знаком + , то участок от X* до Xi маршрута р^ должен быть четным, а участок от X* до Xi маршрута р2 должен быть нечетным. Если же вершина X* помечена знаком - , то участок маршрута р^ будет нечетным, а маршрута ра - четным. Следовательно, цикл, состоящий из участка маршрута р^, от х* до Xi, и соответствующего участка маршрута от до ж*, имеет нечетную длину. Это противоречит предположению, что граф G не содержит циклов нечетной длины, и, значит, случай (ii) невозможен.

Случай (iii) означает, что между помеченной и не помеченной вершинами не существует ребра, т. е. что граф G распадается на две или больше частей, и каждая из них может тогда рассматриваться отдельно. Итак, в конце концов приходим к случаю (i) Теорема доказана.

Если нужно подчеркнуть, что граф является двудольным, то для графа применяют обозначение (Z [j Х', А), подразумевая, что выполняются также соотношения (1.13).

Двудольный граф G = (X [J А) называют полным, если для любых двух вершин Xt 6 X и xj Х' существует ребро (Xi, Xj) в G = {X, А). Если 1 X 1 - число вершин множества Z - равно г и I Z * I = S, то полный неориентированный двудольный граф G - (Х и А) обозначается через Kr,s-

Граф G = {X, А) называется планарным, если он может быть нарисован на плоскости (или сфере) таким образом, что произвольные две дуги графа не пересекаются друг с другом ). На рис. 1.6(a)

1) То есть если точка плоскости (или сферы) принадлежит нескольким дугам графа (двум или большему числу), то она не является внутренней точкой никакой дуги графа.- Прим. ред.




W (6)

Рис. 1.6. Непланарные графы Куратовского. (а) К^,. (б) 3,3.

Эти два графа играют важную роль в теории планарных графов и известны как графы Куратовского.

7. Сильно связные графы и компоненты графа

Ориентированный граф называется сильно связным или сильным, если для любых двух различных вершин а;,- и xj суп1;ествует по крайней мере один путь, соединяющий Xf cxj. Это определение означает также, что любые две вершины такого графа взаимно достижимы.

Ориентированный граф называется односторонне связным или односторонним, если для любых двух различных вершин а;,- и Xj существует по крайней мере один путь из а;,- в xj или из xj в (или оба одновременно).

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

Если для некоторой пары вершин орграфа не существует маршрута, соединяющего их, то такой орграф называется кесеязныль [2].

Граф, приведенный на рис. 1.7(a), как легко проверить, сильно связный. Граф, показанный на рис. 1.7(6), не является сильным (так как в нем нет пути из х^ в Xj), но односторонне связный. Граф, изображенный на рис. 1.7(b), не является ни сильным, ни односторонним, поскольку в нем не существует путей от х^ к Xg и от Х5 к Xg. Он - слабо связный. Наконец, граф, приведенный на рис. 1.7(г), является несвязным.

Пусть дано некоторое свойство Р, которым могут обладать графы. Максимальным подграфом графа G относительно свойства

показан полный граф К5, а на рис. 1.6(6) - полный двудольный граф К33, которые, как известно, являются непланарньши [1, 3].



Р называется порожденный подграф (Xg) графа G, обладающий этим свойством и такой, что не существует другого порожденного подграфа (Xg), у которого Xg 13 Xg и который также обладает свойством Р. Так, например, если в качестве свойства Р взята


Рис. 1.7. (а) Сильно связный граф. (б) Односторонне связный граф. (в) Слабо связный граф. (г) Несвязный граф.

сильная связность, то максимальным сильным подграфом графа G является сильный подграф, который не содержится в любом другом сильном подграфе. Такой подграф называется сильной компонентой графа G. Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента - максимальный слабый подграф.

Например, в графе G, приведенном на рис. 1.7(6), подграф {{xi, х^, Xi, Хе}) является сильной компонентой графа G. С другой стороны, подграфы {{xi, х^}) и {{xi, Xs, х^}) не являются сильными компонентами (хотя и являются сильными подграфами), поскольку они содержатся в графе {{х^, х^, х^, х^) и, следовательно, не максимальные. В графе, показанном на рис. 1.7(b), подграф {{Xi, х^, Xg}) является односторонней компонентой. В графе, приведенном ria рис. 1.7(г), оба подграфа {{хх, х^, хв}> и ({ха, хз, 3:4}> являются слабыми компонентами, и у этого графа только две такие компоненты.



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