Пример 2.5

На рис. 2.10. Приведен полный трехвершинный граф, каждая вершина которого является центром.

Эйлеровы циклы, цепи и графы

Эйлеровым циклом называется цикл, содержащий все ребра связного графа. Граф, имеющий эйлеровы циклы, называется эйлеровым. Цепь, содержащая все ребра связного графа, называется эйлеровой цепью.

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

Появление понятия "графы" обязано Эйлеру, постановка и решение задачи о кенигсбергских мостах которого положили начало разработке теории графов. Расположение мостов в г. Кенигсберге во времена Эйлера приведено на рис. 2.11,а.

Суть задачи в следующем. Требуется, начав из какой-либо части города, пройти все мосты по одному разу и вернуться в ту же часть.

Следуя за Эйлером, построим граф задачи, в котором каждой части города поставим в соответствие вершину, а каждому мосту, соединяющему их, – ребро инцидентное соответствующим вершинам (рис. 2.11,б). Получившийся граф является мультиграфом.

Рис.2.11. Иллюстрация задачи о кенигсбергских мостах

Теперь задача сводится к отысканию маршрута в заданном графе. Так как необходимо вернуться в ту же часть города, то этот маршрут должен быть замкнутым. А так как каждый мост нужно обязательно пройти и только один раз, то он должен быть циклом, содержащим все ребра графа.

Условия, которым должен удовлетворять граф, чтобы быть эйлеровым, даются теоремой Эйлера.

Теорема 2.1. (Эйлера). Конечный неориентированный граф G тогда и только тогда эйлеров, когда он связен и степени всех его вершин четны.

Необходимость. Пусть граф G имеет эйлеров цикл. Любой цикл в графе принадлежит своей компоненте связности, в данном случае существует цикл, содержащий все ребра графа, следовательно, граф состоит из одной компоненты, то есть он связен (случай с присутствием изолированных вершин не рассматриваем).

Каждое вхождение любой вершины в цикл графа G встречается с парой инцидентных ей ребер, а так как цикл эйлеров, то все ребра, инцидентные такой вершине, различны. Следовательно, звездный граф вершины, входящей в эйлеров цикл, содержит четное число ребер, то есть степень этой вершины четна. Необходимость доказана.

Достаточность. Пусть граф связен и степени всех его вершин четны. Так как в графе не существует изолированных и висячих вершин (со степенью, равной 1), то, выбирая в качестве начальной произвольную вершину v графа G и добавляя к ней все новые и новые ребра вместе с инцидентными им вершинами, на промежуточном этапе, будем иметь цепь, каждая вершина которой (за исключением начальной и конечной) инцидентна четному числу (возможно, равному 0) свободных (не вошедших в цепь) ребер.

Начальная и конечная вершины имеют нечетное число свободных ребер. Так как число вершин и их степени конечны, то, продолжая этот процесс, мы обязательно придем в вершину v, то есть в ту вершину, с которой начали построение цикла. Однако в построенный цикл могут не входить некоторые ребра, то есть он не обязательно будет эйлеровым. Иначе говоря, могут существовать вершины, принадлежащие циклу и инцидентные свободным ребрам. Отметим, что количество свободных ребер в каждой такой вершине будет четным. Пусть w – одна из таких вершин. Выберем ее в качестве начальной вершины и, используя свободные ребра, построим аналогично предыдущему новый цикл. Ясно, что объединение этих циклов даст нам цикл, содержащий большее количество ребер, чем предыдущий. Процесс продолжаем до тех пор, пока в цикле не останется вершин со свободными ребрами. Таким образом, эйлеров цикл будет построен и, следовательно, данный граф эйлеров.

В графе задачи о Кенигсбергских мостах (рис. 2.11, б)) все вершины имеют нечетную степень. Следовательно, ее решение невозможно.

Теорема 2.2. Для того чтобы связный граф G содержал эйлерову цепь, необходимо и достаточно, что бы он имел ровно две вершины нечетной степени.

Необходимость. Пусть G содержит эйлерову цепь, связывающую вершины v ¹ w. Тогда граф G È { v, w } является эйлеровым. По теореме Эйлера степени всех его вершин четны. Добавление ребра { v, w } к графу G увеличило степени вершин v, w на единицу, следовательно, в G все вершины имеют четные степени, кроме начальной и конечной вершин эйлеровой цепи, которые имеют нечетные степени.

Достаточность. Пусть G имеет ровно две вершины v и w нечетной степени. Тогда все вершины графа G È { v, w } имеют четную степень, то есть содержит эйлеров цикл. Следовательно, граф G содержит эйлерову цепь, связывающую вершины v и w.

Гамильтоновы циклы и цепи

Гамильтоновым циклом называется простой цикл, проходящий через все вершины рассматриваемого графа. Гамильтоновой цепью называется простая цепь, проходящая через все вершины рассматриваемого графа.

На первый взгляд может показаться, что понятия эйлерова цикла и гамильтонова цикла – это сходные понятия. Однако эти понятия независимы. В эйлеров цикл все ребра входят по одному разу, это требование приводит к тому, что и все вершины входят в цикл, причем число их вхождений непосредственно связано со степенями вершин. В гамильтонов цикл все вершины входят по одному разу, ребра же входят не все и тоже по одному разу. Таблица, приведенная на рис. 2.12, иллюстрирует независимость этих понятий.

С понятием гамильтонового цикла, как и с понятием эйлерова цикла, связаны исторические задачи. Например, задача о шахматном коне. В ней требуется, начав с некоторого поля шахматной доски, обойти конем все ее поля, посещая каждое из них не более одного раза, и вернуться в исходное поле.

Цикл в графе	Гамильтонов
Существует	Не существует
Эйлеров	Существует
Не существует

Рис.2.12. Графы, иллюстрирующие существование циклов Эйлера и Гамильтона

Задачу о шахматном коне (она также связана с именем Эйлера) можно расширить (обобщить), если задавать поле, с которого нужно начать обход доски и поле, в котором его требуется закончить.

Как и задача о кенигсбергских мостах, задача о шахматном коне может быть переведена на язык графов. Для этого поля доски будем считать вершинами графа, а возможные (допускаемые правилами) ходы коня – ребрами, инцидентными соответствующим вершинам. Если использовать принятые в шахматах обозначения, то множество V вершин (n = 64) этого графа будет V ={ a1, a2, …, h8 }, а множество E состоит из ребер: { a1, c2 }, { a1, b3 }, …, { g6, h8 }, { f7, h 8}.

Задача сводится к отысканию гамильтонового цикла или цепи. К этому графу мы вернемся в следующей теме.

Отметим, что нет столь же простых, как для эйлеровых циклов и цепей, необходимых и достаточных условий существования гамильтоновых циклов и цепей. Эти условия зависят от конкретных типов графов.

Приведем некоторые общие и простейшие соображения.

Гамильтоновы циклы и цепи относятся к специальным маршрутам. Если граф G n- вершинный и содержит гамильтонов цикл, то его длина равна n, а длина цепи равна: n – 1.

Простейшим достаточным условием существования гамильтоновых цепей и циклов является его полнота. То есть, если граф полный, то в нем существуют

гамильтоновы циклы, а любые две его вершины могут быть соединены гамильтоновой цепью. Действительно, перечислим в произвольном порядке все n вершин полного графа: . Любые рядом стоящие, а также первая и последняя вершины смежные (граф полный), то есть, инцидентны некоторому ребру. Следовательно, данная последовательность всех неповторяющихся вершин – гамильтонов цикл. Более того, любая перестановка вершин будет гамильтоновым циклом.

Очевидным необходимым условием существования гамильтоновых цепей и циклов является связность графа.

Более тонким необходимым условием существования гамильтонова цикла в графе G является утверждение 2.6.

Утверждение 2.6. Если граф G обладает гамильтоновым циклом, то в нем отсутствуют точки сочленения.

Доказательство. Пусть g = v₁ , v₂ , …, v_i-1 , v_i , v_i+1 ,…, v_n , v₁ – гамильтонов цикл в графе G, где n – число его вершин. Предположим, что вершина v_i является точкой сочленения. Рассмотрим граф – дополнение звездного графа G (v_i). Согласно определению точки сочленения дополнение состоит из компонент связности , k = 1, 2, …, p, где p ³ 2. Пусть вершина v_{i + 1} Î при некотором фиксированном k, тогда ребро { v_i+1, v_i+2 } также принадлежит этой компоненте связности, следовательно, вершина v_i+2 Î . Рассуждая аналогично, убеждаемся, что все вершины графа принадлежат одной и той же компоненте связности , это противоречит сделанному предположению о том, что существует точка сочленения в графе G.

Рассмотрим теперь некоторые наиболее простые методы выделения гамильтоновых цепей (а значит, и циклов) в графе G с множеством вершин V ={ v₁, v₂,…, v_n }. Самым простым, видимо, является метод перебора всевозможных перестановок множества V. Для каждой из них проверяем, является ли замкнутым маршрутом в G. Если является, то – гамильтонов цикл в G, в противном случае переходим к следующей перестановке. В результате такой работы будут выделены все гамильтоновы циклы. Аналогично могут быть выделены гамильтоновы цепи.

Учитывая, что число перестановок на множестве V = { v₁, v₂,…, v_n } равно n!, можно оценить объем этой работы. Данный алгоритм более эффективен для графов близких к полному графу, так как у последних любая перестановка дает положительный результат. Алгоритм перебора перестановок при выделении циклов может быть улучшен, если во множестве циклических перестановок проверять только одного представителя. Другое направление улучшения состоит в учете некоторой информации о структуре графа. В следующей теме мы вернемся к этому вопросу.

2.3. Дерево и лес

Ø Определение дерева и леса

Ø Свойства деревьев

Ø Цикломатическое число графа

Ø Центры деревьев

Ø Изоморфизм деревьев

Определение дерева и леса

Неориентированный граф T называется деревом, если он является связным и не имеет циклов. Иначе говоря, деревом называется связный ациклический граф. Граф, компонентами связности которого являются деревья, называется лесом (рис. 2.13).

Ясно, что ни псевдограф, ни мультиграф не могут быть деревьями. Любая часть леса или дерева не имеет циклов, то есть является лесом или поддеревом. Общее свойство "не иметь циклов" является посылкой для многих других свойств, которыми обладает множество (класс) графов, являющихся деревьями. Прежде чем перейти к изучению этих свойств, рассмотрим ряд утверждений, относящихся к связным графам.

Рис. 2.13. Дерево (а) и лес (б)

Вершина u графа T называется концевой, или висячей, если ее степень r(v) равна единице. Ребро, инцидентное концевой (висячей) вершине, называется концевым (висячим).

Утверждение 2.7. Пусть T – связный граф, u – концевая вершина в T, T¢ – подграф графа T, содержащий все его вершины и ребра кроме указанной концевой вершины u и инцидентного ей ребра e. Тогда T¢ – связный граф.

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

Доказательство. Предположим, что T¢ не является связным графом. Тогда в нем найдутся вершины v ¹ w, которые нельзя соединить маршрутом. Но в T их можно соединить некоторым маршрутом M (в силу связности T). Выделим из M цепь M¢, также соединяющую вершины v, w. Если цепь M¢ не проходит через вершину u, то она является цепью и в T¢, что противоречит предположению, а, следовательно, она проходит через u. Так как u концевая вершина, то цепь M¢ содержит участок …e, u, e,…, то есть, концевое ребро e встречается в цепи более одного раза, что противоречит определению цепи. Полученное противоречие показывает, что исходное предположение неверно, то есть T¢ – связный граф.

Утверждение 2.8. Пусть T¢ – граф, содержащий вершину w,граф R – граф, содержащий ребро e с инцидентными ему вершинами w и v Ï T¢. Тогда, T = T¢ È R – связный граф (рис. 2.14).

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

Рис.2.14. Добавление концевого ребра

Доказательство. Так как подграф T¢ – связный граф, то для доказательства связности графа T достаточно показать, что любую вершину u графа T¢ можно соединить маршрутом с v (поскольку ввиду связности графа T¢, отличные от v вершины, заведомо можно соединить маршрутом). Рассмотрим случай, когда u ¹ w. В силу связности T¢ существует маршрут h в T¢ (а, следовательно, и в T), соединяющий вершины u, w. Но тогда h o w, e, v – маршрут в T, соединяющий u, v. Утверждение доказано.

Свойства деревьев

Следующие высказывания попарно равносильны:

1) граф T есть дерево;

2) граф T является связным и не имеет простых циклов;

3) граф T является связным и число его ребер ровно на единицу меньше числа вершин;

4) Любые две различные вершины графа T можно соединить единственной (и притом простой) цепью;

5) граф T не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл (проходящий через добавляемое ребро).

Докажем эти равносильности.

Равносильность высказываний 1 и 2 вытекает из определения дерева и из утверждения о возможности выделения из любого замкнутого маршрута простого цикла.

Напомним, что граф называется связным, если для любых двух его вершин существует соединяющий их маршрут. В свою очередь, из маршрута может быть выделена цепь с тем же началом и концом, а из цепи – простая цепь. Отметим, что такая последовательность вовсе не обязательна, то есть из маршрута, не являющегося цепью, может быть выделена простая цепь. Более того, в связном графе могут найтись вершины, которые можно соединить лишь простой цепью. Если граф T – дерево, то таким свойством обладают все его вершины.

Лемма 2.1. Пусть T – дерево. Тогда любая цепь в T будет простой.

Доказательство. Пусть v₁ , v₂ ,…, v_k – цепь вдереве T, не являющаяся простой. Тогда в ней найдутся вершины v_i = v_j , где i ¹ j. Для определенности положим i < j. Участок рассматриваемой цепи v_i , v_i+1 , …_, v_j будет циклом, что противоречит тому, что T – дерево.

Теорема 2.3. Любые две различные вершины v и w дерева T связаны одной и только одной простой цепью.

Доказательство. Предположим противное. Пусть вершины v и w дерева T связаны различными цепями L₁ (v, w) и L₂ (v, w). Тогда композиция цепей L₁ (v, w) o L₂ (w, v) даст замкнутый маршрут, из которого может быть выделен простой цикл, чего не может быть в дереве. Следовательно, сделанное предположение не верно, то есть вершины v и w связаны одной и только одной (согласно лемме 2.1) простой цепью.

Следствие. Удаление любого ребра из дерева приводит к нарушению связности.

Теорема 2.4. Если любые две вершины v, w графаT связаны единственной цепью, то граф T – дерево.

Доказательство. Предположим противное. Пусть T не дерево. Тогда в T существует цикл, а, следовательно, и простой цикл. Выберем две различные вершины, инцидентные некоторому ребру { v, w } этого цикла. Тогда простые различные цепи L₁ (w, v) и L₂ (v, w) = { v, w } соединяют вершины v и w, что противоречит условию теоремы.

Теоремы 2.3 и 2.4 доказывают равносильность высказываний 1 и 4.

Лемма 2.2. Если дерево T конечно и имеет хотя бы одно ребро, то у него обязательно найдется концевая вершина.

Доказательство. Предположим, что в T нет концевой вершины. Построим маршрут с началом v₀ . Пусть v₀ , v₁ вершины инцидентные упомянутому в лемме ребру

e₁ . Поскольку это не концевые вершины, то в T найдется еще одно ребро e₂, инцидентное вершинам v₁ , v₂, затем v₂, v₃ и так далее, v_i-1, v_i …. Этот процесс в виду сделанных предположений и конечности графа T обязательно закончится тем, что для некоторого i вершина v_i уже ранее встречалась в построенном маршруте. Иначе говоря, построенный маршрут содержит цикл, а вместе с ними дерево T содержит цикл, что противоречит определению дерева.

Теорема 2.5. Пусть T – дерево с n вершинами и m ребрами. Тогда m = n – 1.

Доказательство проведем индукцией по m – количеству ребер. Граф, состоящий из одной вершины (m = 0, n = 1), очевидно, будет деревом. Пусть m = 1. Каждое ребро в графе может быть инцидентно только двум вершинам. T – дерево (связный граф), поэтому изолированных вершин нет, следовательно, m = n – 1.

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

Докажем это утверждение, если число ребер в дереве T равно m. Согласно лемме 2.2 в T имеется хотя бы одна концевая вершина. Согласно утверждению 2.7 подграф T¢ графа T без этой вершины и ребра является связным графом. Кроме того, T¢ не содержит циклов (если бы T¢ содержал циклы, то и исходный граф T их бы содержал), то есть T¢ – дерево, причем содержащее m – 1 ребро. Согласно индуктивному предположению количество ребер и вершин графа T¢ удовлетворяют соотношению m – 1 = n – 2. Так как в графе T на одно ребро и на одну вершину больше, то для его ребер и вершин справедливо: m = n – 1.

Лемма 2.3. Если в условии утверждения 2.8 граф T¢ – дерево, то граф T тоже дерево.

Доказательство. Если в T найдется хотя бы один замкнутый маршрут M, то он обязательно содержит концевую вершину v (поскольку в T¢ циклов нет). Так как v – концевая вершина, смежная вершине w, то M содержит участок w, e, v, e, w (возможно, входящий в него несколько раз). Следовательно, из маршрута M может быть выделен замкнутый маршрут M¢, который будет также принадлежать графу T¢, что противоречит тому, что он – дерево.

Теорема 2.6. Пусть T – связный граф с m ребрами и с n вершинами и пусть также выполняется равенство m = n – 1. Тогда T – дерево.

Доказательство проведем индукцией по n – количеству вершин (в отличие от доказательства теоремы 2.5).

Если n = 1, то m = n – 1 = 0. Граф, содержащий одну вершину и не имеющий ребер, очевидно, является деревом.

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

Докажем справедливость этого утверждения для любого графа T с n вершинами. Покажем, что в T имеется концевая вершина. Если ее нет, то степень любой вершины
v Î T r (v)³ 2. Следовательно, используя известное соотношение , имеем: , откуда m ³ n, а это противоречит условию, что m = n – 1. Таким образом, в графе T имеется концевая вершина v.

Рассмотрим наибольший подграф T¢ графа T, не содержащий вершину v вместе с инцидентным ей ребром, то есть с n – 1 вершиной и n – 2 ребрами. Согласно утверждению 2.7 граф T¢ является связным, а, следовательно, по индуктивному предположению T¢ – дерево. Но тогда в силу леммы 2.3 граф T является деревом.

Теоремы 2.5 и 2.6 устанавливают равносильность высказываний 1 и 3.

Теорема 2.7. Для того чтобы граф T являлся деревом необходимо и достаточно, чтобы добавление к нему одного ребра с концевыми вершинами из T приводило бы к появлению ровно одного простого цикла, содержащего это ребро.

Необходимость. Пусть T – дерево. Тогда в T нет циклов. Пусть R некоторый граф с единственным ребром e, не принадлежащим T и инцидентным вершинам v, w Î T. Рассмотрим граф T¢ = T È R. Используя теорему 2.3, получаем, что в T найдется простая цепь h₁, соединяющая вершины v, w. Но тогда m₁ = w, e, v o h₁ – простой цикл. Покажем, что он единственен. Предположим противное. Пусть m₂ – еще один простой цикл в T¢. Тогда он обязательно должен содержать ребро e, в противном случае в T существует цикл, то есть T не является деревом, а это противоречит условию. Следовательно, m₂ = w, e, v o h₂ (или v, e, w o h₂), где h₂ – простая цепь, соединяющая вершины v, w. Но тогда в силу теоремы 2.3 h₂ = h₁, следовательно, m₂ = m₁.

Достаточность. Пусть граф T не имеет циклов и пусть, добавляя к нему новое ребро, получаем ровно один простой цикл, проходящий через это ребро, и, тем не менее, граф T не является деревом. Так как T не имеет циклов и не является деревом, то он несвязен, то есть найдутся в T вершины v, w, которые нельзя соединить простой цепью. Добавим к графу T ребро e, инцидентное этим вершинам, получим граф T¢. По условию теоремы 2.7 добавление ребра к T должно привести к появлению в T¢ простого цикла m. Этот цикл обязательно пройдет через добавленное ребро, иначе существовал бы цикл и в T. Тогда справедлива композиция: m = w, e, v o h, где h – простая цепь, целиком лежащая в T и соединяющая вершины v, w. Это доказывает то, что граф T связен, а так как он не имеет циклов, то T – дерево.

Теорема 2.7 устанавливает равносильность высказываний 1, 5. Таким образом, все равносильности доказаны.

Цикломатическое число графа

Пусть дан связный граф G, и пусть число его вершин равно n (G), а число ребер – m (G). Напомним, что подграф H графа G называется суграфом, если n (H) = n (G). Число ребер различных суграфов может быть различным. Очевидно, что оно лежит в пределах 0 £ m (H) £ m (G). То есть суграф не обязательно должен быть связным.

Покрывающим суграфом связного графа называется суграф, каждая вершина которого инцидентна хотя бы одному ребру из Н. Рассмотрим множество S всех связных покрывающих суграфов связного графа G.

Теорема 2.8. Минимальный по числу ребер связный суграф, покрывающий вершины связного графа G, представляет собой дерево.

Доказательство. Покажем, что если G не является деревом, то существует отличный от G связный покрывающий суграф. Действительно, пусть G – не дерево. Тогда он содержит хотя бы один цикл (без нарушения общности можно считать, что это простой цикл). Удалим любое ребро, входящее в цикл, при этом связность оставшейся части H графа G не нарушится, так как существует маршрут (участок упомянутого цикла), соединяющий вершины, инцидентные удаленному ребру, следовательно, существуют и ребра, инцидентные каждой из этих вершин. Таким образом, H есть связный покрывающий суграф (иначе, связный подграф графа G).

Пусть G¹ – связный покрывающий суграф, полученный на первом шаге. Если G¹ содержит циклы, то, повторив предыдущую процедуру, получим связный покрывающий суграф G² и так далее. Так как число ребер конечное, то этот процесс остановится на некотором шаге l (заметим, что удалено ровно l ребер). В результате, мы имеем подграф G^l, который, во-первых, не содержит циклов (в противном случае мы могли бы продолжить данную процедуру), во-вторых, он связен, так как удалялись ребра, принадлежащие циклам. Следовательно, граф G^l – связный покрывающий суграф, являющийся деревом. Этот суграф будет минимальным, поскольку удаление любого ребра из дерева приводит к нарушению связности.

Таким образом, у любого связного графа G существует связный минимальный покрывающий суграф. Если G – дерево, то оно одновременно является и упомянутым суграфом.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Согласно теореме 2.8, остовное дерево графа G и его связный минимальный покрывающий суграф – это эквивалентные понятия.

Пусть G – связный граф. В силу теорем 2.5 и 2.8 справедливо соотношение:
m (G) – l (G) = n (G) – 1, где l (G) – число удаленных ребер. Тогда

l (G) = 1 + m (G) – n (G).(_*)

Число l (G), определяемое для связного графа G формулой (_*), называется цикломатическим числом связного графа.

Для произвольного графа цикломатическое число определяется суммой цикломатических чисел его связных компонент. Следовательно, оно вычисляется по формуле:

l (G) = p (G) + m (G) – n (G), (_**)

где p (G) – число связных компонент графа G.

Итак, если граф G – дерево, то его цикломатическое число: l(G) = 0. Если G – лес, то также l (G) = 0, так как связными компонентами леса являются деревья.

Цикломатическое число произвольного связного графа G всегда больше или равно (в случае дерева) нулю, оно показывает: сколько требуется удалить из G ребер, чтобы получить остовное дерево связного графа G.

Центры деревьев

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

Пусть T – дерево, V – множество его вершин ,| V | ³ 3. Всем его концевым вершинам припишем уровень, равный 1, и пусть они образуют множество V₁ Ì V. Удалим эти вершины вместе с инцидентными им концевыми ребрами. В результате, согласно утверждению 2.7, получим связный граф T¹, являющийся поддеревом с множеством вершин V \ V₁. Если T¹ состоит не менее чем из трех вершин, припишем его концевым вершинам уровень, равный 2, и так далее. Пусть k – наименьшее число, для которого множество V_k = V \ содержит менее 3 вершин. Тогда удаляя концевые вершины уровня k - 1 (множество – V_k-1) при k ³ 2, мы получим подграф T^{k - 1} графа T, который либо состоит из одной вершины (отсутствуют ребра), которой естественно приписать уровень k, либо содержит ребро, инцидентное двум вершинам уровня k (две концевые вершины).

Из определения уровней вершин дерева непосредственно следует, что (приведем без доказательства):

· если дерево - конечно, то у него обязательно найдутся (одна или две, но не более) вершины максимального уровня;

· совокупность множеств V₁, V₂,…, V_k образует разбиение множества вершин дерева T;

· отношение принадлежности вершин дерева T определенному уровню является отношением эквивалентности на множестве вершин T;

· всякая вершина u уровня i, где 1 < i < k имеет ровно одну смежную вершину более высокого уровня и хотя бы одну смежную вершину более низкого уровня (при i = 1 справедливо только первое, при i = k справедливо только второе);

· смежные вершины могут принадлежать одному уровню только в том случае, если он наибольший;

· всякая цепь, соединяющая две вершины одного уровня, проходит через вершину более высокого уровня;

· уровень вершин, входящих в цепь, при последовательном перечислении их от начала к концу либо только возрастает, либо только убывает, либо возрастает, а затем убывает. Если цепь проходит через обе вершины наибольшего уровня, то имеется участок постоянства уровня.

Напомним, что центрами графа называются вершины, удовлетворяющие соотношению:

,

где – максимальное удаление в T от вершины v.

Теорема 2.9. Центрами дерева являются вершины наибольшего уровня, и только они.

Доказательство. Пусть T – дерево и v – вершина наибольшего уровня, тогда максимальное удаление r (v) = d (v, u*), где u* принадлежит к множеству вершин 1 уровня, причем цепь L (v, u*) содержит одну и только одну вершину каждого уровня, отличного от наибольшего, и все вершины наибольшего уровня. Поэтому при наибольшем уровне, равном k, имеем: r (v) = k – 1, если вершина v единственна, и r (v) = k, если имеется еще одна вершина наибольшего уровня. В первом случае существует еще хотя бы одна цепь L (v, u**) длины k – 1, такая, что композиция L (u*, v)o L (v, u**) является тоже цепью.

Из этих рассуждений следует, что максимальное удаление любой другой вершины будет больше, чем r (v). Действительно, для любой вершин w, уровень которой меньше k,всегда найдется цепь, проходящая через вершину v, длина которой будет больше r (v). Таким образом, для любой вершины w имеем: r (w) ³ r (v), где v вершинанаибольшего уровня. Равенство достигается тогда и только тогда, когда w – вершина наибольшего уровня, если такая имеется. Следовательно, r (T) = r (v), если только v – вершина наибольшего уровня дерева T.

Дерево называется центральным, если оно имеет один центр, и – бицентральным, если – два центра.

Следствие из теоремы 2.9. Диаметральные цепи проходят через центр (центры) дерева T. Причем d (T)= 2k - 2, если T – центральное дерево, и d (T) = 2k – 1, если оно бицентральное.

Доказательство. Пусть T – центральное дерево, L (v^k, v¹) и L (v^k, u¹) – радиальные цепи, такие, что L (v¹, u¹) = L (v¹, v^k) o L (v^k, u¹) – цепь (такие цепи обязательно найдутся), верхний индекс вершин показывает их уровень. Длина этой цепи, очевидно, будет равна 2 (k – 1) = 2k – 2. Представим рассматриваемую цепь в виде (ребра в записи цепи опущены): L (v¹, u¹) = v¹, v², …, v^k-1, v^k, u^k-1, …, u¹. Ясно, что любая другая цепь будет иметь равное либо меньшее количество вершин, чем данная, а, следовательно, и ребер, т.е. представленная цепь является диаметральной.

Пусть теперь T – бицентральное дерево. Цепь L (v¹, u¹) = L (v¹, v^k) o { v^k, u^k }o L (v^k, u¹), где u^k вторая вершина наибольшего уровня, а цепи L (v^k, u¹) и L (v¹, v^k) получены из радиальных путем удаления в каждой из них ребра { v^k, u^k }, имеет вид: L (v¹, u¹) = v¹, v², …, v^k-1, v^k, u^k, u^k-1, …, u¹. Рассуждая аналогично предыдущему, убеждаемся, что эта цепь является диаметральной и имеет длину: 2k – 1.

Изоморфизм деревьев

Можно ожидать, что проблема изоморфизма графов (см. раздел 2.1), для деревьев должна решаться с помощью более эффективных алгоритмов, чем основанных на простом переборе. Одним из таких, достаточно эффективных алгоритмов, является алгоритм Дж. Эдмондса, который основан на понятии уровней вершин дерева. Рассмотрим процедуру кортежирования, однозначно ставящую в соответствие каждой вершине дерева T кортеж – натуральное число, являющееся конечным словом во множестве (алфавите) натуральных чисел, на котором обычным образом заданы операция "приписывания" и отношение ³.

v-поддеревом дерева T называется часть суграфа T \ e, содержащая вершину v, уровень которой меньше или равен уровню второй инцидентной ребру e вершине. В том случае, когда дерево центральное и вершина v – ценр, v -поддеревом называется само центральное дерево.

Обозначим через k (v) кортеж вершины v.

Кортежем вершины v называется натуральное число (слово)
k (v) = k₀ (v) k (v₁) k (v₂)… k (v_p), где k₀ (v) – число вершин в v -поддереве дерева T;
k (v₁), k (v₂) ,…, k (v_p) – кортежи инцидентных вершине v вершин в v -поддереве, удовлетворяющие условию: k (v₁)³ k (v₂) ³ … ³ k (v_p).

Замечание. Если вершина v – концевая, то ее v -поддерево состоит из одной вершины v, поэтому ее кортеж: k (v) = k₀ (v) = 1. Таким образом, кортеж любой концевой вершины равен 1.

---

Дата добавления: 2015-07-20