Лекции по дискретной математике. Глава 2. Часть 2 - файл n1.doc

Лекции по дискретной математике. Глава 2. Часть 2
скачать (527.5 kb.)
Доступные файлы (1):
n1.doc528kb.01.06.2012 12:06скачать

n1.doc

  1   2

2.9. Подструктуры графа

2

Определения

.9.1. Клика




Кликой графа G=(V,E) называется любой полносвязный подграф графа G=(V,E).

В

Примеры

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


2




В данном примере имеется несколько клик с тремя вершинами (например, V={2,3,4}), однако наибольшая клика одна – V={3,4,5,6}




 3


4 




6


5 

 1


 8


7 




9


Рис.2.9.1. Клика и наибольшая клика графа

Меры






(G) – число клики, равное числу вершин наибольшей клики.

Класс сложности






Нахождение клики графа относится к NP-полному классу, а проблема определения наибольшей клики – NP-тяжелая.

Точное решение






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

Эвристические алгоритмы






Существуют несколько типов эвристических алгоритмов решения проблемы наибольшей клики в полиномиальное время:


Простой алгоритм






Один из простейших жадных последовательных алгоритмов поиска максимальной клики носит английское название: 1-opt local search with add move for the MCP.

Введем следующие обозначения:

CC – текущая клика;

PA – множество вершин возможных добавлений, т.е. множество вершин, соединенных ребрами со всеми вершинами текущей клики СС;

degG(S)(v) – степень вершины vS в подграфе G(S), где SV.


  1. Найти вершину v с max vPA{ degG(PA)(v) }(вершину с максимальной степенью);

  2. Если имеется несколько вершин с той же степенью, то выбирается любая из них;

  3. CC := CCv;

  4. Построить множество PA и найти степени этого множества degG(PA)(i), iPA;

  5. Повторить 1 до тех пор, пока PA:=0.


Пример






Задан граф и его таблица инцидентности:


max vPA{ degG(PA)(v) } для начала алгоритма


1

3

6

--

2


2

3

4

--

3


3

1

2

4

5

7

--

4



4

2

3

5

6

--

1

6

5


5

3

4

6

7

8

--


6

1

3

4

5

7

9

--

7

8





9

7

5

6

8

9

--


8

5

7

9

--


9

6

7

8

--


deg1(G)=2;deg2(G)=2; deg3(G)=5;

deg4(G)=4;deg5(G)=5; deg6(G)=6;

deg7(G)=4;deg8(G)=3; deg9(G)=3

Шаг 1. Находим вершину с наибольшей степенью – вершину 6, ее степень равна 6.

Шаг 2. Текущая клика равна

СС:= 6

Шаг 3. Множество вершин, соединенных ребрами со всеми вершинами текущей клики (на первом шаге – это строка таблицы инцидентности для вершины 6), и их степени:

PA:= {1,3,4,5,7,8)

degG(PA) : 2,5,4,5,4,3
Шаг 4. Выбираем из PA вершину с наибольшей степенью. Таких вершин две: 3 и 5. Произвольно выбираем вершину 3.

Шаг 5. Текущая клика равна:

СС:= {3,6}.

Шаг 6. Находим вершины, инцидентные ко всем вершинам текущей клики (имеющие ребра ко всем вершинам текущей клики):

PA:= {1,4,5}.

Их степени равны degG(PA) : 2,4,5.

Шаг 7. Выбираем в РА вершину с наибольшей степенью – вершину 5.

Шаг 8. Текущая клика равна:

СС:= {3,5,6}.

Шаг 9. Находим вершины, инцидентные ко всем вершинам текущей клики (имеющие ребра ко всем вершинам текущей клики):
PA:= {4}.

Степень вершины 4 равна четырем.

Шаг 10. Текущая клика равна:

CC:={3,4,5,6}.

Шаг 11. Находим вершины, инцидентные ко всем вершинам текущей клики (имеющие ребра ко всем вершинам текущей клики):

PA:= { }.

PA пусто, алгоритм стоп.

Найдена максимальная клика (возможно максимальная) клика. В этом можно убедиться, вернувшись к рис.2.9.1.

2.9.2. Независимое множество вершин


Определения






Независимое множество вершин S есть такое подмножество вершин графа G, что любые две вершины в нем не смежны (никакая пара вершин не соединена ребром).

Среди всех возможных независимых множеств Si выделяют наибольшее – максимальное независимое множество вершин.

Пример







Независимые множества вершин

S1={1,3} S2={4,6}

S3={1,4} S4={3,6}

S5={1,3,7} S6={2,7,8}

S7={2,4,8} S8={2,5,7,8}

4



3



2



1








6



8



7






5



Максимальное независимое множество вершин

S8 ={2,5,7,8}


Рис.2.9.2. Независимые множества вершин


Меры








Класс сложности







Проблема нахождения независимого множества вершин является NP-полной, а проблема нахождения максимального независимого множества вершин – NP-тяжелой.

Точные решения






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

Эвристические алгоритмы







Относятся к тем же группам, что и для проблемы нахождения максимальной клики.

Жадный алгоритм







Введем следующее обозначение:

Si – независимое множество вершин графа G=(V,E).

  1. Начальное условие Si:=0;

  2. Если граф не пустой, то случайны образом выбираем вершину vi с наименьшей степенью;

  3. Si:= Si  vi ;

  4. Удалить вершину vi и все инцидентные к ней вершины. Перейти к п.2.

Пример






4



3



2



1






Начальное условие:

Si:=0



6



8



7






5

Шаг 1. Определяем степени вершин: deg1=3; deg2=3; deg3=3; deg4=3; deg5=3; deg6=5; deg7=2; deg8=2.

Имеется две вершины (7 и8) с одинаковой минимальной степенью. Выбираем вершину 8.

Si:={8}

Удаляем вершину 8 и все инцидентные ей вершины (вершины 1 и 6). Получаем подграф


Шаг 2. Определяем степени вершин подграфа, полученного на предыдущем шаге: deg2=1; deg3=3; deg4=3; deg5=2; deg7=1.

Имеется две вершины минимальной степени – вершины 2 и 7. Выбираем вершину 2.

Si:={2,8}

Удаляем вершину 2 и инцидентную ей вершину 3. Получаем подграф


4








7

5 




Шаг 3. Определяем степени вершин подграфа, полученного на предыдущем шаге: deg4=3; deg5=2; deg7=1.

Вершина 7 имеет наименьшую степень.

Si:={2,7,8}

Удаляем вершину 7 и инцидентную ей вершину 4. Получаем подграф, состоящий из одной вершины 5.

Si:={2,5,7,8}

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

2

Определения

.9.3. Паросочетание графа


Паросочетанием M графа G=(V,E) является такое подмножество ребер E, что никакие два ребра в М не инцидентны любой вершине vV (иными словами, в М нет двух ребер, имеющих общую вершину).

Вершина vV будет М-покрытой, если она инцидентна ребру в М, в противном случае вершина будет М-непокрытой.

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

Среди всех возможных паросочетаний графа выделяют два особых вида:

Очевидно:

Меры







Класс сложности






Нахождение паросочетания графа относится к NP-полному классу, а проблема определения наибольшего паросочетания – NP-тяжелая.

Точные решения






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

Алгоритмы для частных типов графов






Наиболее разработанное направление – паросочетания для двудольных графов.

Ниже рассматриваются два подхода:


Метод максимального пути






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

Это приведение достаточно простое. Для заданного двудольного графа G=(V,E) с двумя подмножествами вершин L и R, V=LR, строится сеть G`=(V`,E`):

  1. к графу G=(V,E) добавляется две новые вершины стока и истока s и t, т.е. V`=V{s,t}.

  2. дуги (направленные линии) графа G` задаются следующим образом: E`={{s,u}:L}{{u,v}E: uL,vR}{{v,t}: vR}.

  3. Всем дугам, инцидентным s и t, присваивается единичная емкость, а для всех остальных дуг емкость принимается равной бесконечности.



Пример













L

R





















L

R

s

t

емк.=?





















емк.=1

емк.=1


Рис.2.9.3. Приведение двудольного графа сети


Теорема



Значение наибольшего s-t потока в G` равно числу наибольшего паросочетания в G.

Алгоритм






Наибольший s-t поток можно найти с помощью алгоритма Форда-Фалкерсона.

Дополняющие пути







Путь P= v0, v1, v2, …, vk в графе G является М-чередующимся, если он содержит поочередно ребра из паросочетания М и ребра вне его (в E/М).

Пусть P= v0, v1, v2, …, vk будет простым М-чередующимся путем. Р будет М-дополняющим путем, если v0 и vk не являются вершинами в паросочетании (они являются М-свободными).

Пример






vk-1

М-свободная вершина

v0

v1











vk






М-свободная вершина

Рис.2.9.4. М-дополняющий путь


Теорема существования






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

Алгоритмы






Эта теорема лежит в основании почти всех известных алгоритмов определения наибольшего паросочетания в произвольном графе. Основная идея этих алгоритмов:

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

Для двудольных графов одним из самых эффективных и популярных алгоритмов поиска наибольшего паросочетания является алгоритм Хопкрофта-Карпа (Hopcroft-Karp), исполняемый за О(n4) (n – число вершин графа).


Пример







12

 11

12

 11





1

 6

1

 6



2

 7

2

 7



3

 8

3

 8



4

 9

4

 9

5

 10

5

 10

Наибольшее паросочетание

{{1,11},{3,10},{4,8}, {5,6}}


Рис.2.9.5. Наибольшее паросочетание, найденное алгоритмом Хоплкофта-Карпа


2.9.4. Вершинное покрытие


Определения







Вершинным покрытием S графа G=(V,E) является подмножеством вершин V, которое инцидентно ко всем ребрам негорафа, т.е. для каждого ребра {u,v}E для uS или vS.

Минимальным вершинным покрытием графа G=(V,E) называется вершинное покрытие минимальной мощности S`.

Пример






v2



v1




Вершинное покрытие

и минимальное вершинное покрытие

S`={v1, v4}






v3



v4



Рис.2.9.4. Вершинное покрытие

Меры






Класс сложности







Нахождение вершинного покрытия относится к NP-полному классу, а проблема определения минимального вершинного покрытия – NP-полная.

Точное решение



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

Жадный алгоритм





И

Алгоритм G1

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



  1. Начальное значение множества вершинного покрытия S:=0;

  2. Выбрать любое ребро {u,v};

  3. S:=S  {u,v};

  4. Удалить вершины u и v, а также все инцидентные к ним ребра и все изолированные вершины.

  5. Повторить 2 до тех пор, пока в графе есть ребра.


С

Пример

ложность этого алгоритма – O(n+m), где n –число вершин и m – число ребер графа.



e



c



b



Начальное значение

S:=0




a



d



f



g


Шаг 1. Выбираем ребро {e,d};

S:={e,d};


c



b


Удаляем вершины e и d и все инцидентные к ним ребра и изолированные вершины. Получаем подграф




a


Шаг 2. Выбираем ребро {b,c};

S:={b,c,d,e};

Удаляем все инцидентные ребра и изолированные вершины. Подграф пуст – алгоритм стоп.

Полученное вершинное покрытие неминимально. Минимальным покрытием будет S`={b,d,e}.

Алгоритм G1






  1. Вычислить максимальное или даже наибольшее паросочетание М графа G.

  2. Взять вершины максимального или наибольшего паросочетания в качестве вершинного покрытия графа G.

Замечание






Аппроксимационное отношение алгоритмов G1и G2 равно 2.

2.9.5. Реберное покрытие


Определения







Реберным покрытием называется подмножество ребер U` графа G=(V,E), U`E, такое, что всякая вершина графа G инцидентна ребру из U`.

Минимальное реберное покрытие- минимальное среди всех возможных подмножеств реберных покрытий.

Пример









Рис.2.9.7. Реберное покрытие


Меры






Класс сложности





Проблема нахождения реберного покрытия относится к NP-полным, а вычисление числа реберного покрытия – к NP-тяжелым.

2.9.6. Теоремы о подструктурах графа


Теорема 1 (Идентичности Галлаи-Gallai Idtntities)






Пусть для любого графа G=(V,E) будут

n=|V|,

(G) – число независимости,

(G) – число реберного покрытия,

(G)– число вершинного покрытия,

(G) – число паросочетания,

тогда


Теорема 2







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

  1. Минимальное реберное покрытие будет минимальным тогда и только тогда, когда оно содержит наибольшее паросочетание.

  2. Максимальное паросочетание является наименьшим тогда и только тогда, когда оно содержится в минимальном реберном покрытии.

Теорема 3






Для любого графа G=(V,E) справедливо следующее неравенство
(G)  (G)  2(G).

Теорема 3 (Konig`s Minimax Theorem)






Если G=(V,E) является двудольным графом, то
(G)  (G).
      1.   1   2


        2.9. Подструктуры графа 2 Определения .9.1. Клика
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации