Маршруты, цепи, циклы

Маршрутом в графе G = (X, U) называется некоторая конечная последовательность ребер вида S = (x ₀, x ₁), (x ₁, x ₂), …, (x_{l -1}, x_l), где x ₀, x_l ─ ─соответственно его начальная и конечная вершины. Очевидно, что в конечном графе G можно выделить только конечное число маршрутов. Число ребер в маршруте S называется его длиной. Существует простой способ определения маршрутов длиной q по матрице R графа G путем возведения ее в q -ю степень.

Например, пусть задана матрица R графа G (рис. 15.23):

					.
R = 2

Рис. 15.23. Пример графа G

Возведем ее в квадрат по правилу:

r ² _i,j = r_1,i * r_{j ,1} + r _{2, i} * r_{j ,2} +... + r_n,i * r_j,n. (1.4)

Тогда для рассматриваемого в данном примере графа, к примеру, элемент r ²₁₁ матрицы R² будет иметь следующее значение:

r ² _{1, 1} = a ₁₁ b ₁₁ + a ₁₂ b ₂₁ + a ₁₃ b ₃₁ + a ₁₄ b ₄₁ = 0 + 1*1 + 1*1 + 0 = 2.

А, например, r ²_3,3 = r _1,3 r _3,1 + r _2,3 r _3,2 + r _3,3 r _3,3 + r _4,3 r _3,4 = 1*1 + 0*0 + 0*0 + 1*1 = 2.

					.
R^2 = 2

Каждый r_i,j элемент R² равен числу маршрутов длиной 2, ведущих из вершины x_i в x_j. Например, r _3,2 = 2 означает, что в графе два маршрута ведущих из x ₃ в x ₂ длиной 2: S₁ = (x ₃, x ₁), (x ₁, x ₂); S₂ = (x ₃, x ₄), (x ₄, x ₂).

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

Маршрут, в котором нет повторяющихся ребер, называется цепью. Замкнутая цепь, в которой x ₀ = x_l, называется циклом. Соответственно цепи и циклы называются простыми, если они не содержат повторяющихся вершин, кроме, разумеется, первой и последней в случае цикла. В графе G (см. рис. 15.14, a):

S₁ = (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₆), (x ₆, x ₂), (x ₂, x ₄) ─ маршрут,

S₂ = (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₆), (x ₆, x ₂) ─ цепь,

S₃ = (x ₆, x ₂), (x ₂, x ₄), (x ₄, x ₁), (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₆) ─ цикл,

S₄ = (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₇), (x ₇, x ₆) ─ простая цепь,

S₅ = (x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₇), (x ₇, x ₆), (x ₆, x ₅), (x ₅, x ₄), (x ₄, x ₁) ─ простой цикл.

Цикл длиной 3 называется треугольником.

Связный регулярный граф степени 2 называется циклическим графом или циклом. Циклический граф с n вершинами обозначается C_n (рис. 15.24, а).

а б

Рис. 15.24 Циклический граф (а), граф-колесо (б)

Соединение графов К₁ и С_n-1 (n ³ 3) называется колесом с n вершинами и обозначается W_n. На рис. 15.24, б показано колесо W₆.

Две произвольные вершины x_i, x_j Î X графа называются связными, если существует маршрут S, в котором концевыми будут вершины x_i, x_j. Граф G называется связным, если любые две его вершины связаны. В противном случае G не связен, а каждый из составляющих его подграфов G₁, G₂, …, G _l называется компонентой связности. Из определения связности следует, что в связном графе G вершина x_i связана сама с собой; если x_i связана c x_j, то x_j связана c x_i; если x_i связана c x_j, а x_j связана c x_k, то и x_i связана c x_k (x_i, x_j, x_k Î X).

Следовательно, отношение связности является отношением эквивалентности. В этом случае множество вершин Х графа G = (X, U), который моделирует любой объект, можно разбить на непересекающиеся классы G _i, причем ребра графа будут соединять только вершины внутри этих классов. Таким образом, получим разбиение графа G на связные подграфы (компоненты связности). Например, графы, изображенные на рис. 15.14, связные, а граф на рис. 15.25 состоит из четырех компонентов связности G₁ ─ G₄, т.е. не связен. Заметим, что связный граф состоит из единственной компоненты связности. Если граф имеет несколько компонент связности, то он не связен, так как вершины из разных компонент связности нельзя соединить маршрутом.

Рис. 15.25. Пример несвязного графа

Очевидно, что число ребер в связном графе

n – 1 £ m £ n (n – 1)/2. (1.5)

Теорема 15.1. Пусть G – простой граф (см. стр. 10) с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

n – k £ m £ (n - k)(n - k + 1)/2. (1.6)

Следствие 15.1. Любой простой граф с n вершинами и более чем (n – 1)(n – 2)/2 ребрами связен.

При конструировании систем часто надо знать, какое наименьшее число связей необходимо удалить из схемы, чтобы она перестала быть связной. Если вершины связного графа G = (X, U) разбить на 2 подмножества X’ и X’’, где X’’, X’ Ì X, X’’ = X \ X’, X’ È X’’ = X, то подмножество ребер U’ Ì U, у которых одни концевые вершины принадлежат X’, а другие X’’, называют разрезом графа G. Подграф G’ = (X, U\U’), полученный из G удалением ребер разреза, будет несвязанным графом, состоящим, по крайней мере, из двух компонент связности. Множество ребер U’’ Ì U, удаление которых дает несвязный подграф G’ = (X, U \ U’’) и не существует подмножества U’ÌU’’, такого, что G’’ = (X, U \ U’), несвязен, называют правильным разрезом. Из определения следует, что правильный разрез разбивает G точно на две компоненты связности. В этом случае разрез будет определяться как объединение правильных разрезов. На рис. 15.26,а показан пример разреза в графе G = (X, U). Разрез показан пунктирной линией.

а б

Рис. 15.26. Пример разреза в графе (а) и наличия точки сочленения (б)

Правильными разрезами будут следующие подмножества ребер: U₁ = {(x ₃, x ₆), (x ₄, x ₆), (x ₄, x ₇)}, U₂ = {(x ₄, x ₁₀), (x ₅, x ₁₀)}, U₃ = {(x ₅, x ₁₂)}, U₄ = {(x ₅, x ₁₅)}, а разрез U = U₁ È U₂ È U₃ È U₄. Заметим, что разрез в графе всегда существует. Тривиальными разрезами G являются U’ = U и U’ = Æ. Если разрез состоит из одного ребра u_i Î U, то u_i называется перешейком или мостом.

Точкой сочленения называется вершина графа, после удаления которой граф распадается на связные компоненты. Например, в графе G на рис. 15.26, б вершина 3 является точкой сочленения.

Неразделимый граф ─ это связный, непустой, не имеющий точек сочленения граф. Блок графа ─ это его максимальный неразделимый подграф. Если G ─ неразделимый граф, то он часто сам называется блоком. Так, на рис. 15.27 приведен пример графа G, имеющего две точки сочленения x ₅ и x _6, удаление которых разбивает граф G на 4 блока (рис. 15.28).

Граф блоков B(G) ─ это граф, в котором вершины ─ блоки и две вершины смежны, если соответствующие блоки имеют общую точку сочленения.

Вершинная связность H = H(G) в G – это наименьшее число вершин, удаление которых приводит к несвязному графу. H(G) в несвязном графе равна нулю. Связность в графе с точкой сочленения равна 1.

Рис. 15.27. Граф G Рис. 15.28. Блоки графа G

Реберная связность l = l(G) – это наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.

Для любого графа:

H(G) £ l(G) £ r_min (G), (15.7)

где r_min (G) ─ наименьшая степень графа.

Граф G называется n-связным, если H(G) ³ n и n-реберносвязным, если l(G) ³ n.

Теорема 15.2 (Дирак). Если граф G n-связен, n ³ 2, то любое множество, содержащее n вершин графа G, принадлежит простому циклу.

Теорема 15.3. Граф 3 ─ связен тогда и только тогда, когда он или совпадает с колесом, или получается из колеса с помощью двух типов операций:

1) добавление нового ребра;

2) замена вершины V с r (V), по крайней мере, на две смежные вершины V’, V’’, где каждая вершина, которая была смежна с V, соединяется точно с одной из V’, V’’ так, чтобы в полученном графе r (V’) ³ 3 и r (V’’) ³ 3.

Дата добавления: 2015-10-26