Дерево, эквивалентные определения

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Дерево (англ. tree) — связный ациклический граф.

Пример дерева



Определение:
Лес (англ. forest) — граф, являющийся набором непересекающихся деревьев.

Примеры леса

Содержание

[править] Определения

Для графа G эквивалентны следующие утверждения:

  1. G — дерево.
  2. Любые две вершины графа G соединены единственным простым путем.
  3. G — связен и p = q + 1, где p — количество вершин, а q количество ребер.
  4. G — ацикличен и p = q + 1, где p — количество вершин, а q количество ребер.
  5. G — ацикличен и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
  6. G — связный граф, отличный от K_p для p > 3, а также при добавлении любого ребра для несмежных вершин появляется один простой цикл.
  7. G — граф, отличный от K_3 \cup K_1 и K_3 \cup K_2, а также p = q + 1, где p — количество вершин, а q количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

[править] Доказательство эквивалентности

1 \Rightarrow 2

Граф связен, поэтому любые две вершнины соединены путем. Граф ацикличен, значит путь единственен, а также прост, поскольку никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.

2 \Rightarrow 3

Очевидно, что граф связен. Докажем по индукции, соотношение p = q + 1. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше p вершин. Если же граф G имеет p вершин, то удаление из него любого ребра делает граф G несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, p = q + 1.

3 \Rightarrow 4

Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавляем ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию.

4 \Rightarrow 5

G — ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то p = q + k, где k — число компонент связности. Поскольку p = q + k, то k = 1, а значит G — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.

5 \Rightarrow 6

Поскольку K_p для p > 3 содержит простой цикл, то G не может им являться. G связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.

6 \Rightarrow 7

Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку 2 \Rightarrow 3, получим p = q + 1. Любые две вершины соединены простой цепью, так как G — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться K_3, так как иначе добавив ребро, соединяющее две вершины цикла, мы получим более одного простого цикла, что противоречит условию. K_3 является собственным подграфом G, поскольку G не является K_p для p > 3. G — связен, а значит есть вершина смежная с K_3. Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф G является K_p для p > 3, и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.

7 \Rightarrow 1

Если G имеет простой цикл, то он является отдельной компонентой K_3 по ранее доказанному. Все остальные компоненты должны быть деревьями, но для выполнения соотношения p = q + 1 должно быть не более одной компоненты отличной от K_3, так как в K_3 p = q = 3. Если это дерево содержит простой путь длины 2, то в G можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является K_1 или K_2. Значит G является K_3 \cup K_1 или K_3 \cup K_2, которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если G ациклический и p = q + 1, то из 4 \Rightarrow 5 и 5 \Rightarrow 6 верно, что G — связен. В итоге получаем, что G является деревом по определению.

[править] См. также

[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты