Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Доказательство. Утверждение (теорема о свойствах точки сочленения)





Утверждение (теорема о свойствах точки сочленения).

Пусть - связный граф и . Тогда следующие утверждения эквивалентны:

1. v – точка сочленения;

2. : любая простая цепь, соединяющая вершины u и w проходит через вершину v.

3. Вершина v не является висячей вершиной никакого остовного дерева графа G.

. Рассмотрим граф . Так как v – точка сочленения, то граф не связен, так что число k его компонент связности . Выберем произвольно две компоненты связности графа : и . Пусть . В графе не существует простой цепи, соединяющей вершины u и w. Но в исходном графе G такие цепи были, ведь граф G был связен. Все они исчезли после удаления вершины v, значит, все они через неё проходили.

. Допустим, что вершина v – это висячая вершина некоторого остовного дерева T графа G (рис. 2)

 

Рис. 2

 

Тогда две любые другие вершины u и w дерева T, отличные от вершины v, соединены в T (и, значит, в G) простой цепью, не проходящей через вершину v – противоречие.

. Легко видеть, что во всяком дереве висячие вершины и только они не являются точками сочленения.

Если v – не есть висячая вершина никакого остовного дерева графа G, её удаление разрушит все остовные деревья этого графа. Что и означает разделение связного графа на несколько компонент связности.

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

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




Дата добавления: 2013-12-13; Просмотров: 479; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.018 сек.