Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
|
3.15. Деревья (основные определения) Существует один простой и важный тип графов, которому разные авторы дали одинаковое название – деревья. Деревья отличаются предельной простотой строения. Существует несколько определений дерева. Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется лесом. Таким образом, деревья являются компонентами леса. Пусть U S G , и , m U n S Тогда справедлива эквивалентность следующих утверждений (см. рис. 3.33): 1) G - дерево; 2) G - связный граф и ; 1 n m 3) G - ациклический граф и ; 1 n m 4) любые две несовпадающие вершины графа соединяет единственная простая цепь; 5) G - ациклический граф, обладающий тем свойством, что если какую- либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл. Ориентированный граф называется ориентированным деревом (ордеревом), если: 1) 1 x существует ровно одна вершина S x 1 , называемая 2 x 4 x корнем, которая не имеет 3 x предшествующих вершин, т. 9 x е. ; 0 1 x P 2) любой верши- 8 x не 1 x x j в графе G непос- 5 x 6 x 7 x 10 x 13 x 14 x 15 x редственно предшествует ро- 11 x 12 x вно одна вершина, т. е. Рис. 3.33. 1 j x P Неориенторованное дерево можно превратить в ориентированное, выбрав в качестве корня произвольную верши- 1 x ну. На рисунке 3.34 корень графа – вершина 6 x . Под- 3 x граф U S G , / / графа U S G , называется остов- ным подграфом, если / S S Подграф / G графа G 2 x 8 x называется остовным поддеревом (остовным карка- 4 x 9 x сом), если S S / и G - дерево. 5 x 7 x Теорема 3.8 (Теорема Кэли ). Число различ- 6 x ных деревьев, которые можно построить на n раз- Рис. 3.34. личных вершинах, равно 2 n n n t Артур Кэли (Кейли) (1821 – 1895) – английский математик. 77 В этой формуле подсчитывается число всех деревьев с данными n вершинами. Многие из этих деревьев изоморфны, и возникает вопрос о числе не изоморфных деревьев среди них. Это более трудная задача, она решается для каждого конкретного случая по алгоритму теории Пойа. Для подсчета числа остовов в графе используется матрица Кирхгофа. Теорема 3.9 (Теорема Кирхгофа). Число остовных деревьев в связном графе G порядка 2 n равно алгебраическому дополнению любого элемента матрицы Кирхгофа G B Подсчитаем, например, по этой теореме число всех остовов графа, изображенного на рисунке 3.15 (стр. 59). Напомним, что матрица Кирхгофа B определяется следующим образом: , , и смежны не и 0, смежны, и , 1 j i x P j i x x x x b i j i j i ij Тогда 1 1 0 0 0 0 0 1 2 1 0 0 0 0 0 1 4 1 0 1 1 0 0 1 2 1 0 0 0 0 0 1 2 1 0 0 0 1 0 1 3 1 0 0 1 0 0 1 2 7 6 5 4 3 2 1 7 6 5 4 3 2 1 x x x x x x x x x x x x x x B . Определим алгебраическое дополнение элемента 11 b . 1 1 0 0 0 0 1 2 1 0 0 0 0 1 4 1 0 1 0 0 1 2 1 0 0 0 0 1 2 1 0 0 1 0 1 3 11 A 1 1 0 1 0 2 1 0 0 1 2 1 0 0 1 3 4 1 0 1 1 2 1 0 0 1 2 1 1 0 1 3 2 1 0 0 0 0 4 1 0 1 0 1 2 1 0 0 0 1 2 1 0 1 0 1 3 1 1 0 0 0 0 4 1 0 1 0 1 2 1 0 0 0 1 2 1 0 1 0 1 3 3 2 0 0 0 12 3 1 0 1 1 2 1 0 1 3 1 0 1 2 1 0 1 2 1 2 1 0 1 2 1 0 1 3 3 4 1 0 1 1 2 1 0 0 1 2 1 1 0 1 3 2 11 1 1 0 0 1 6 0 0 1 0 4 1 . Таким образом, у этого графа существует 11 различных остовов. Все они изображены на рисунке 3.35. 78 Рис. 3.35. Из определения дерева вытекает следующая теорема: Теорема 3.10. Число ребер произвольного неориентированного графа G , которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно k n m , где m - число ребер, n - число вершин и k - число компонент связности графа G . Доказательство. Рассмотрим i -ю компоненту связности i G графа G . Пусть i G содержит i n вершин. Тогда остов i G графа i G , являясь деревом, содержит 1 i n ребро. Следовательно, для получения i G из компоненты i G нужно удалить 1 i i n m ребер, где i m - число ребер в i G . Просуммируем удаляемые ребра по всем компонентам связности, получим k i i m m 1 , k i i n n 1 , k n m n m k i i i 1 1 Число k n m G v называется цикломатическим числом или циклическим рангом графа G , число k n G v называется коциклическим рангом или корангом. G v равно числу ребер, ходящим в любой остов графа G . Очевидно, что m G v G v Из теоремы 3.10 вытекают два следующих следствия. Следствие 1. Неориентированный граф G является лесом тогда и только тогда, когда 0 G v . Следствие 2. Неориентированный граф G имеет единственный цикл тогда и только тогда, когда 1 G v . 3.16. Задача об остове экстремального веса Пусть U S G , - связная сеть. В приложениях часто возникает задача о построении остова графа G , имеющего наименьший вес. Пусть, например, , ,U S G служит моделью железнодорожной сети, соединяющей пункты S x x x n ,..., , 2 1 , а j i x x , ω - расстояние между пунктами i x и j x . Требуется проложить сеть телеграфных линий вдоль линий железнодорожной сети так, чтобы все пункты n x x x ,..., , 2 1 были связаны между собой телеграфной сетью и общая протяженность линий телеграфной сети была наименьшей. Известно несколько алгоритмов построения экстремального остовного дерева. Рассмотрим алгоритм Прима (алгоритм ближайшего соседа), представляющий собой итерационную процедуру, состоящую из двух шагов и выполняющуюся 1 n раз на графе G с n вершинами. Алгоритм может получать минимальное или максимальное по весу дерево, разница заключается лишь в том, что в формуле (3.16.1) находится либо максимум, либо минимум. Пусть S S S S // / , и // / // / , S S S S S Ø, т. е. / S и // S - разбиение множества узлов сети G на два непересекающихся подмножества. Определим пошаговое расстояние между множествами / S и // S следующим образом: , , , ω min , // / // / S x S x x x S S d j i j i (3.16.1) Прим (???? - ????) – американский математик. 79 где j i x x , - дуга, соединяющая вершины i x и j x В алгоритме Прима остовное дерево строится в результате последовательного расширения исходного поддерева. На каждой итерации число вершин и ребер поддерева увеличивается на единицу. Основные шаги алгоритма таковы. Шаг 1. (Присвоение начальных значений). Полагают 1 / x S , где 1 x - произвольная вершина, / / // , \ U S S S Ø. Шаг 2. (Обновление данных). Находится ребро j i x x , такое, что // / , S x S x j i и , , ω min , // / S x S x x x x x j i j i j i Полагают , \ , / // / / S S S x S S j , / / j i x x U U Шаг 3. (Проверка на завершение). Если S S / , то / / / ,U S G - искомый остов. В противном случае переходят ко второму шагу. Пример 1. Построить остов с наименьшим весом для сети, заданной матрицей весов . Построим по этой матрице сеть. Поскольку матрица симметрическая, то граф дан неориентированный. Исходный граф изображен на рисунке 3.36 слева. 12 9 12 4 8 4 7 6 14 9 8 7 5 10 6 5 5 14 10 5 6 5 4 3 2 1 6 5 4 3 2 1 x x x x x x x x x x x x Шаг1. / 6 5 4 3 2 // 1 / , , , , , , U x x x x x S x S Ø. Первая итерация. Шаг 2. , , , , , , , 5 , ω , 6 5 4 3 // 2 1 / 2 1 // / x x x x S x x S x x S S d 2 1 / , x x U Шаг 3. S S / , переход на начало второго шага. Вторая итерация. Шаг 2. , , , , , , , 5 , ω , 6 5 4 // 3 2 1 / 3 2 // / x x x S x x x S x x S S d 3 2 2 1 / , , , x x x x U Шаг 3. S S / , переход на начало второго шага. Третья итерация. Шаг 2. , , , , , , , 6 , ω , 6 5 // 4 3 2 1 / 4 2 // / x x S x x x x S x x S S d 4 2 3 2 2 1 / , , , , , x x x x x x U Шаг 3. S S / , переход на начало второго шага. Четвертая итерация. Шаг 2. , , , , , , , 4 , ω , 6 // 5 4 3 2 1 / 5 4 // / x S x x x x x S x x S S d 5 4 4 2 3 2 2 1 / , , , , , , , x x x x x x x x U Шаг 3. S S / , переход на начало второго шага. Исходный граф Остовный граф 2 x 5 x 2 x 5 x 12 5 5 6 4 6 x 5 5 6 4 6 x 1 x 14 1 x 10 7 4 x 9 4 x 9 80 3 x 3 x Рис. 3.36. Пятая итерация. Шаг 2. // 6 5 4 3 2 1 / 6 3 // / , , , , , , , 9 , ω , S x x x x x x S x x S S d Ø, 6 3 5 4 4 2 3 2 2 1 / , , , , , , , , , x x x x x x x x x x U Шаг 3. S S / . Итак, получен остовный граф. / / / ,U S G изображен на рисунке 3.36 справа, его вес 29 9 4 6 5 5 ω / G 3.17. Обходы графов. Фундаментальные циклы Рассмотрим опросы, связанные с существованием в графе эйлеровых или гамильтоновых цепей и циклов. При решении прикладных задач часто возникает необходимость отбора вершин или ребер графа, связанная с поисками элемента с определенным свойством. Напомним, что связный граф называется эйлеровым, если он содержит цикл, содержащий все ребра графа. Такой граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий. Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Задачи о нахождении эйлеровых и гамильтоновых циклов в графе внешне похожи, однако вторая задача значительно сложнее первой. Принадлежность графа к классу эйлеровых графов легко устанавливается следующей теоремой: Теорема 3.11. Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны. Доказательство. 1. Необходимость Пусть G - эйлеров граф. Тогда цикл этого графа проходит через каждую вершину, причем входит в нее по одному ребру, а выходит по другому. Это значит, что каждая вершина инцидентна четному числу ребер. Таким образом, степени всех вершин четны, так как эйлеров цикл должен содержать все ребра графа G . 2. Достаточность. Пусть степени всех вершин графа четны. Начнем построение цепи 2 P 1 P из произвольной вершины 1 x (см. рис. 3.37). Попав в оче- редную вершину i x , мы всегда можем из нее выйти по друго- i x му ребру, так как степени всех вершин четны. Продолжая та- / 1 P 2 x ким образом, мы закончим цепь 1 P в вершине 1 x , т. е. 1 P бу- дет циклом. Если при этом окажется, что 1 P содержит все // 1 P вершины, то граф будет эйлеровым. 1 x Если 1 P содержит не все вершины графа G , то уда- Рис. 3.37. лим из G все ребра цикла 1 P . Граф 1 1 \ P G G также будет эй- леровым. Кроме того, так как G - связный граф, то графы 1 G и 1 P будут иметь хотя бы одну общую вершину 2 x (см. рис. 3.37). Повторим процедуру построения цикла, начав с вершины 2 x . Получим новый цикл // 1 2 / 1 3 P P P P , который, начиная с 1 x проходит по ребрам цепи / 1 P до 2 x , затем обходит все ребра цепи 2 P и возвращается в 1 x по ребрам цепи // 1 P . Если 3 P не эйлеров цикл, то повторяя описанную процедуру, получим еще больший цикл и так далее до тех пор, пока не получится эйлеров цикл. Для эйлеровых графов существует процедура, называемая алгоритмом Флери , которая позволяет очень быстро построить один из существующих эйлеровых циклов. Этот алгоритм задается следующими правилами. Флери (???? - ????) – французский математик. 81 1) Произвольно выбирается некоторая вершина 1 x и ребро 1 u инцидентное 1 x . Этому ребру присваивается номер 1. Вычеркиваем это ребро 1 u и переходим в вершину 2 x по ребру 2 1 1 , x x u 2) Находясь в вершине i x , следует не выбирать ребро, соединяющее i x с 1 x , если имеется возможность иного выбора. 3) Находясь в вершине i x , следует не выбирать ребро, которое является перешейком (т. е. ребром, при удалении которого граф, образованный не вычеркнутыми ребрами, распадается на две компоненты связности, каждая из которых имеет хотя бы по одному ребру). 4) После того, как в графе будут занумерованы все ребра, образуется эйлеров цикл, причем порядок нумерации соответствует последовательности обхода ребер. |