Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2. Деревья, разрезающие множества и циклы

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

2.1. Деревья, остовы и кодеревья

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

Деревом графа G называется связный ациклический подграф графа G. Остов графа G — это дерево графа G, содержащее все вершины G. Связный подграф дерева Т называется поддеревом Т. В качестве примера рассмотрим граф G, изображенный на рис. 2.1, а.

Графы (рис. 2.1, б) являются деревьями графа G, графы (рис. 2.1, в) — остовами графа

Кодерево Т остова Т графа G является подграфом графа G, содержащего все вершины G и только те ребра G, которые не входят в Т. Следует отметить, что кодерево может быть несвязным. Кодеревья G4 остовов (рис. 2.1, в) представлены на рис. 2.1, г. Ребра остова Т называются ветвями Т, а ребра соответствующего кодерева Т — хордами или связями.

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

Теорема 2.1. Для графа 0, имеющего вершин и m ребер, следующие утверждения эквивалентны:

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

Доказательство.

. См. упражнение 1.2, б.

(см. скан)

Рис. 2.1. Деревья, остовы и кодеревья. а — граф G; б — деревья графа G; в — остовы графа G; г — кодеревья и графа

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

Рассмотрим произвольное ребро . Это ребро составляет единственный путь между своими концевыми вершинами. Следовательно, в не существует пути между этими вершинами. Поэтому несвязный граф. Далее, он должен содержать точно две компоненты, иначе граф G не будет связным. Пусть компоненты Пусть число вершин и ребер в соответственно. И пусть аналогично определены для . Тогда имеем Отметим, что удовлетворяют предположению индукции, т. е. что существует только один путь между двумя любыми вершинами в . Так как , то имеем по индуктивному предположению . Следовательно,

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

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

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

. Пусть -компоненты графа — число вершин и ребер в компоненте - соответственно. Тогда Каждая компонента - является связным, а также ациклическим графом, поскольку этим свойством обладает граф G. Поэтому G; является деревом. Далее, по утверждению 3 данной теоремы для любого 1

Поэтому имеем однако по предположению

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

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

Очевидно, что утверждения 1—5 в изложенной выше теореме представляют собой множество необходимых и достаточных условий для того, чтобы граф G был деревом.

Прямым следствием этой теоремы является следующее утверждение:

Следствие 2.1.1. Рассмотрим подграф G графа G на вершинах. Пусть G имеет вершин и ребер. Тогда следующие утверждения эквивалентны:

1. G является остовом G. 2. Существует единственный путь между двумя любыми вершинами в G. 3. G является связным, и является ациклическим, и Если G является ациклическим и любые две несмежные вершины G соединить ребром, то получающийся граф имеет точно один цикл. Сформулируем условие, которое не перекрывается предыдущим следствием, но доказывается проще:

Следствие 2.1.2. Подграф G графа G на вершинах является остовом графа G тогда и только тогда, когда ациклический, связный и имеет ребер.

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

Тогда возникает вопрос: достаточно ли двух из четырех перечисленных свойств, чтобы определить остов? На этот вопрос мы ответим позднее (см. также упражнение 2.3).

Теорема 2.2. Подграф графа G на вершинах является остовом G тогда и только тогда, когда G является ациклическим и имеет ребер.

Доказательство. Необходимость следует из утверждения 4 теоремы 2.1. Чтобы доказать достаточность, необходимо показать, что G — связный граф и содержит вершин G. Пусть G состоит из компонент, причем — число вершин в компоненте Пусть — число вершин в G. Тогда Каждый - является связным и ациклическим графом, поскольку G — ациклический граф, Таким образом, каждая компонента — дерево и, следовательно, имеет ребер, т. е. общее число ребер в G равно Однако по предположению Так как ясно, что равенство выполняется тогда и только тогда, когда Таким образом, G — связный граф, имеющий вершин. А поскольку он еще и ациклический, то по определению является остовом

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

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

Теорема 2.3. Граф G является связным тогда и только тогда, когда он имеет остов.

Поскольку остов Т графа G — ациклический, то каждый подграф остова Т является ациклическим подграфом графа G. Будет ли тогда верно, что каждый ациклический подграф является подграфом некоторого остова G? Положительный ответ доказывается в следующей теореме:

Теорема 2.4. Подграф G связного графа G является подграфом некоторого остова G тогда и только тогда, когда G — ациклический.

Доказательство. Необходимость очевидна. Для доказательства достаточности пусть Т — остов графа G. Рассмотрим граф Ясно, что G — подграф графа Граф — связный и содержит все вершины графа G, поскольку является подграфом графа Если — ациклический, то он является остовом графа его подграфом, и тогда теорема доказана. (Отметим, что, если — ациклический, и тогда G — подграф Т.) Предположим, что содержит цикл Из что G — ациклический, следует, что не все ребра содержатся в G. Таким образом, должен иметь по крайней мере одно ребро, например не содержащееся в G. После удаления из циклического ребра получим связный граф содержащий все вершины G Заметим, что является подграфом графа Если — ациклический граф, тогда он является требуемым остовом. Если нет, то будем повторять процесс до тех пор, пока не получим остов, подграфом которого является G. Докажем интересную теорему о минимальном количестве висячих вершин дерева (т. е. вершин степени 1).

Теорема 2.5. В нетривиальном дереве существуют по крайней мере две висячие вершины.

Доказательство. Предположим, что дерево Т имеет n вершин. Тогда по теореме 2.1 оно содержит ребер. По теореме 1.1 имеем число ребер в Т. Тогда . Это равенство будет выполняться только в том случае, если по крайней мере два члена в левой части будут равны 1, т. е. Т имеет по крайней мере две висячие вершины.

<< Предыдущий параграф Следующий параграф >>
Оглавление