2.5 Деревья

Сделаем сначала несколько замечаний.

1. Пусть х - некоторая вершина графа О = (V. Е) и И' множество всех вершин связной компоненты С, содержащей х. Тогда

11' = {у € V: О содержит маршрут Аху}.

2. Граф С = (V, Е) является двудольным тогда и только тогда, когда он не содержит нечетных циклов. Действительно, если С - двудольный граф и V = V') и 1-2- где 11 П 1*2 = 0, то для любого цикла х\х2 ■ ■ ■ хе имеем х\ £ 11 (например), х-) £ 12 - •'':>, € V-! и т.д.. Так как х2 £ У2: то е - четное число. Обратно, пусть С не содержит нечетных циклов. Заметим, что С -двудольный граф тогда и только тогда, когда все его связные компонентыявляются двудольными, т.е. мы можем считать, что С - связный граф. Пусть х £ V. Пусть 1| = {у € V; минимальная длина <1(х. у) пути Л является нечетной } и 1-2 = V \ I '). Если какие-нибудь вершины из Ц,, г = 1,2, соединены ребром, то С содержит нечетный цикл.

Определение. Граф, не содержащий циклов, называется лесом или ациклическим графом. Связный лес называется деревом.

Примеры деревьев:

Ясно, что лес является объединением непересекающихся деревьев.

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

ДОКАЗАТЕЛЬСТВО. Действительно, если С не является деревом и х\... хе - цикл, то л; |.7 -2 • • • и {х \. х,.} - два пути Л.Г|..Г(. Обратно, пусть С - дерево и

два пути Л.Г|..Г(. Пусть у + 1    минимальный индекс такой, что

ф ;</;_ 1 (т.е. ;/;| = у/|.....= у//) и / минимальное число такое, что 3 >г и уу+1 - вершина Р\, скажем у^+\ = хт. Тогда

 

Р1 = ХоХ\ . . . X е 1

Р2 = х0у1... укхе

 

У4+1    р2 Уз и х^х%-\-\ • • • х^лУу ' ' ' Уъ+1    цикл С Противоречие.

Утверждение 7.   Следующие утверждения эквивалентны для графа

С:

а) С - дерево;

б) С - минимальный связный граф, т.е. С - связный граф и для любого ребра {а, 6} £ Е(С) граф С \ {а, 6} является несвязным (другими словами, каждое ребро является мостом);

в) С - максимальный ациклический граф, т.е. С - ациклический граф и если ж, у - несмежные вершины С, то С + {ж, у} содержит цикл.

ДОКАЗАТЕЛЬСТВО, а) => б). Пусть С - дерево и {ж. у} £ Е(С). Граф С \ {ж, у} не содержит Ахл пути хх\... гку: т.к. иначе С содержит цикл. Таким образом, С\ {х, у} - несвязный граф. Докажем, что б) =>■ в). Пусть С - минимальный связный граф и хх\... гку - цикл в нем. Тогда С \ {ж, у} - связный граф, т.к. в любом пути Ащг1 ребро {х, у} заменяется на путь хх\... гку. Противоречие. Т.е. С - дерево. Если а, Ь - две несмежные вер­шины его, то существует путь ах\... гф в С. Следовательно, граф С+{а, 6} содержит цикл ах\... гф. Это доказывает, что С - максимальный ацикли­ческий граф. Докажем, что в) =>■ а). Предположим, что С - несвязный граф и а, Ь - вершины его, принадлежащие разным компонентам связно­сти. Рассмотрим граф С + {а, Ь}. Он должен содержать цикл ах\... гф. Но это означает, что С содержит Аа_р путь. Противоречие.

Утверждение 8. Каждый конечный связный граф С содержит дерево, содержащее все вершины графа.

ДОКАЗАТЕЛЬСТВО. Пусть п = \С\ порядок графа С и х £ У {О). Положим Т\ - подграф, состоящий из одной вершины х. Предположим, что мы построили цепь деревьев

г, с т; С • • • С 7), С С

такую, что |7}| = /. Если к < п, то, ввиду связности, существует вершина у £ У {С) \ 1(7},). инцидентная некоторой вершине г £ 1(7},). Пусть 7},_ | -подграф, полученный из 7}, присоединением этой вершины г и ребра {у, г}.

Тогда 7},_ | является снова связным графом, в котором ребро {у} г} не явля­ется ребром никакого цикла, т.е. 7},_| - ациклический граф. Продолжая этот процесс, мы построим искомое дерево Тп.

Следствие 1. Пусть С - дерево порядка п. Тогда \Е(С) \ = п — 1.

ДОКАЗАТЕЛЬСТВО. Действительно, из утверждения 8 следует, что С содержит подграф, являющийся деревом, и в котором \Е{Тп)\ = п — 1. Если С ф Т„. то получаем противоречие с утверждением 7 (точнее, с минимальностью связного графа С).

Следствие 2. Пусть С - лес порядка п, имеющий к связных компо­нент. Тогда \Е(0) \ = (п — к).

Доказательство следует из следствия 1.

Следствие 3. Пусть С - дерево порядка п > 2. Тогда С содержит (по меньшей мере) две вершины степени 1.

ДОКАЗАТЕЛЬСТВО. Действительно, пусть <1\ < (1-> <■■■< (1„ неубы­вающая последовательность степеней вершин дерева С Допустим против­ное. Тогда (12>2и 2|#(<3)| = 2(п - 1) = о!г + о!2 + • • • + о!п > 1 + 2(п - 1). Противоречие.

Вернемся к предложению 8. Из него следует, что в любом связном графе (порядка п) есть дерево, содержащее все вершины графа. Оно называется основным (каркасным) деревом графа. Вернемся еще раз к построению этого остова. Если исходный граф С не содержит циклов, то он сам и является деревом. Иначе, возьмем любой цикл и удалим любое ребро из него. Мы не нарушим связность этого нового графа, но уменьшим в нем число циклов. Продолжая этот алгоритм, мы получим остовное дерево гра­фа. Число удаленных ребер при применении этого алгоритма называется циклическим рангом (или цикломатическим числом) графа С и обознача­ется через 7((2). Ясно, что 7(С) = т — п + 1, где т = \Е(0)\,п = Применяя этот алгоритм к произвольному (не обязательно связному гра­фу С), мы получим остовное дерево, циклический ранг 7(С) которого ра­вен 7(С) = \Е(С)\ — \0\ + к. где А* - число связных компонент. Число х(С) = |С| — к (число ребер в остовном лесе) называется коциклическим рангом.

Задача 22. Найти число всех неизоморфных деревьев Т порядка п, где п < 7.

ОТВЕТ: а) при п = 6 их число равно 6; б) при п = 7 их число равно 11.

Задача 23. Доказать, что каждое дерево является двудольным графом. Какие деревья являются полными двудольными графами?

УКАЗАНИЕ. Воспользоваться замечанием 2 в начале 2.5.

Задача 24. Найти циклические и ко циклические ранги графов Кп, Кгщги Еп, ]¥п, Платоновых графов, графа Петерсена.

Задача 25. Пусть С - граф порядка п. Доказать эквивалентность сле­дующих утверждений:

1) С - дерево;

2) С - связный и \Е(С)\ =гг—1;

3) С - ациклический и || = п — 1;

4) если п = 1 или 2, то С = /\'"; если /у > 3. то С ф К" и добавление одного ребра к С приводит к появлению ровно одного цикла.

УКАЗАНИЕ. Импликация 1) =>- 2) следует из определения и следствия 1. Импликация 2) =>- 3) следует из утверждения 8. Импликация 3) =>- 4) при п < 2 очевидна. Если же п > 3, то ясно, что С ф Кп. Докажем, что С - связный граф. Иначе, каждая из его к связных компонент является деревом и \Е(С)\ = п — к = п — 1. Т.к. к = 1. Остальное следует из утверждения 7.

Конечный граф С = (V, Е) порядка п назовем помеченным, если все его вершины "помечены" целыми числами от 1 до тг, т.е. существует биекция <р : {/'с • • • • <'/(} —> {1.2..... /у}. Числа -р{г\)..... (р(уп) называются метка­ми вершин г>1,..., уп. Два помеченных графа (6?1, (р\) и (6?2, уг) называются изоморными, если существует изоморфизм между нашими графами, кото­рый сохраняет распределение меток.

Приведем примеры всех помеченных неизоморфных деревьев порядка 2, 3, 4:

а) п = 2

•-• Их число равно 1.

1 2

б) п = 3

 

 

•—

 

-•-

 

—•

•—

-•-

—•

•—

 

-•-

—•

 

 

 

 

1

 

2

 

3

1

3

2

2

 

1

3

 

 

в)

п =

4

 

 

 

 

Их

число равно 3.

 

 

 

 

 

 

 

1

2

3

4

 

1

2

4

3 1

3

2

4

1

3

4

2

2

1

3

4

 

2

1

4

3 2

3

1

4

2

3

4

1

2

4

1

3

 

2

4

3

1 3

1

2

4

3

2

1

4

г ^

 

 

 

 

г\

 

 

/3 і\

 

 

 

г\

 

 

 

 

 

 

 

 

 

 

 

 

 

"3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Их число равно 16.

Теорема 6.(А.Кэли, 1889)

Число различных помеченных деревьев порядка п равно пп^2.

ИСТОРИЧЕСКАЯ СПРАВКА. Артур Кэли (1821-1895) - английский математик; известен исследованиями в теории групп и в теории колец (чи­сла Кэли); автор работ по теории определителей (в частности, ввел в рас­смотрение ныне действующее обозначение для определителя), по геометрии Лобачевского (модель Кэли-Клейна), по теории инвариантов и дифферен­циальным уравнениям.

ДОКАЗАТЕЛЬСТВО. Пусть Т(п, к) - число помеченных деревьев по­рядка гг, в которых фиксированная вершина у имеет степень к. Докажемравенство (*):

(п -1)(к- 1)Т(п, к) = (п- к)Т(п} к - 1).

Возьмем, сначала, любое помеченное дерево А порядка гг, в котором р(у) = к — 1. Возьмем в нем любое ребро {гп, г}, не инцидентное у, и удалим

Из предыдущего следует, что удаленное ребро являлось мостом. Соеди­ним вершину у новым ребром с вершиной г из другой связной компоненты. Тогда получим снова дерево В, в котором р(у) = к. Такую пару (А, В) мы будем называть связкой. Сколько таких связок? Дерево А можно выбрать Т(п, к — 1) способами. Для каждого дерева А удаляемое из него ребро {гп, г} можно выбрать (п — 1) — (к — 1) = п — к способами. Следовательно, число всех таких связок равно (п — к)Т(п,к — 1). Возьмем теперь любое помеченное дерево В порядка п, в котором р(у) = к. Пусть Т\.Т->..... 7), - поддеревья, полученные из В удалением вершины у с каждым из инци­дентных ей ребер.

Удаляя, например, ребро {у}ш\} и соединяя гш\ ребром с любой вер­шиной любого из оставшихся деревьев, мы получим дерево А, в котором

p(v) = к — 1. Т.е. получается связка (А, В) (и все связки получаются та­ким образом!). Подсчитаем другим способом число этих связок. Дерево В можно выбрать Т(п, к) способами. Для каждого такого выбора ребро

{w\,u} можно получить (тг2 + пз Ч-----Ь щ) = (п — п\ — 1) способами; ребро

{w2,u} можно получить (п — П2 — 1) способами и т.д. Т.е. ребра {wi,u} можно получить (п — п\ — 1 + гг — п2 — 1 + ■ ■ ■ + п — щ — 1) = = пк — к — (п — 1) = (п — 1)(к — 1) способами (мы использовали равенство /71 +1)2 Н— • + ///, = г/ — 1. где /// - порядок дерева 7). / < к). Следовательно, число всех связок равно (п —1)(к — 1)Т(п, к), и формула (*) доказана. Так как Т(п, п — 1) = 1, то из (*) следует равенство

T(n,k) = C*ll-(n-l)n^\

Число Т(п) всех помеченных деревьев порядка п равно

п—1

Т(п) = Т(п, 1) + Т(п, 2) + • • • + Т(п, n-l)=J2 Cnll ■ (п - lf^k =

k=l

= ((п — 1) + l)"^2 = r/"^2. Теорема доказана.

Задача 26. Найти цикломатическое число полного графа.

Задача 27. Пусть /7 > 3. Доказать, что если полный граф К" разложим в объединение гамильтоновых циклов (не имеющих общих ребер), то п -нечетное число.

УКАЗАНИЕ. Граф Кп является однородным степени (п — 1). Каждый гамильтоновый цикл является 2-однородным. Следовательно, 21 (п — 1) и /7 - нечетное число. Так как число всех ребер \Е(Кп)\ = п^п~^; То в этом объединении будет (п — 1)/2 циклов.

Задача 28. Пусть п - нечетное целое число > 3. Доказать, что К" является объединением (п — 1)/2 гамильтоновых циклов (любые два из которых не имеют общих ребер).

Задача 29. Полный граф Кп(п > 2) разложим в объединение гамильто­новых путей (любые два из которых не имеют общих ребер) тогда и только тогда, когда п - четное число.

Примеры:

а) К6 является объединением следующих гамильтоновых путей:

 

б) К4 является объединением таких гамильтоновых путей

 

УКАЗАНИЕ. Если п - нечетное число, то с каждым гамильтоновым пу­тем графа Кп^1 можно связать гамильтонов цикл Кп (присоединяя остав­шуюся вершину) и наоборот.

Задача 30. Доказать, что в связном конечном графе С = (V. Е). не являющимся деревом, каждой вершине можно поставить в соответствие смежное с ней ребро, т.е. существует инъективное отображение (р : V Ч> Е такое, что для любой вершины у £ V существует вершина и £ V такая, что <р(у) = {у,и}.

Иллюстрацией к этой задаче может служить пример города, в котором каждая улица имеет длину в один квартал, каждый перекресток (называ­ется площадью) имеет название и из каждой площади исходит улица с тем же названием. Например, из площади Советов исходит улица Советская и т.д.

УКАЗАНИЕ. Если п = \С\ = \У\, то \Е\ > п (иначе, С - дерево).

Рассмотрим схему превращения С в дерево. Схема состоит из последова­тельного удаления ребер. Пусть е = (а, Ь) - одно из таких удаляемых ребер и Т - полученное в результате удаления дерево. Каждой вершине дерева Т (кроме а\) поставим в соответствие смежное с ней ребро (это легко видеть,если принять а за корень дерева), а вершине а поставим в соответствие удаленное ребро е = (а, Ь).

Задача 31. Пусть Є = (V. Е) - связный конечный граф. Существует инъективное отображение <р : Е —>• V такое, что для любого ребра е Є Е вершина <р(е) инцидентна е тогда и только тогда, когда С - дерево или С - цикл с деревьями, вырастающими из его вершин (см. рисунок).

 

УКАЗАНИЕ. Если С - дерево и <7() его корень, то рассмотреть ото­бражение {ао:а\} —>• аь{асьа2} —>• Я2,{а1,аз} ^ аз и Т-Д- Если С - цикл 0,10,2... ап-\, то поставим в соответствие ребрам {а^,^} —>• а^,г < п — 1 и {ап_1,а1} —>• аь Итак, ясно, что если граф имеет указанный в усло­вии задачи вид, то искомое отображение существует. Обратно, если та­кое отображение существует и С = а\а2 ... ап^\ - цикл С, то, например, 1р({а1,а2}) = а2; и тогда 1р({а2,аз}) = аз и т.д. . Таким образом, <р(С) = = {^1,02,^35 • • • ^п-г}- Пусть Ь\ £ V инцидентна а\. Тогда (^({01,61}) = Ъ\ и а\ - корень некоторого дерева, вырастающего из а\. Аналогичные рассу­ждения относительно вершин а2:..., ап^\ приведут к решению задачи.