В.Б. Алексеев, С.А. Ложкин - Элементы теории графов, схем и автоматов (DJVU), страница 3

Обозначим такую матрицу 1,. Рассмотрим операцию умножения магриц, которая отличается от обычного умножения только тем„что вместо сложения используется дизьюнкция. Тогда легко видеть, что 1г,+г = 1г.. 1ь Утверждение. Пусьпь р — 12 . Тогда матрицу 1 моэгсно получить из матрицы 1п используя не. более 2рзт операций конвгонкции и дизеюнкции. Доказагпельсгпво. Будем последовательно вычислять матрицы 1г, г4, Х8, ...., 1г . возводя предыдущую матрицу в квадрат.

Возведение матрицы в квадрат (по обычному правилу: "строчка на столбец" ) требует не более 2рз операций кон ьюнкции и дизьюнкции. Доказываемое утверждение следует из того, чхо 1г = 1, поскольку р — 12". 3 2. Деревья Определение. Граф С = 11',Е) называется деревом, если он связный и не содержит циклов. Вершины степени 1 в дереве называют его листьями. Определение. Подграф С1 = ®,Е1) графа С = (1",Е) называется остовным деревом, если С1 ---- дерево и 1'1 = 1'. Теорема 2.1.

Любий (конечный) связный граф С = ~Ъ; Е) содерлсит хотя бы одно остовное дерево С1 = (1:, Е1). Доказательство. Если в С нет циклов, то положим С1 — — С. Если в С есть циклы, го удалим из С какое-нибудь ребро, входящее в цикл. Получится некоторый подграф С' . По лемме 1.3 С' — — связный граф. Если в С' нет циклов, то положим С1 = С', иначе продолжим этот процесс. Процесс должен завершиться, так как Е конечное множество.

Теорема 2.2. Пусть в дереве С имеется р вершин и о ребер. Тогда д = р — 1. Доказагпельство. Так как С связный граф и С не содержит циклов, то р — ц = 1 по лемме 1А. Отсюда о = р — 1. Понятие дерева можно определить различными способами, что вытекает из следующей теоремы. Теорема 2.3. Пустгь С = (1', Е) неориентированный граф без петель и кратных ребер, (1~) = р, )Е) = д. Тогда следующие 5 условий зквивс ентны: 1) С дерево; 2) С без циклов и д = р — 1; 3) С связный 'и д = р — 1; ф С -- связный, но при удалении любого ребра становится несвлзным; б) С -- без циклов, но при добавлении любого нового ребра на тех же вершинах появляетсл цикл.

Докозаэээельс)ээоо. ДОкажем следущие пе]эеходы 1) =-"~ ) ==.)" 3) =~Ф' 4) =Ф 5) =-~ 1), ОткуДН буДег слеДОВВТЬ, '1тО из лн)бОГО ус;!Овия Вьггекае'! любое другое. Переход 1) =~ 2) следует из теоремы 2.2. Пус"гь теперь выполняется 2). '1огда по лемме 1А в С число связных компонент равно !) — О = 1, чо ес)ь С вЂ” связный !риф. Огскэда следуе:г переход 2) =) 3). Переход 3) =~ 4) вытекает из следствия к лемче 1А. Пус! ь Вы!ю:1нясггся 4). Тогда, е1.,'1И бы Б С был цикл,:го п])н удалс!г!Ни люоого ребра из зт1)го цикла С остался бы связным, со!Гласно лс"мме 1.3.

Эт!э противоречило оы 4). Значит С пе имеет циклов. Вторая часть условия 5) Быте!сает„со!О)асно лемме 1.2. из того, что С связный. Таким образоч, получаем, что 4) =~ 5). Пусть Вьпнэлняется 5). Если п]эи ".этОм С не ОВязный Г]эаф и Ве]э1пины а, ю лежит В разных (.'Бязных компонентах графа С, то дооавление к С ребра 1'и, п)„очевидно, не порождиег циклов, что п]эо!Иворе)1!т О). О!сюда следует, ч)о С связный гриф„'1!э е1:гь 5) =-.,"» 1). Тео]эеме), доказана. Ъсловия 4) и 5) показывак)ч; чтс» множество всех де]эеньев з!О мнОжестВО 1гсех мин!и!аэ!ьнь)х свэ!зных Г]эафОВ и, Б ЗО же время, мнОжес.:1ВО В(и!х максимальных Г]эа(1)ОВ оез цик:1ОВ.

, ]лэ! представления данных в информацисэнных системах„в спраВОчниках, при реализации алГО]эи'ГМОВ НОиска и В д]эуГих п])илОжениях )асгсэ использукпся жоуэиевые деревья, то есть деревья с выделенной вершиной, именуемой корнем. Мы дадим следующее индуктивное определение корненого дерева. Определение. 1) Г]эаф„имеющий одну вершину !', которая вы~1елена. и не имен)щий ])ебе]э, являс)тся к()рневык! де]и'ВОМ с корнем 2) Пусть эг]1, эг]2,...,.О„„)зде Эи1 — корневые деревья с корнями с1,1)2....,о,„.

Пусть О; = ~1',;,Е;) и ]'';]]], = при )ф ]'. Пус-!.ь О ф 1:1 ! ! 12 0... 01',„. То )сда граф В = ~ 1', Е), где 1 = 1 ! ] ] ~ 2 ] ]... ]] 1; ] ]1 ! 1, .Е = Е1 0Е) ! ]...].)Е„„0~(г, е!),...,1О, !))„)) и Выделена вершина г, является корненым деревом с корнем г (см. рис. 2.1). При зтом В1, Вэ,...,.О,„ называются поддеревьями ко!эневого дерева И.

1;11 ХЬ В,„ Рис. 2.1. 3) Только хакие графы называются корневыми деревьями, которые могут быть построены по 1) и 2). Например, файловая структура в компьютере является корневым деревом. При этом корню соохветствует сам компьютер, вершинам второго яруса соответствухот диски А, В, С, 0 и т. д., вершинам третьего яруса соответствуют директории, вершинам следующих ярусов соответсгвуют поддиректории и файлы. Определение.

Упорядоченное корневое дерево это корневое дерево О., в котором задан порядок его поддеревьев х.11,.02,...,.О (можно считать, что числами 1,2,..., иь занумерованы ребра, выходящие из корня дерева Х)) и каждое П; --- само есть упорядоченное корневое дерево. Теорема 2.4. Число упорядоченных корневых деревьев е д ребрами не прееосходитп 44. Докизатпелъетпео. Рассмотрим важный для приложений способ обхода упорядоченного корневого дерева, который называют "по1лском в глубину".

Этот обход описывается рекурсивно следующим образом. 1) Начагь из корня дерева .0; 2) пока есть поддеревья, перейти по ребру в корень очередного поддерева, рекурсивно обойти эго поддерево 'в глубину', вернуться в корень исходного дерева. В результате обход "в глубину" проходих по каждому ребру дерева О ровно 2 раза: од1лн рвз при переходе в очередное поддерево, второй раз при возвращении из этого поддерева. В соответствии с обходом "в глубину" будем строить последовательность из О и 1, записывая на каждом шаге О ил14 1, причем О будем записывахь, если происходит переход в очередное поддерево, а 1, если мы возвращаемся 1лз поддерева.

Получим последовахельность из О и 1 длины 20, которую назовем кодом дерева П. По этому коду однозначно восстанавливается дерево .О, поскольку каждый очередной разряд однозначно указывает, начинать ли строить новое очередное поддерево или возвраща:гься на ярус ближе к корню. Таким образом, упорядоченных корневых деревьев с д ребрами не больше, чем последовательностей из О и 1 длины 2д. а их число равно 2~4 = 44.

Изоморф1изм корневых деревьев определяется так же, как изоморфизм обычных графов, но дополнительно требуется, чтобы корню одного дерева сопоставлялся при изоморфизме корень другого дерева. Для упорядоченных корневых деревьев дополнительно требуется, чтобы при изоморфизме сохранялась упорядоченность. Следствие. Число неизоморфных корневых деревьев с д ребрами и число неизоморфных обычных деревьев с д ребрами не превосходит ~~Ч Доказательство. Выделяя н неизоморфных деревьях по одной точке, мы получим неизоморфные корненые деревья. Упорядочиная поддеревья в неизоморфных корневых деревьях, мы получим различные упорядоченные корневые деревья.

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

Но это не единственные графы, обладающие этим свойством. Определение. Ориентированным ациклическим графом называется люоой ориентированный граф, н котором нет ориентированных циклон. Определение. Вершина ориентированного графа называется истоком (стпоком), если в нее не входит ни одна дуга, то есть а+(ь) = О, (соответственно, из нее не выходит ни одной дуги, то есть а (г) = О. Утверждение 1.1. В любом (конечном) ориентированном ици; клическом графе есть хогпя бы один исток и хотя бы один сток. Доказительство.

Выберем любую вершину и будем строить путь из нее, двигаясь произвольно по направлению дуг. При этом вершины не могут повторяться, так как н данном орграфе нет ориентированных циклон. Поэтому путь должен прийти в тупик, который и является стоком. Для получения истока надо аналогично строить путь, двигаясь против направления дуг. Определение. Глубиной вершины и н ориентированном ациклическом графе называется максимальная длина ориентированного пути из всех истоков н вершину и. Это определение корректно н силу утверждения 1.1. При этом глубина каждой вершины в ориентированном ациклическом графе не превосходит р — 1, где р — — число вершин в графе.

Утверждение 1.2. Пусть (и,и) дуга в ориентированном ачиклическом грифе. Тогда глубина вершины и больше, чем глубини 15 вершины и. Доказательство следует из того, что если из некоторого истока в вершину и существует ориентированный путь длины Й, то из того же истока в вершину и существует ориенгиронанный путь длины 1+1. 3 3. Планарные графы Пусть задан неориентированный граф С = (1', Е). Пусть каждой вершине с; из 1г сопоставлена точка а,; в некотором евклидовом пространстве, причем а; ф а при г ф 1. Пусть каждому ребру е = (ь;, и ) из Е сопоставлена непрерывная кривая Х, соединяющая точки а; и а; и не проходящая через другие точки а~.