Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Доказательство. Доказать: любые две вершины графа соединены единственной простой цепью

12. Дано: – дерево.

Доказать: любые две вершины графа соединены единственной простой цепью.

Дерево – это связный граф без циклов. Пусть u, v - произвольные вершины дерева. Если бы существовали две простые цепи, соединяющие вершины u и v, то они образовали бы цикл (рис. 4) – противоречие.

23. Дано: любые две вершины графа соединены единственной простой цепью.

Доказать: – связен и каждое его ребро – это мост.

Если любые две вершины графа соединены простой цепью, то граф связен. Пусть вершины v 1, v 2 соединены ребром е. Значит, ребро е – единственная простая цепь, соединяющая v 1 с v 2, следовательно, е - мост.

34. Дано: граф связен и каждое его ребро – это мост.

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

Доказательство проведем методом математической индукции по числу

вершин графа.

База. Пусть . Единственный вариант – это граф . Тогда , q = 1, .

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

Индуктивный переход. Рассмотрим произвольный граф с числом вершин , каждое ребро которого – мост. Удалим любое ребро. Граф распадется на две компоненты связности. Пусть в одной из них р 1 вершин и q 1 ребер; во второй – р 2 вершин и q 2 ребер.

В силу индуктивного предположения ,

45. Дано: граф – связен, и число ребер в нем на единицу меньше числа вершин.

Доказать: не содержит циклов.

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

56. Дано: граф не содержит циклов и

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

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

61. Дано: граф не содержит циклов, но добавление в граф любого ребра приводит к появлению единственного цикла, который проходит через добавленное ребро.

Доказать. Граф – дерево.

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

Следствие. Всякое дерево содержит по крайней мере две висячие вершины.

Доказательство. Предположим, что некоторое дерево содержит одну висячую вершину или вовсе их не содержит. Тогда степени по крайней мере вершины графа не меньше 2. Воспользуемся теоремой Эйлера: , что противоречит равенству

5.3.3. Ориентированные, упорядоченные, бинарные деревья

<== предыдущая лекция | следующая лекция ==>
Деревья. Определение. Деревом называют связный граф без циклов | 
Поделиться с друзьями:


Дата добавления: 2014-01-05; Просмотров: 2196; Нарушение авторских прав?; Мы поможем в написании вашей работы!


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



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




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