Сколько в графе цепей
Перейти к содержимому

Сколько в графе цепей

МАРШРУТ, ПУТЬ, ЦЕПЬ, ЦИКЛ

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

Конечная последовательность ребер в[, е2, . еп графа (не обязательно различных) называется маршрутом длины п, если существует последовательность vo, v,, v„ из л+1 (не обязательно различных) вершин. Одно ребро рассматривается как маршрут единичной длины.

Путь — маршрут, в котором все ребра различны.

Маршрут замкнут, если начальная vq и конечная v„ вершины совпадают vq — v„, и не замкнут, если v0Ф v„ .

Пример. На рис. 5.5 последовательность ребер е, е$, е4, е$, е$, e-j образует незамкнутый маршрут длиной 6 единиц. Последовательность е$, е2, *7» е ь образует путь, а е3, е2, ei, е4, еь — замкнутый путь.

Иллюстрация понятий «маршрут (путь)», «цепь», «цикл»

Рис. 5.5. Иллюстрация понятий «маршрут (путь)», «цепь», «цикл»

Если все ребра, составляющие маршрут, различны и при этом начальная и конечная вершины маршрута не совпадают, он называется цепью (последовательность ребер в, е4, е$ на рис. 5.5). Если цепь замкнута, маршрут называется циклом (последовательность ребер е, еь, е4, е 5 на рис. 5.5).

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

Цикл, в котором содержатся все ребра графа, причем каждое ребро встречается только один раз, называется эйлеровым. Эйлеров цикл содержится в графе, не содержащем вершин нечетной степени.

Пример. Последовательность ребер от исходной вершины v0 графа рис. 5.6 составляет эйлеров цикл С= 3, vb v0, v4, vb v* v5, v4, v^, v0).

Эйлеров цикл

Рис. 5.6. Эйлеров цикл

Для того чтобы в графе имелась эйлерова цепь, содержащая все его ребра в точности но одному разу (начальная и конечная вершины маршрута не совпадают), необходимо и достаточно, чтобы V/ и vj были единственными вершинами нечетной степени (рис. 5.7). На любом связном графе с 2к нечетными вершинами имеется семейство из к цепей, которые содержат все ребра графа по одному разу (рис. 5.8).

Граф, содержащий эйлерову цепь

Рис. 5.7. Граф, содержащий эйлерову цепь

Граф, содержащий семейство, состоящее из 2 эйлеровых цепей

Рис. 5.8. Граф, содержащий семейство, состоящее из 2 эйлеровых цепей

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

Граф с п вершинами имеет гамильтонов цикл, если для любой пары его вершин выполняется соотношение

В частности, граф имеет гамильтонов цикл, если для каждой его вершины

Если выполняется условие то граф имеет гамильтонову цепь.

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

При решении ряда технических задач, связанных, например, с расчетом электрических цепей требуется определение числа независимых контуров (циклов). Эта задача решается путем определения цикломатического числа y(G) графа G, имеющего п вершин, т ребер и г компонент связности:

Маршруты, цепи, циклы в графах

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

Определение 4-14- Пусть G= (V, Е) — граф. Маршрутом длины, к из вершины v в вершину w (или (щ гф-маршрутом) в графе G называется последовательность вершин До, V. щ) (необязательно различных) е V таких, что Vq = v, Vk = w, и (щ_i, vt) е Е для всех г — 1,2. к. Вершины v и w называются концевым,и (v — начальной, w — конечной) вершинами маршрута, а остальные вершины — внутренними.

Ясно, что маршрут можно задать и последовательностью ребер: (ei = (гд, г’1), во = (v, гь). ед. = (vk-i, Vk)) • Любой участок маршрута сам я в л яется м ар ш рутом.

Определение 4-15. Маршрут называется цепью, если все его ребра различны и простой цепью, если все его вершины (возможно, кроме концевых вершин) различны.

Определение 4-16. Если в маршруте До,щ,щ) начальная и конечная вершины совпадают До = г;Д, то он называется замкнутым маршрутом. При этом обычно считают, что последовательности (vo,vi. vk), (vi. Vk,v0), — различные записи од-

ново и того же маршрута. Замкнутая цепь называется циклом, а замкнутая простая цепь простым циклом,.

Пр и м е р 4.7. Привести пример маршрута, цепи, цикла, простой цепи и простого цикла в графе, заданном на рис. 22.

Маршрутом в данном графе, например, является следующая последовательность вершин (гд, г д, г у, гд, гц, го, гд). Однако данный маршрут не является цепью, так как содержит одинаковые ребра. Цепью, например, является следующий маршрут (гд, 1’2, г’б, г/Д, v4, гд, v$). Примером простой цепи может служить маршрут (гд, гд, гдц гд, гд). Циклом является замкнутая цепь, например, (гд, го/ее, г?з, гд, го, гд, гд). Простая цепь (го,гд,г/’з, гд, гд) является простым циклом.

Любая цепь является подграфом. Любой участок цепи или цикла — это цепь, а участок простой цепи или простого цикла — простая цепь.

Длина любого цикла в графе не меньше трех, так как по определению граф не содержит кратных ребер. Минимальная из длин всех циклов графа называется его обхватом.

Справедливы следующие утверждения:

  • 1) для различных вершин v^w любой (го г/фмаршрут содержит простую (гд гг;)-цепь;
  • 2) всякий цикл содержит простой цикл;
  • 3) объединение двух несовпадающих простых (уду)-цепей содержит простой цикл.

Следующая теорема позволяет по матрице смежности графа исследовать его маршруты ([14] §4.3).

Теорема 4.3. Если C(G) — матрица смежности графа (С, то (гщ)-й элемент матрицы C k (G) = C(G). G(G) равен числу (гд, гд)-

маршрутов длины к.

Следствие 1. В графе G тогда и только тогда существует (гд,гд)- маршрут (/’ДД, когда (г,j)-й элемент матрицы C(G) + C 2 (G) + . + +C n

Следствие 2. В графе G тогда pi только тогда существует цикл, содержащий вершину щ, когда (г, г)-й элемент матрицы («(G) + C 2 (G) + + . + C n

l (G) не равен нулю.

П р и м е р 4.8. Определить, существуют ли (^2, щ)-маршруты в

графе G, который задан матрицей смежности («(G) = J .

Элемент С24 = 0, значит (^2,^4)-маршрута длины 1 пет.

В матрице C 2 (G) соответствующий элемент равен 0, значит маршрута длины 2 нет.

В графе G существует один (уд, гц)-маршрута длины 3, так как соответствующий элемент в С 3 (С) равен 1. Это маршрут (гд,гц, гд,гц).

В некоторых прикладных задачах встречаются так называемые двудольные графы.

Определение 4-17. Двудольным называется граф G=(VE), множество вершин которого можно разбить на два подмножества V и Ух (V П Vj = 0) таким образом, что каждое ребро графа G соединяет вершины из разных множеств. Если при этом каждая вершина из одного подмножества смежна с любой вершиной другого подмножества, то граф называется полным двудольным.

На рис. 23 и 24 изображены двудольные графы, причем граф на рис. 24 — полный двудольный.

Справедлива следующая теорема.

Теорема 4.4. Граф является двудольным тогда и только тогда, когда все его простые циклы четной длины.

П р и м е р 4.9. Доказать, что граф, заданный матрицей смеж-

/О 1 0 1 0

hocthC(G) = О 1 О 1 0 двудольный.

Используем теорему 4.3 для вычисления количества циклов данного графа. Чтобы найти количество циклов длины 3, вычислим матрицу С 3 (С7).

Все диагональные элементы матрицы C 3 (G) равны 0, следовательно, циклов длины 3 у данного графа нет. Чтобы найти количество циклов длины 5, вычислим матрицу C 5 (G).

Циклов длины 5 у данного графа тоже нет, так как все диагональные элементы матрицы C 5 (G) равны 0. У графа всего 5 ребер, поэтому делаем вывод, что простых циклов нечетной длины в нем нет. Значит, он двудольный.

Сколько в графе цепей

Множество точек (вершин, узлов) и множество линий (ребер, дуг), которые соединяют эти точки, будем называть графом Г. Граф Г3 (рис. 3.1а) и ему подобные конструкции из линий и точек называется полным, поскольку все его вершины связаны между собой линиями. Граф, изображенный на рис. 3.1б, полным уже не назовешь, однако линии такого частичного графа образуют полную цепь. Цепь называется полной, если она связывает все точки графа линиями без образования петель и контуров. Цепи, связывающие только часть точек (рис. 3.1в), мы рассматривать не будем и, следовательно, термин «полная» применительно к цепи можно будет опускать без риска быть непонятыми.

Рис. 3.1

Цепь имеет голову и хвост. Голова цепи привязывается к какой-либо точке, которую мы будем в этом случае называть привязкой. Для графа Г3, если в качестве привязки выступает точка a, имеем две цепи abc = 02, acb = 12; если привязкой является точка b, получим еще две цепи — bac = 01, bca = 21; наконец, если c — привязка, то cab = 10, cba = 20 — цепи. Вместо шести мы на самом деле имеем только три цепи A, B и C, поскольку не столь уж важно, каким образом начинается запись цепи — с головы или с хвоста; отсюда получаем:

A = 01 = 10, B = 02 = 20, C = 12 = 21.

Одной из тем этого подраздела является поиск групп преобразования цепей. Дело в том, что, скажем, цепь 01 переходит в цепь 02 путем замены линии 1 на линию 2, при этом линия 0 остается на месте. Этот переход можно записать как 12 или 21. Обратный переход цепей друг в друга осуществляется при противоположной замене линий, т.е. 12 = 21. Последовательная замена линий: сначала 12, затем 12, оставляет исходную цепь 01 тождественной самой себе. Но осуществление двух различных замен, например, 12 и 01 по отношению к исходной цепи 01, приводит к преобразованию: из 01 в 02 и из 02 в 12, что равносильно действию замены 02.

Цепи образуют субстанционное множество, а преобразования — операционное. При замене отдельных звеньев цепи удобно воспользоваться аддитивной записью. В частности, действие преобразования mn на цепь lm выразится через суммы:

01 + 12 = 02, 01 + 02 = 12, 02 + 01 = 12, . ,

а переходы от одной цепи к другой запишутся через разности, например, преобразование A в B как A – B = 01 – 02 = 12, обратное преобразование как B – A = 02 – 01 = 12. Все остальные преобразования в Г3 запишутся с помощью следующих простых выражений:

A – C = 01 – 12 = 02, B – C = 02 – 12 = 01,

C – A = 12 – 01 = 02, C – B = 12 – 02 = 01,

A – B – A = A – A = 12 + 12 = e, B – A – B = B – B = 12 + 12 = e,

A – C – A = A – A = 02 + 02 = e, C – A – C = C – C = 02 + 02 = e,

B – C – B = B – B = 01 + 01 = e, C – B – C = C – C = 01 + 01 = e,

C – A – B = C – B = 02 + 12 = 01, B – A – C = B – C = 12 + 02 = 01,

A – C – B = A – B = 02 + 01 = 12, B – C – A = B – A = 01 + 02 = 12,

A – B – C = A – C = 12 + 01 = 02, C – B – A = C – A = 01 + 12 = 02.

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

Однако в группах цепей имеются и важные отличия по сравнению с ранее рассмотренными группами, а именно: не всякое преобразование gj может последовать за преобразованием gi. В частности, преобразование 12 не может последовать за преобразованием 02, поскольку первое отвечает переходу цепи A в цепь B, а второе — переходу цепи A в цепь C; между тем разрешен переход от A к B и от B к C. Таким образом, в графах на операционное множество накладывается жесткое ограничение, продиктованное субстанционным множеством. Своенравная природа графа проявляется и в совершенно новом делении элементов группы на классы эквивалентности. Здесь уже нет классов сопряженных элементов и классов смежности, иначе находятся подгруппы, отсутствуют делители и т.д. Покажем на примере группы G3 от графа Г3, как производится групповой анализ графа.

Пусть вершина a треугольника, изображенного на рис. 3.1а, является привязкой. Следовательно, она находится в особом положении относительно двух других вершин треугольника — b и c. Так возникают два класса вершин — a> и b, c>. Стороны треугольника также разбиваются на два класса в зависимости от степени удаленности от привязки — и . Это деление на классы пока никак не проявляется на строении группы G3. Привязка a определяет две цепи — B и C, для которых возможны переходы 01 и 01, принадлежащие одному классу. Вместе с тождественным преобразованием они дают элементарную подгруппу G3a = e, 01, 01>. Каждая привязка определяет свою подгруппу: G3b = e, 02, 02>, G3c = e, 12, 12>. Все вместе элементы G3a, G3b и G3c образуют графовую группу преобразований цепей в треугольнике:

G3 = e, 01, 01, 12, 12, 02, 02>.

В процессе формирования группы G3 была установлена и соответствующая иерархия элементарных подмножеств, которую, как мы знаем, удобно представлять в виде решетки S(G3). Если наши подгруппы обозначить через числа 1, 2, 3, тождественный элемент через 0, то отношение порядка между подгруппами S(G3) будет выглядеть так, как это показано на рис. 3.2.

Рис. 3.2

Прежде чем переходить к анализу следующей группы, обратим внимание на то, что наименьшей группой преобразования цепей является G2 = e>, которая оставляет свою единственную цепь, соединяющую две вершины, в покое. Группа G3 является первой нетривиальной графовой группой преобразования цепей с двумя образующими, неоднозначно определенными, например, такими: a = 01, b = 12. Тогда все остальные элементы группы G3 выразятся следующим образом:

Не забудем сказать и о том, что все группы цепей коммутативны и нечетны. Проявлением аддитивной сущности графовых групп является отсутствие степеней образующих. Для мультипликативных подстановок было справедливо условие:

если a · b = c, то a = c · b –1 и b = a –1 · c ;

для аддитивных реберных подстановок истинным является аналогичный закон с учетом коммутативности:

если a + b = c, то a = b + c и b = a + c.

Добавить комментарий

Ваш адрес email не будет опубликован.