Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
1 x 2 x 3 x 4 x G - эйлеров, ибо 2 8 5 4 1 x P x P x P x P , 6 4 7 6 3 2 x P x P x P x P 8 7 4 1) Выберем 1 x и ребро 7 1 1 , x x u и присвоим G : 1 3 5 ему номер 1, затем перейдем в вершину 7 x x i 8 x 7 x 2 6 x 5 x 2) находясь в 7 x , не выбираем вычеркнутое ребро 1. Из Рис. 3.38. оставшихся трех ребер ни одно не является перешей- ком, поэтому выбираем любое, например, 6 7 2 , x x u , присваиваем ему номер 2 и переходим в вершину 6 x x i 3) После восьми шагов опять приходим в вершину 1 x . Построенный цикл: 7 1 , x x 1 8 8 2 2 3 3 5 5 4 4 6 6 7 , , , , , , , x x x x x x x x x x x x x x Если каждое ребро графа G входит в одну из существующих реберно- непересекающихся цепей этого графа, то говорят, что набор таких цепей покрывает граф G . Пусть связный граф G содержит k вершин нечетной степени. Заметим, что по лемме о рукопожатиях (см. задачу 3.9.1) число k четно. В этом случае справедлива теорема о минимальном числе реберно-непересекающихся цепей. Теорема 3.12. Если связный граф содержит ровно k вершин нечетной степени, то минимальное число покрывающих его реберно-непересекающихся цепей равно 2 k . Вопрос о принадлежности графов к классу гамильтоновых решается, как правило, очень трудно. Рассмотрим несколько теорем такого рода (достаточных условий гамильтоновости). Теорема 3.13. Граф со степенной последовательностью (списком степеней его вершин) n P P P 2 1 является гамильтоновым, если для всякого k , удовлетворяющего неравенствам 2 1 n k , истинна импликация k n P k P k n k . На основе теоремы 3.13 были получены другие достаточные условия гамильтоновости. Эти условия проще в практическом применении, но слабее теоремы 3.13. Теорема 3.14 (теорема Оре ). Если для любой пары x и y несмежных вершин графа G порядка 3 n выполняется условие n y P x P , то G - гамильтонов граф. Из этой теоремы вытекает следующее следствие: Ойстин Оре (1899 - 1968) – норвежский математик. 82 Следствие 1. Если 3 n G и для любой вершины x графа G выполняется неравенство 2 n x P , то G - гамильтонов граф. Все эти теоремы дают достаточные условия гамильтоновости. На практике для построения примеров не гамильтоновых графов с заданными свойствами были бы полезны необходимые условия гамильтоновости. Однако для графов общего вида необходимые условия неизвестны за исключением некоторых особых типов графов. Для ориентированных эйлеровых и гамильтоновых графов получены результаты, похожие на вышеприведенные. Следующие две теоремы характеризуют эйлеровы орграфы. Теорема 3.15. Для связного ориентированного графа G следующие утверждения равносильны: 1) граф U S G , эйлеров; 2) для любой вершины S x верно равенство x P x P ; 3) граф G является объединением контуров, попарно не имеющих общих ребер. Теорема 3.16. Связный орграф G содержит открытую эйлерову цепь тогда и только тогда, когда в нем есть две такие вершины x и y , что 1 x P x P , 1 y P y P и z P z P для любой вершины z , отличной от x и y . Вопросы, связанные с распознаванием гамильтоновости орграфа и построением гамильтоновых контуров или путей, являются столь же сложными, как и аналогичные вопросы для неориентированных графов. Следующая теорема дает достаточные условия гамильтоновости неориентированного графа. Теорема 3.17. Пусть G - сильно связный орграф порядка 1 n без петель и параллельных дуг. Если для любой пары x и y его несовпадающих несмежных вершин справедливо неравенство 1 2 n y P x P , то в G есть гамильтонов контур. Пусть U S G , - неориентированный граф, содержащий n вершин, m ребер и k компонент связности, / G - остов графа G . / G имеет k n G v ребер k n u u u ,..., , 2 1 . Эти ребра называются ветвями остова / G . Оставшиеся k n m ребер k n m v v v ,..., , 2 1 , не входящие в / G , называются хордами остова / G По определению дерева, если к остову / G добавить произвольную хорду i v , то в полученном графе i v G / найдется ровно один цикл i C , состоящий из хорды i v и некоторых ветвей остова / G . Цикл i C называется фундаментальным циклом графа G относительно хорды i v остова / G . Множество k n m C C C C ,..., , 2 1 всех фундаментальных циклов относительно хорд остова / G называется фундаментальным множеством циклов графа G относительно остова / G . Ясно, что k n m G v C Пусть m w w w ,..., , 2 1 последовательность k n k n m u u u v v v ,..., , , ,..., , 2 1 2 1 всех ребер графа G . Фундаментальному циклу i C соответствует вектор im i i c c c c ,..., , 2 1 , определенный следующим образом: если , 0 , если , 1 i j i j ij C w C w c Тогда фундаментальное множество циклов C задается матрицей фундаментальных циклов m G v G v G v m m c c c c c c c c c C , 2 , 1 , 2 22 21 1 12 11 , которая имеет 83 вид 2 1 , 2 , 1 , , 2 2 , 2 1 , 2 , 1 2 , 1 1 , 1 1 0 0 0 1 0 0 0 1 C C c c c c c c c c c C m G v G v G v G v G v m G v G v m G v G v , где 1 C - единичная матрица порядка G v содержит лишь хорды фундаментальных циклов i C . Пример 2. Найти матрицу фундаментальных циклов графа G , изображенного на рисунке 3.39. Здесь 10 m , 7 n , 1 k . Так как цикломатическое число равно 4 1 7 10 G v , то для получения остова / G необходимо удалить четыре ребра. Пусть это будут ребра 1, 2, 3 и 4 (остов на рис. 3.39 выделен жирными линиями). Остальные ребра графа G занумеруем цифрами от 5 до 10. Из рисунка видно, что фундаментальный цикл 1 C , соответствующий хорде 1, состоит из ребер 1, 6, 7, 8, цикл 2 C - из ребер 2, 7, 9, цикл 3 C - из ребер 3, 5, 7, цикл 4 C - из ребер 4, 5, 7, 10. Тогда C имеет вид 5 6 4 1 2 7 3 10 8 9 Рис. 3.39. 3.18. Клики, независимые множества Множество вершин графа называется независимым (внутренне устойчивым), если никакие две вершины из этого множества не смежны. Очевидно, что граф, порожденный вершинами независимого множества, будет пустым. Независимое множество называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Наибольшее по мощности независимое множество называется наибольшим. Как установил Шеннон , теория независимых множеств в графе имеет большое значение для фундаментальных проблем теории информации. Сам процесс передачи информации может быть представлен в виде графа, причем максимальное число безошибочных сигналов соответствует максимальному независимому множеству графа. Число вершин в наибольшем независимом множестве графа G называется числом (вершинной) независимости или неплотностью этого графа и обозначается G 0 α . Для графа, 1 x 2 x 3 x 4 x 5 x изображенного на рисунке 3.40, наибольшими независимыми множествами будут: 5 4 3 2 1 , , , , x x x x x и 10 9 8 7 6 , , , , x x x x x , мак- симальными независимыми 6 7 8 1 , , , x x x x , 6 7 10 2 , , , x x x x и так далее. Задачи отыскания наибольшего независимого множества и определения числа независимости, как правило, очень труд- 10 x 9 x 8 x 7 x 6 x ны, поэтому полезны оценки их величин. Рис. 3.40. Теорема 3.18. Для любого графа U S G , верно неравенство S x x P G 1 0 1 α . Клод Элвуд Шеннон (1916 – 2001) – американский математик. 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 10 9 8 7 6 5 4 3 2 1 4 3 2 1 C C C C C 84 Доказательство теоремы 3.18, которое здесь опущено, дает алгоритм построения независимого множества M , такого что S x x P M 1 1 . Множество M строится следующим образом: всякий раз в графе G выбирается вершина минимальной степени и заносится в множество M , после чего эта вершина и все смежные с ней удаляются из графа. Далее процесс повторяется. Построенное таким способом множество M иногда принимают в качестве первого приближения при отыскании наибольшего независимого множества вершин графа. С понятием независимости в графе связано понятие доминирования. Подмножество S S / вершин графа U S G , называется доминирующим (внешне устойчивым), если каждая вершина из / \ S S смежна с некоторой вершиной из / S , т. е. каждая вершина графа находится на расстоянии в одно ребро от доминирующего множества. Доминирующее множество называется минимальным, если никакое его собственное подмножество не является доминирующим. Доминирующее множество, имеющее наименьшую мощность, называется наименьшим. Число доминирования G δ графа G есть наименьшее число вершин, составляющих минимальное доминирующее множество. Отыскание наименьшего доминирующего множества является содержанием многих прикладных задач. Например, задача размещения предприятий в ряде населенных пунктов при условии, чтобы расстояние от каждого из населенных пунктов до какого-либо предприятия не превосходило заданной величины, сводится к построению наименьшего доминирующего множества, если предположить, что вершины графа – предприятия смежны тогда и только тогда, когда расстояние между соответствующими пунктами не превышает заданной величины. Теорема 3.19. Независимое множество максимально тогда и только тогда, когда оно доминирующее. Доказательство. Пусть S S / - максимальное независимое множество. Тогда не может быть вершины / \ S S k , не соединенной с ребром, так как в противном случае множество / S k также было бы независимым, но / S - максимальное по условию. Отсюда но / S - доминирующее множество. Пусть теперь / S - независимое доминирующее множество. Тогда никакую вершину k нельзя перевести из / \ S S в / S так, чтобы множество / S k осталось независимым. Следовательно, / S - максимальное множество. Антиподом понятия независимого множества является понятие клики. Подмножество / S вершин графа U S G , называется кликой, если любые две входящие в него вершины смежны. Это значит, что подграф / / / ,U S G является полным. Определение клик графа полезно в кластерном анализе, при информационном поиске и так далее. Клика называется максимальной, если она не содержится в клике с большим числом вершин, и наибольшей, если число вершин в ней наибольшее среди всех клик. Число вершин в наибольшей клике графа называется кликовым числом или плотностью графа и обозначается через G Практически очевидна следующая теорема. Теорема 3.20. Подмножество вершин графа G является кликой тогда и только тогда, когда оно независимо в дополнительном графе G , т. е. G G 0 α . Клика графа представляет «естественные» группировки вершин в максимально полные подграфы. На рисунке 3.41 представлен граф и все его клики. 1 x 2 x 3 x 4 x 1 x 2 x 2 x 3 x 3 x 3 x 4 x 85 8 x 7 x 6 x 5 x 8 x 7 x 6 x 6 x 5 x 6 x 5 x Рис. 3.41. Граф и его клики. Опишем алгоритм выделения клик в графе. Этот алгоритм представляет собой метод поиска с возвращением по специальному дереву поиска. Каждый узел этого дерева соответствует полному подграфу исходного графа, а само дерево поиска строится следующим образом. Корень дерева поиска – пустое начальное множество S . Пусть теперь S - произвольная вершина дерева поиска какого-либо уровня. Тогда вершиной следующего уровня дерева будет вершина x S , если S x и x смежна с каждой вершиной из S . В дереве поиска вершины S и x S соединяются ребром, которое соответствует вершине x . На рисунке 3.42 показано дерево поиска для графа G , изображенного на рис. 3.41 (вершины обозначены только цифрами, буква x - опущена). Каждая клика мощностью n порождается в дереве поиска ! n раз. При построении дерева все тонкие ребра можно оборвать, они не приводят к новым кликам. При этом необходимо руководствоваться двумя правилами: 1) если все поддеревья узла x S в дереве поиска клик уже исследованы, то необхо- S {1} {2} {3} {4} {5} {6} {7} {8} {1,2} {2,1} {2,3} {2,8} {3,2} {3,7} {3,5} {4,5} {5,4} {5,3} {5,6} {6,7} {6,4} {7,3} {8,2} {3,8} {3,6} {4,6} {6,5} {6,3} {7,6} {8,3} {2,3,8} {3,2,8} {3,7,6} {3,6,5} {4,6,5} {5,4,6} {5,6,4} {6,5,3} {6,7,3} {6,4,5} {7,3,6} {8,2,3} {2,8,3} {3,8,2} {3,6,7} {3,5,6} {4,5,6} {5,3,6} {5,6,3} {6,5,4} {6,3,7} {7,6,3} {8,3,2} {6,3,5} Рис. 3.42. Дерево поиска клик. димо лишь исследовать только те вершины из y S , для которых вершина y не смежна с x ; 2) если S - узел в дереве поиска, а S - узел предыдущего уровня, и все поддеревья узла x S уже исследованы, то все неисследованные поддеревья узла x S можно опустить. Иногда полезно понятие матрицы клик. Пусть U S G , - произвольный граф, p Q Q Q Q ,..., , 1 1 - множество всех его максимальных клик и n x x x S ,..., , 2 1 . Определим бинарную n p - матрицу G C C , строки которой соответствуют кликам из множества Q , а столбцы – вершинам графа G , причем если , 0 , если , 1 i j i j ij Q x Q x c Матрица G C называется |