Упражения

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

2. Подмножество V' вершин графа G называется доминирующим, если каждая вершина из V(G) \V' смежна с некоторой вершиной из V'. Докажите, что независимое множество является максимальным (не обязательно наибольшим) тогда и только тогда, когда оно доминирующее.

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

3. Верно ли, что любое паросочетание графа содержится в наибольшем паросочетании?

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

Список литературы

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е изд. Пер. с англ. – М: Вильямс, 2011. – 1296 с.

2. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 434 с.

3. Седжвик Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах. Пер. с англ. – СПб: Диасофт, 2002. – 496 с.

4. Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд.: Пер. с англ. – СПб.:БХВ-Петербург, 2011.– 720 с.

5. Троелсен Э. С# и платформа .NET 3.0, специальное издание. –СПб: Питер, 2008. – 1456 с.

6. R. Boppana, M Halldorsson // Approximating maximum independent sets by excluding subgraphs, Bit 32, 2, June 1992

7. P. Erdős, G. Szekerres, //A combinatorial problem in geometry, Compositio Math., 2:463-470,1935.