 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Следствие 1 В любом нетривиальном дереве имеются по крайней мере две висячие вершины
|
|
Доказательство
Рассмотрим дерево G(V, Е). Дерево — связный граф, следовательно, 
.
Далее от противного. Пусть 
. Тогда
2q = Уd(vi) > 2(р - 1) + 1 = 2р - 1.
Но q = р - 1, то есть 2q = 2р - 2. Имеем противоречие: 2р - 2 2 > 2р - 1.
Следствие 2. Каждая не висячая вершина свободного дерева является точкой сочленения.
Доказательство
Пусть G(V, Е) — дерево, v 
V и d(v) > 1. Тогда 
и, w V(u,v) E& (u, w) E. Граф G связен, поэтому существует цепь (и, w). Если v 
<и,w>, то имеем цикл v,<и,w>, v, что противоречит тому, что G — дерево. Следовательно, и, w V 
<и,w> v <u, w> и по теореме 8.1.2 вершина v — точка сочленения.
Дата публикования: 2014-11-04; Прочитано: 515 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
