Файл: Diskretnaya_matematika.doc

3.7.2 . Базисные циклы и разрезающие множества

Пусть T- остов графаG, аg_i^* – хорда кодереваT*. Так как Т – ацикличный граф, то граф Тg_i^* содержит точно один циклC_i. ЦиклC_iсостоит из хордыg_i^* и тех ветвей остова Т, которые образуют единственную простую цепь между концевыми вершинами хордыg_i^*. ЦиклC_i, возникающий в графе Тg_i^*, называетсябазисным цикломотносительно хордыg_i^*остова Т. Множество всех таких циклов, число которых равно цикломатическому числуµ(G) графаG, называютбазисным множеством цикловграфаGотносительно остова Т.

Пусть G(X) – связный граф иX= {X₁,X₂} – некоторое раз­биение множества его вершин:X=X₁ X₂ иX₁X₂ =. Множество ребер графаG, одна концевая вершина каждого из которых принадлежитX₁, а другая –X₂, называетсяразрежающим множествомилиразрезомграфа. Удаление разрежающего множества – разрез графа, разде­ляет граф на две компоненты и делает его несвязным.

Пусть T – остов связного графа G, а g_j – ветвь этого остова. Удаление ветви из остова разбивает остов на 2 компоненты T₁ и T₂. Пусть X₁ и X₂ множества вершин, соответственно, компонент T₁ и T₂, а G₁ и G₂ – подграфы графа G, порожденные множествами вершин X₁ и X₂. Очевидно, что T₁ – остов подграфа G₁, а T₂ – остов подграфа G₂. Следовательно, подграфы G₁ и G₂ связны, а разрез, разделяющий X₁ и X₂, является разрежающим множеством графа G.

Разрежающее множество S_j, составленное из ребер, связывающих вершины компонент T₁ и T₂ остова называется базисным разрежающим множеством графа G. При этом, компоненты T₁ и T₂ остова образованы удалением ветви g_j остова T.

Свойства базисных циклов и разрежающих множеств

1. Базисный цикл C_i относительно хорды g_i^* кодерева T* связного графа G включает точно те ветви остова T, которым соответствуют базисные разрежающие множества, включающие эту хорду.

2. Базисное разрежающее множество S_jотносительно ветвиg_jостоваTсвязного графаGвключает точно те хорды кодереваT*, которым соответствуют базисные циклы, включающие эту ветвь.

3.7.3. Цикломатическая матрица и матрица разрезов

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

1. Количество базисных циклов графа Gравно цикломатическому числу графа - числу ребер в кодереве.

2. Количество базисных разрежающих множеств равно величине ранга графа - числу ребер в остове.

Построим цикломатическую матрицу C= (c_ik) и матри­цу разрезовS= (s_jk) графа, элементы которых:

1, еслиg_k  C_i ; 1, если g_k  S_j ;

c_ik = s_jk =

0, если g_k  C_i . 0, если g_k S_j.

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

Суперпозиция осуществляется с помощью операции сложения по модулю 2 двоичной алгебры, обозначаемой символом . Вектор-строка с_i= (c_i1,c_i2, …,c_im), описы­вающая циклC_iграфа, вычисляется как покомпо­нентная сумма по модулю 2 векторов, соответствующих базисным циклам. Аналогично, вектор-строкаs_j= (s_j1,s_j2, …,s_jm) описывает разрезS_jграфа и вычисляется как сумма по модулю 2 векторов, соответствующих базисным разрезающим множествам.

Рассмотрим пример построения этих матриц для графа, приведенного на рис. 3.30. Сначала вычислим ранг и цикломатическое число этого. Ранг графа – число ребер в остове (рис. 3.31) – равен 4. Цикломатическое число графа – число ребер в кодереве (рис. 3.32) – равно 3. Следовательно, имеем 3 базисных цикла и 4 базисных разрезающих множества. Далее запишем эти базисные циклы и разрезающие множества.

Базисные циклы:

Базисные разрезающие множества:

Составление цикломатической матрицы

где

Составление матрицы разрезов

где

Замечание.Символобозначает операцию сложения по модулю 2. Результат этой операции равен 0, если арифметическая сумма чисел есть четное число, и равен 1–в противном случае.

Цикломатическая матрица Cи матрица разрезовSявля­ются ортогональными, что математически выражается матричным уравнением:CS^T=. ЗдесьS^T– транспони­рованная матрицаS, а– нулевая матрица.

Ортогональность матриц CиSобусловлена тем, что множество хорд, порождающих базисные циклы, и множество ветвей, порождающих базисные разрезающие множества, не пересекаются (рис. 3.30). Легко проверить ортогональность полученных матриц.

3.8. Задача определения путей в графах

3.8.1. Определение путей в графе

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

Граф G(X) с двумя отмеченными вершинамиx_i,x_jназы­вается (x_i,x_j) – плоским, если графG^(X)=G(X)(x_i,x_j), полученный до­бавлением кG(X) ребра (x_i,x_j), является плоским.

Рассмотрим алгоритм определения пути, ведущего из вершины x_iвx_jплоского графа. Еслиx_iне является вершиной никакого про­стого цикла, то при определении алгоритма пути изx_iвx_jв графеG(X) всегда выбирается самый левый или правый коридор (ребро) (рис. 3.33).

–путь при выборе левого коридора;

–путь при выборе правого коридора.

Аналогичный алгоритм определения пути в прадереве предпо­лагает следующие действия. Из корня идти по какой-либо ветви насколько возможно далеко, затем возвратиться на какой-нибудь перекресток и отправиться по новому направлению (еще не прой­денному) и т.д. Искомый путь из x_iвx_jбудет состоять из всех тех ребер, которые в процессе поиска были пройдены по одному разу.

При определении пути в произвольном графе, не являющемся прадеревом, приходим к предыдущему случаю следующим образом. Если, пройдя по некоторому ребру g, попадаем на уже пройденный ранее перекресток х, то реброg«отсекается» от одной из своих концевых точек. После отсечения ребра, пройденные хотя бы один раз, образуют прадерево.

Рис. 3.33. Определение пути в графе

При определении пути в графе с помощью алгоритма Тарринеобходимо в данном алгоритме пользоваться правилом:

а) не проходить дважды по одному ребру в одном и том же направлении;

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

3.8.2. Алгоритм определения кратчайших путей

Эта задача имеет большое значение в практических примене­ниях. К ней сводятся многие задачи выбора наиболее экономичного (с точки зрения расстояния или стоимости) маршрута на имеющейся карте дорог, наиболее экономичного способа перевода динамиче­ской системы из одного состояния в другое и т.д. Существует много математических способов решения, но часто методы, основанные на теории графов, наименее трудоемки.

Рассмотрим задачу о кратчайшем пути. Пусть дан графG(X), ду­гам которого приписаны веса (расстояния, стоимости и т.п.), задаваемые матрицей С = ||c_ij||.

Задача о кратчайшем пути состоит в нахож­дении кратчайшего пути от заданной начальной вершины sXдо заданной конечной вершиныt Xпри условии, что такой путь су­ществует. В общем случае возможно С_ij> 0, С_ij < 0, С_ij= 0. Единст­венное ограничение состоит в том, чтобы в графеG(X)не было цикловс отрицательным суммарным весом.

Приведем очень простой и эффективный алгоритм Дейкстрырешения этой задачи для случая С_ij0i,j. Алгоритм основан на приписывании вершинам временных пометок, причем пометка вер­шины дает верхнюю границу длины пути отsк этой вершине. Вели­чины этих пометок постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это означает, что по­метка уже не является верхней границей, а дает точную длину крат­чайшего пути отsк рассматриваемой вершине. Пустьl(x_i) – пометка вершиныx_i. Опишем основные этапы алгоритма.