 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Свободные деревья
|
|
Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется (свободным) деревом. Компонентами связности леса являются деревья.
Граф G, в котором q(G) = р(G)- 1, называется древовидным.
В ациклическом графе G z(G) = 0. Пусть и, v — несмежные вершины графа G, х = (и, v) 
E. Если граф G+x имеет только один простой цикл, z(G+х)= 1, то граф G называется субциклическим.
Пример
На рис. 9.1 показаны диаграммы всех различных (свободных) деревьев с 5 вершинами, а на рис. 9.2 — диаграммы всех различных (свободных) деревьев с 6 вершинами.
Рис. 8.1. Свободные деревья с 5 вершинами
|
Рис. 8.2. Свободные деревья с 6 вершинами
Основные свойства деревьев
Следующая теорема устанавливает, что два из четырех свойств — связность, ацикличность, древовидность и субцикличность — характеризуют граф как дерево.
Теорема
Пусть G(V, Е) — граф с р вершинами, q ребрами, k компонентами связности и z простыми циклами. Пусть далее х — ребро, соединяющее любую пару несмежных вершин в G. Тогда следующие утверждения эквивалентны:
1. G — дерево, то есть связный граф без циклов, k(G) = 1&z(G) = 0;
2. любые две вершины соединены в G единственной простой цепью,
.
3. G — связный граф, и любое ребро есть мост,
;
4. G — связный и древовидный,
;
6. G — ациклический и субциклический,
;
7. G — связный, субциклический и неполный,
;
8. G — древовидный и субциклический (за двумя исключениями),
;
Доказательство
Рис. 8.3. К доказательству теоремы о свойствах деревьев
[1 
2] От противного. Пусть существуют две цепи <и, v> (рис. 9.3, слева). Тогда w, w2 — простой цикл.
|
|
[2 3.] Имеем: 
и, v 
!, следовательно, 
. Далее от противного. Пусть ребро х — не мост. Тогда в G - х концы этого ребра связаны цепью. Само ребро х — вторая цепь.
[3 4.] Индукция по р. База: р = 1 q = 0. Пусть 
для всех связанных графов G с числом вершин меньше р, у которых любое ребро суть мост. Тогда удалим из G ребро х (которое является мостом). Получим две компоненты G ' и G ", удовлетворяющие индукционному предположению. Имеем:
.
[4 5.] От противного. Пусть есть цикл с п вершинами и п ребрами. Остальные р - п вершин имеют инцидентные им рёбра, которые связывают их с циклом, Следовательно, q ≥ р, что противоречит условию q = р - 1.
[5 1.] Граф без циклов, следовательно, его компоненты — деревья. Пусть их k;. Имеем:
i = У(pi-1) = Уpi-k = p-k
Но q=p-1, следовательно, k = 1.
[5 6.] По ранее доказанному 5 1 2. Имеем: . Соединив две несмежные вершины, получим единственный простой цикл.
[6 7.] При р ≥ 3 граф Кр содержит цикл, следовательно, G ≠ Кр. Далее от противного. Пусть G несвязен, тогда при соединении ребром двух компонент связности цикл не возникнет.
[7 2.] Имеем k(G) = 1, следовательно, . Пусть цепь не единственная. Тогда существует цикл Z, причем Z = К3, = С3. Действительно, пусть Z > С3, тогда, соединив две несмежные вершины этого цикла, получим два цикла. Но G связен и G ≠ К3, следовательно, существует другая вершина w, смежная с Z = К3 (см. рис. 9.3, справа). Если w смежна более чем с одной вершиной Z, то имеем больше одного цикла. Если w смежна только с одной вершиной Z, то соединив её с другой вершиной, получим два цикла.
[7 8.] Имеем k(G) = 1, следовательно, G ≠ К2 
К3, G ≠ К1 К3. Имеем по доказанному: 7 2 3 4, то есть q = р- 1.
[8 5.] От противного. Пусть в G есть цикл Z = Сп. Если n > 3, то если внутри Z уже есть смежные вершины, имеем два цикла. Если в Z нет смежных вершин, то, соединив несмежные вершины в Z, получим два цикла. Следовательно, Z = К3. Этот цикл Z является компонентой связности G. Действительно, пусть это не так. Тогда существует вершина w, смежная с Z. Если w смежна более чем с одной вершиной Z, то имеем больше одного цикла. Если w смежна только с одной вершиной Z, то, соединив её с другой вершиной, получим два цикла. Рассмотрим G:=G - Z. Имеем: р = р' + 3, q = q' + 3. Но q = р - 1, следовательно, q' = р' - 1. Отсюда z(С') = 0, так как один цикл уже есть. Следовательно, компоненты G' — деревья. Пусть их k. Имеем:
I = У(pi-1) = Уpi-k = ṕ-k
но q' = p' -1, следовательно. k = 1. то есть дерево одно. Если в этом дереве сбединить несмежные вершины, то получим второй цикл. Два исключения: деревья, которые не имеют несмежных вершин, — это К1 и K2.
Общая схема доказательства представлена на рис. 9.4. Граф доказательства сильно связен, следовательно, теорема доказана.
Дата публикования: 2014-11-04; Прочитано: 512 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
