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

Деревья

Определение. Деревом называют связный граф без циклов. Лесом называют граф без циклов.

На рис. 3 показан лес, состоящий из четырех деревьев.

Теорема о свойствах деревьев.

Пусть – простой граф с р вершинами и q ребрами. Следующие утверждения эквивалентны

1. – дерево.

2. Любые две вершины графа соединены единственной простой цепью.

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

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

5. не содержит циклов и.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2013-12-13