Краткий курс лекций по Дискретной математике (стр. 14 )

Если G – дерево, тогда любая цепь будет простой.

Любые две вершины дерева можно соединить цепью, притом простой.

Пусть G – дерево. Если добавить одно ребро, то получим ровно один простой цикл.

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

Рассмотрм одну из таких задач. Для этого введем еще одно определение.

Остовом (покрывающим деревом) графа называется его подграф, являющийся деревом и содержащий все вершины графа.

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

Проектирование сети дорог сводится к построению остова гарфа, имеющего минимальный вес. В силу связности дерева выполнится условие соединить каждый город с каждой дорогой.

Рассмотрим сначала задачу построения остова без учета весов его ребер. Идея алгоритма состоит в том, что просматриваются в произвольном порядке ребра графа и св соответствии с правилом принимается решение о включении очередного ребра в остов.

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

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

Алгоритм построения остова

Шаг 1. Выбрать любое ребро и окрасить в зеленый цвет. Образовать подграф G1 из этого ребра. Выполнить шаг 2.

Шаг 2. Пусть просмотрено i > 1 ребра графа G. Выбрать любое неокрашенное ребро. Возможны четыре варианта.

Вариант а. Окрасить ребро в зеленый цвет и сформировать подграф Gi+1 , добавив к компонентам подграфа Gi новую компоненту связности – рассматриваемое ребро. Выполнить шаг 2.

Вариант б. Окрасить ребро в зеленый цвет и сформировать подграф Gi+1 , объединив две компоненты связности в одну. Выполнить шаг 2.

Вариант в. Окрасить ребро в зеленый цвет и сформировать подграф Gi+1 , добавив к одной компоненте подграфа Gi рассматриваемое ребро. Выполнить шаг 2.

Вариант г. Окрасить ребро в красный цвет, если оно образут в построенным подграфе цикл.

Замечание. Данный алгоритм называется «жадным», т. к. каждое ребро просматривается не более одного раза, т. е. после просмотра оно окрашивается в зеленый или красный цвет, и в рассмотрение больше не включается.

Построим остов для графа, заданного диаграммой, не учитывая вес ребер.

Окрасим ребро {v1, v2} в зеленый цвет.

Окрасим ребро {v4, v5} в зеленый цвет, т. к имеет место вариант а.

Окрасим ребро {v4, v1} в зеленый цвет, т. к имеет место вариант б.

Окрасим ребро {v2, v5} в красный цвет, т. к имеет место вариант г.

Окрасим ребро {v4, v3} в зеленый цвет, т. к имеет место вариант в.

Ациклический подграф содержит все вершины графа, значит остов построен:

 

Присвоим каждому ребру вес. И построим остов с минимальным весом (минимальный остов).

Алгоритм построения такого остова отличаеися от вышеизложенного лишь тем, что ребра просматриваются в порядке возрастания их весов. Если на каком – то шаге среди непросмотренных ребер имеется более одного ребра с наименьшим весом, то рассматривается на данном шаге любое из них.

У порядочим ребра графа, переписывая их в порядке возрастания их весов: {v1, v2}, {v4, v5},{v1, v4},{v5, v2},{v3, v5},{v3, v2},{v1, v3},{v4, v3}.

Окрасим ребро {v1, v2}в зеленый цвет.

Окрасим ребро {v4, v5} в зеленый цвет (вариант а).

Окрасим ребро {v1, v4} в зеленый цвет (вариант б).

Окрасим ребро {v5, v2} в красный цвет (вариант г).

Окрасим ребро {v3, v5} в зеленый цвет (вариант в).

Ациклический подграф содержит все вершины графа, значит остов построен:

 

5.  Цикловой ранг графа. Цикломатическое число

Если G(V, X) не является ациклическим графом, то в нем можно выделить цикл.

Независимыми называются циклы графа G, если они отличаются хотя бы одним ребром.

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

Количество простых циклов в базисе называется цикломатическим числом или циклическим рангом графа G.

Обзначим цикломатическое число через n(G).

Справедливо утверждение:

Если G(V, X) – связный граф, то n(G) = m(G) – n(G) + p(G), где m(G) – количество ребер в графе, n(G) – количество вершин в графе, p(G) – количество компонент связности в графе.

Так, например, для дерева не существует цикловой базис, т. к. в дереве m = n – 1, р = 1(дерево – связный граф). Тогда цикломатическое число равно n(G) = n – 1 – n +1 = 0. Следовательно в базисе нет ни одного цикла.

Рассмотрим алгоритм нахождения циклового базиса связного мультиграфа.

Если n(G) = 0, то граф ациклический, циклового базиса не существует.

Пусть n(G) > 0. Выделим в G любое остовное дерево Т. Пусть число вершин в графе G равно n, а число ребер – m. x1, x2,…, xn-1 – ребра в Т (остовное дерево содержит все вершины графа, а по свойству дерева число ребер на 1 меньше числа вершин), xn, xn+1,…, xm – остальные ребра графа G (заметим, что n ³ 2, m ³ n). Число последних ребер m – (n – 1) = m – n + 1, и совпадает с цикломатическим числом связного графа. Добавляя любое из ребер xi ( i = n, …, m) , к дереву Т, получаем некоторый подграф графа G, из которого выделяем простой цикл mi-(n-1) , проходящий через ребро xi. Действуя таким образом, находим совокупность простых циклов {m1, mm-n+1}. Т. к. в каждом из циклов этой системы имеется ребро, не содержащееся в других циклах, то полученная система независимая, следовательно, является цикловым базисом графа G.

Используя данный алгоритм, определим цикловой базис мультиграфа, представленного на рисунке:

Вычислим цикломатическое число: n =4, m = 8, p =1, следовательно, n(G) = 8 - 4 + 1 = 5. Значит, цикловой базис содержит 5 независимых циклов. Построим остовное дерево:

Добавим по одному удаленные из графа ребра и будем, таким образом, получать простые циклы:

Добавим ребро х3, получим цикл v1 x2 x3 x5 v1.

Добавим ребро x6 , выделим простой цикл: v1 x2 x3 x6 v1.

Добавим ребро x7 , выделим простой цикл: v1 x2 x7 x1 v1.

Добавим ребро x8 , выделим простой цикл: v1 x2 x8 x1 v1.

Добавим ребро x4 , выделим простой цикл: v1 x2 x3 x4 х1 v1.

Получили пять циклов, составляющих цикловой базис графа.

Контрольные вопросы

1.  Какой маршрут называется минимальным?

2.  Алгоритм выделения минимального маршрута в ненагруженном неорграфе.

3.  Алгоритм выделения минимального маршрута в нагруженном графе.

4.  Какой граф называется ациклическим? Какой подграф называется остовом? Алгоритм его построения.

5.  Что называется цикловым рангом графа? Что такое цикломатическое число, цикловой базис графа? Алгоритм построения циклового базиса графа.

ЛЕКЦИЯ 19

ТЕМА: ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ЦЕПИ И ЦИКЛЫ

ПЛАН:

1.  Эйлеровы цепи и циклы

2.  Гамильтоновы циклы и цепи

Главная

1.  Эйлеровы цепи и циклы

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

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

Пусть G(V, X) – псевдограф. Цепь (цикл) в G(V, X) называется эйлеровой (эйлеровым), если она (он) проходит по одному разу через каждое ребро графа G(V, X).

Поставим в соответствие схеме мультиграф, в котором каждой части суши соответствует вершина, а мостам – ребра. На языке теории графов задача прозвучит так : найти эйлеров цикл в мультиграфе G(V, X).

V1

V2

V3

V4

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

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

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

Доказательство проведем по индукции.

Пусть G содержит только одно ребро, тогда это ребро – петля, т. к. нет висячих вершин, а петля – это простой цикл.

 

Пусть G содержит два ребра, тогда это кратные ребра. И, следовательно, простым циклом является v x1 w x2 v:

Пусть граф не содержит кратных ребер, т. е G – граф и v1 , v2 – произвольные смежные вершины графа. Рассмотрим последовательность v1, v2, v3…вершин графа G такую, что для любого i ³ 3 вершины vi, v i-1 смежны и vi ¹ vi-2 :

vi-2 vi-1 vi

 

Поскольку в графе нет висячих вершин, то такую последовательность можно продолжать неограниченно. Используя конечность множества вершин графа, получаем, что обязательно произойдет совпадение vi = vj, где 1£ i < j – 2. Пусть это будет первое совпадение, т. е. совпадение с наименьшим номером j. Тогда последовательность vi v i+1 v i+2…vj – простой цикл в графе.

Введем обозначения: если m1 и m2 – циклы псевдографа G, имеющие хотя бы одну общую вершину и не имеющие общих ребер, то, очевидно, существует цикл, проходящий через все ребра, входящие в m1 и m2 . Обозначим m1 + m2 любой из таких циклов. Для любого цикла обозначим V(m) и X(m) соответственно множество вершин и множество ребер, входящих в m.

Пусть m - цикл без петель. Тогда для "v Î V(m) количество ребер в Х(m), инцидентных v, четно.

Поскольку в цикле m отсутствуют петли и все ребра попарно различны, то с каждым новым вхождением в m вершины v в этот цикл войдут также два новых инцидентных ей ребра, а следовательно, общее число ребер в Х(m) инцидентных v, четно.

Следствие. Если вершина входит в некоторый цикл. То она не может быть висячей.

Теперь сформулируем и докажем теорему о существовании в графе эйлерова цикла.

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

Необходимость. Пусть G обладает эйлеровым циклом.

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

Достаточность. Пусть m – количество ребер в G.

При m = 1 связный псевдорграф G с вершинами четной степени может выглядить только следующим образом: G(V, X), где V = {v}, X = {x = {v, v}}. Значит, G(V, X) – петля, а петля – это эйлеров цикл.

Предположим, что для некоторого целого m ³ 2 достаточность доказана для всякого псевдографа с m -1 ребрами. Докажем справедливость для псевдографа с m ребрами.

Пусть в связном псевдографе G c m ребрами степени вершин четны. В силу утверждения 1 в G имеется простой цикл m0 . Если m0 содержит все ребра из G, то эйлеров цикл найден. В противном случае удаляем из G все ребра, содержащиеся в m0. в результате получим псевдограф G' , каждая компонента связности которогоявляется либо изолированной вершиной, либо псевдографом, степень каждой вершины которого четна. Пусть Gi, где i = 1, 2, …р – компоненты связности графа G',отличные от изолированных вершин. По предположеню, для каждого псевдографа Gi можно построить эйлеров цикл mI. В силу связности G цикл m0 имеет общие вершины с любым из циклов mi , где i = 1, 2, …р. Тогда искомым эйлеровым циклом в G является цикл :

m = (…((m0 + m1 ) + m2) + …+ mр).

Сформулируем и докажем теорему о существовании эйлеровой цепи в графе.

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

Необходимость. Пусть G имеет эйлерову цепь, соединяющую v и w. Добавим к G дополнительное ребро {v, w}. Получим псевдограф G', обладающий эйлеровым циклом, а следовательно, степени вершин графа G' четны. Но тогда четны и степени вершин псевдографа G, за исключением вершин v и w.

Достаточность. Пусть G имеет ровно две вершины v и w нечетной степени. Добавим к G новое ребро {v, w}. Получим связный псевдограф G' со всеми вершинами четной степени. Тогда в графе G' существует эйлеров цикл. Исключив из этого цикла ребро {v, w}, получим эйлерову цепь, соединяющуя вершины v и w.

Замечание. Эйлерова цепь соединяет вершины нечетной степени. Вернемся к задаче о Кенигсбергских мостах. Необходимое условие существования эйлерова цикла или эйлеровой цепи выполняется, т. к граф связный. Найдем степени вершин графа: d(v1) = d(v2) = d(v4) = 3, d(v3) =5. Значит, граф не обладает ни эйлеровым циклом, ни эйлеровой цепью.

Познакомимся с алгоритмами выделения эйлерова цикла и эйлеровой цепи.

Алгоритм 1 выделения эйлерова цикла в связном мультиграфе G(V, X), где Х ¹Æ и степени вершин четны..

1.  Выделить из G цикл m1. Положить k = 1 (k - число циклов), G' = G.

2.  Удалить из G' ребра, принадлежащие множеству Х(mk). Полученный псевдограф снова обозначить G'. Если в G' отсутствуют ребра, то переходим к шагу 4. В противном случае выделяем из G' цикл mk+1 и перейти к шагу 3.

3.  Присвоить k: = k + 1 и перейти к шагу 2.

4.  По построению m1 , …, mk – циклы. Если k = 1, то m1 – искомый эйлеров цикл, работа алгоритма заканчивается. В противном случае находим цикл mi такой, что V(mi) Ç V(m1) ¹Æ, где 2 £ i £ k. Перейти к шагу 5.

5.  Присвоить к: = i – 1, m1 : m1 + mi, mj : mj+1 , j = I, …, k. Перейти к шагу 4.

Применим этот алгоритм для выделения эйлерового цикла для псевдографа с четными степенями вершин..

Удалим из G петли. Получим связный мультиграф G’, степени которого четны. Пусть в G’ имеется хотя бы одно ребро. Тогда, применяя к G' приведенный алгоритм, найдем эйлеров цикл в графе G'. Добавляем в этот цикл удаленные петли, получим эйлеров цикл в G.

Рассмотрим теперь применения этого алгоритма для выделения эйлеровой цепи в связном псевдографе, имеящим ровно две вершины v, w нечетной степени., где Х ¹Æ. Добавляя к G ребро {v, w}, получим псевдограф G' с четными степенями вершин. Выделив в G' эйлеров цикл и удалив из него ребро {v, w} , получим эйлерову цепь.

Алгоритм 2 выделения эйлерова цикла в связном мультиграфе G(V, X), где Х ¹Æ и степени вершин четны.

1.  Выбрать произвольно некоторую вершину v.

2.  Выбрать произвольно некоторое ребро х, инцидентное v, и присвоить ему номер 1.

3.  Каждое пройденное ребро вычеркивать и присваивать ему номер, на единицу больший номера предыдущего вычеркнутого ребра.

4.  Находясь в вершине vi, не выбирать ребра, соединяющего vi с v, если есть возможность другого выбора.

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

6.  После того, как в графе будут занумерованы все ребра, цикл, образованный ребрами с номерами от 1 до n, где n – число ребер в графе, есть эйлеров цикл.

Для использования этого алгоритма для построения эйлеровой цепи первый пункт будет таким: выбрать вершину с нечетной степенью. Остальные шаги не изменятся.

Пример. Построить эйлеров цикл, используя оба алгоритма.

Применим первый алгоритм.

Данный псевдограф - связный. Найдем степени вершин: d(v1) = 4, d(v2) = 4, d(v3) = 6, d(v4) = 4, d(v5) = 4. Все степени вершин четные, следовательно, граф обладает эйлеровым циклом. Построим его.

Используем первый алгоритм.

Удалим петли х10 и х11. Получим мультиграф. Выделим цикл v3x4x2x5v3 – обозначим m1. Удалим ребра x4, x2, x5 . Снова выделяем цикл v3x3x1x6v3 - m2 . V(m1)ÇV(m2) = {v1, v2, v3}. Удалим ребра. Выделяем цикл v3x7x9x8v3 - m3. V(m2)ÇV(m3) = {v3}. В мультиграфе построили эйлеров цикл m1 + m2 + m3 . Добавим удаленные петли и получим цикл в заданном графе: v3x4x2x5 x3x1x6 x7 x10 x9 x11 x8v3.

Используем второй алгоритм.

Как и в первом алгоритме, удалим петли, получим мультиграф. Выберем любую вершину, например, v3. Выберем инцидентное ей ребро, например, х7 . Присвоим ему номер 1, т. е. х71 и вычеркнем. Выбираем инцидентное ребро вершине v4 – это ребро х9, присвоим ему номер 2 – х92 , вычеркнем. Выбираем инцидентное ребро вершине v5 – это ребро х8, присвоим ему номер 3 – х83 , вычеркнем. Далее аналогичным образом выбираем ребра х4, х2, х5 и х3, х1, х6. В мультиграфе эйлеров цикл построен. Добавим в него удаленные петли. Окончательно получим эйлеров цикл в данном графе: v3x7x10x9 x11x8x4 x2 x5 x3 x1 x6v3.

2.  Гамильтоновы циклы и цепи.

Пусть G— псевдограф. Цепь (цикл) в G называется гамильтоновой (гамильтоновым), если она (он) проходит через каждую вершину псевдографа G ровно один раз.

С понятием гамильтоновых циклов тесно связана так назы­ваемая задача коммивояжера: в нагруженом графе G опреде­лить гамильтонов цикл минимальной длины (иными слова­ми, коммерсант должен совершить поездку по городам и
вернуться обратно, побывав в каждом городе ровно один paз, и при этом стоимость такой поездки должна быть мини­мальной.

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

1 2

 

1

 

2

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

Рассмотрим класс графов, в которых заведомо суще­ствуют гамильтоновы цепи и циклы – это полные графы. Очевидно, что в полном графе всегда существуют гамильтонов цикл, а также гамильтоновы цепи, соединяющие две произ­вольные вершины этого графа, т. к. любая вершин полного графа смежна со всеми остальными вершинами Таким образом, простейшим до­статочным условием существования гамильтоновых цепей и цик­лов в графе является его полнота. Приведем также простейшие необходимые условия. Очевидным необходимым условием суще­ствования гамильтоновых цепей и циклов в графе G является связность G. Более тонким необходимым условием существова­ния гамильтонова цикла в графе G является следующее утверждение (примем его без доказательства):

Если граф G обладает гамильтоновым циклом, то в нем отсутствуют точки сочленения.

Приведем наиболее простые методы выделения в графе G(V, X), где V = {v1, …, vn}, гамильтоновых циклов и цепей. Наиболее простым из них является метод перебора всевозможных перестановок vi1, …, vin множества V. Если перестановка является маршрутом в G, то эта перестановка – гамильтонова цепь. По окончании перебора всех возможных перестановок будут выделены все гамильтоновы цепи.

Для выделения гамильтоновых циклов перебираем всевозможные перестановки v1, vi1, …, vin-1 . Если v1, vi1, …, vin-1, v1 – маршрут в графе G, то это гамильтонов цикл.

При выделении всех гамильтоновых цепей необходимо перебрать n! Перестановок, при выделении гамильтоновых циклов – (n – 1)! перестановок.

Описанный метод не учитывает информацию о графе. Рассмотрим метод, аналогичный предыдущему, но учитывающий информацию о графе. Составим всевозможные последовательности вершин vi1, …, vir, где vi1 Î V, vi2 Î G(vi1)\{vi1}, …, vir Î G(vir-1)\{vi1, …, vir-1}, G(vir) \{vi1, …, vir}= Æ, где G(vir) – множество образов вершины vir. Тогда в каждом случае, когда r = n, последовательность vi1, …, vir – гамильтонова цепь. Соответственно, когда r = n, vi1 Î G(vin), последовательность vi1, …, vir, vi1 – гамильтонов цикл.

При этом выделяются все гамильтоновы циклы и цепи.

Контрольные вопросы

1.  Сформулировать определение эйлерова цикла (цепи) .

2.  Необходимое и достаточное условие существования Эйлерова цикла (цепи).Алгоритм построения эйлерова цикла (цепи).

3.  Сформулировать определение гамильтонова цикла (цепи).

4.  Необходимые и достаточные условия существования гамильтонова цикла (цепи).

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

ЛЕКЦИЯ 20

ТЕМА: ДВУДОЛЬНЫЕ ГРАФЫ

ПЛАН:

1.  Двудольный граф. Условие существования двудольного графа

2.  Паросочетания . Реберные покрытия

Главная

1.  Двудольный граф. Условие существования двудольного графа

V1 V2

Определение. Граф G(V, X) называется двудольным, если множество его вершин можно разбить на два подмножества V1 и V2 таких, что V = V1 È V2, V1 Ç V2 = Æ.Т. е. у любого ребра {v, w} Î X, если vÎ V1, то w Î V2. Множества V1 и V2 называются долями графа. На рисунке представлен типичный двудольный граф.

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

Сформулируем задачу назначения на должность.

Имеется m человек и m должностей. Любой человек может занимать некоторые из должностей в соответствии со своей квалификацией. Вопрос: можно назначение на должность произвести таким образом, чтобы занятая каждым человеком должность не противоречила его квалификации.

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

Условие существования двудольного графа формулируется в следующем утверждении, которое примем без доказательства.

Граф G(V, X) двудольный  тогда и только тогда, когда все его простые циклы четной длины.

Если двудольный граф, в котором множеству V1 принадлежат m вершин, а множеству V2 – n вершин, полный, то он обозначается Кm, n. Приведем пример графа К3,3 .

2.  Паросочетания. Реберные покрытия

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

Паросочетанием в М в графе G(V, X) называется подмножество ребер X' множества Х такое, что каждая вершина графа инцидентна не более чем одному ребру из X'.

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

Реберным покрытием С графа G(V, X) называется такое подмножество его ребер X’ множества Х, что каждая вершина графа инцидентна хотя бы одному ребру из X’.

Реберное покрытие, содержащее наибольшее число ребер, называется минимальным реберным покрытием.

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

 

Паросочетаними являются множества: {{v2, v5}, {v3, v6}}, {{v3, v6}, {v4, v7}, {v9, v8}}. Максимальным паросочетанием является, например, множество {{v8, v4}, {v6, v3}, {v5, v2}}. Если в это множество добавить хотя бы одно какое - либо ребро, то это множество уже не будет паросочетанием.

Добавим в максимальное паросочетание ребра {v1, v2}, {v4, v7}, {v9, v8}, получим реберное покрытие, причем минимальное.

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

1.  Пусть М – произвольное паросочетание графа. Возьмем любую вершину vÎ V, которая не инцидентна ни одному из ребер, составляющих М. добавим к паросочетанию любое ребро, инцидентное вершине v, и будем повторять это действие до тех пор, пока не переберем все вершины, не инцидентные ни одному ребру из М. в результате получим множество ребер C'Í Х, являющихся реберным покрытием графа.

2.  Пусть С – произвольное реберное покрытие, вершина vÎ V, инцидентна более чем одному ребру из С. Исключим из С любое инцидентное v ребро и будем повторять это действие до тех пор, покане останется ни одной вершины, которая инцидентна более чем одному ребру. Получим некоторое паросочетание M’ графа G.

Справедливо утверждение, которое примем без доказательства:

Если М – максимальное паросочетание, то C' – минимальное реберное покрытие. Если С – минимальное реберное покрытие, то М' – максимальное паросочетание.

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

Введем несколько необходимых понятий.

Открытая вершина – это вершинане инцидентная ни одному ребру из ребер паросочетания М.

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

Увеличивающая чередующаяся цепь – это чередующаяся цепь, у которой концевые вершины являются открытыми.

Для графа, представленного на рисунке выше возьмем паросочетание М = {{v2, v5}, {v3, v6}}, тогда упорядоченная последовательность ребер {{v1, v2}, {v2, v5}, {v5, v6}, {v6, v3}, {v3, v4}} ­ - увеличивающая чередующаяся цепь.

Алгоритм выделения максимального паросочетания основывается на утверждении:

Паросочетание М тогда и только тогда максимальное, когда для него не существует увеличивающей чередующейся цепи.

Алгоритм построения максимального паросочетания

Задан связный граф G(V, X) и выделено какое – либо паросочетание М:

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

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

Рассмотрим пример на построение максимального паросочетания и минимального реберного покрытиядл вышеприведенного графа:

выделим паросочетание { {v5, v6} ,{v3, v4}} (ребра окрашены в красный цвет); открытыми являются вершины: v1, v2, v7, v8, v9 ; для вершин v2, v7, v8 существуют увеличивающие цепи; для v2 : {v2, v5}, {v5, v6}, {v6, v3}, {v3, v4}, {v4, v7}; для нее максимальное паросочетание : {v2, v5}, {v6, v3}, {v4, v7} (ребра – синие тонкие линии)); для v7 – как для v2 ; для v8 максимальное паросочетание: {v8 , v4}, {v3 , v6} , {v5, v2} (ребра – широкие синие линии).

Из максимального паросочетания, например для вершины v2, построим минимальное реберное покрытие: не инцидентны вершины v1 и v8 . Добавим ребра к М : {v1, v2}, {v8, v4}. Осталась не инцидентной вершина v9. Добавим в построенное реберное покрытие еще одно ребро {v9, v8}.

М вместе с добавленными ребрами – минимальное реберное покрытие данного графа.

 

V5 V6 V7 V8

 

Максимальные паросочетание Минимальное реберное покрытие

Контрольные вопросы

Какой граф называется двудольным. Перечислить перечень некоторых задач на двудольные графы. Условие существования двудольного графа. Что называется паросочетанием и максимальным паросочетанием? Что называется реберным покрытием и минимальным реберным покрытием? Связь между задачами о выделении паросочетания и реберного покрытия. Пояснить понятия – открытая вершина, чередующаяся цепь и увеличивающая цепь. Рассказать алгоритм выделения максимального паросочетания и минимального реберного покрытия.

ЛЕКЦИЯ 21

ТЕМА: ПЛОСКИЕ ГРАФЫ

ПЛАН:

1.  Задача о плоской укладке графа

2.  Основные определения

3.  Алгоритм плоской укладки графа

Главная

1.  Задача о плоской укладке графа

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