Доказательство. Необходимость. ( ) Пусть G=(V, U)-дерево
Необходимость. () Пусть G =(V, U) - дерево. Покажем, что |V| = |U| + 1. Рассмотрим некоторое корневое представление G.
К этому графу, пока это возможно, применяется следующее преобразование: выбирается произвольная висячая вершина и удаляется из графа вместе с ведущим в эту вершину ребром.
Очевидно, что через конечное число выполнений приведенного преобразования от графа G останется только корневая вершина.
Поскольку число удаленных при этом вершин равно числу удаленных ребер и одна вершина графа G осталась, то |V| = |U| + 1.
Достаточность. () Пусть G =(V, U) - неориентированный связный граф без петель, для которого |V| = |U| + 1. Покажем, что G - это дерево.
Предположим противное: G не является деревом. Следовательно, в G имеются циклические ребра.
Выполним процедуру последовательного размыкания циклов в G,не нарушающего связности этого графа. Она основана на следующем элементарном действии: выбирается произвольный элементпрный цикл в G, длина которого не меньше чем 3,после чего из G удаляется любое ребро этого цикла.
Указанное действие повторяется до тех пор, пока в получаемых связных графах имеются циклические ребра.
Заданное преобразование графа заканчивается за конечное время и полученный в результате граф является связным.
Обозначим этот граф как G * = (V, U *). Поскольку G * не содержит циклических ребер, то он является деревом.
Поэтому из доказательства необходимости следует справедливость равенства: |V| = |U * | + 1.
Последнее противоречит начальному предположению о том, что |V| = |U| + 1, поскольку по построению графа G * должно выполняться неравенство: |U * | < |U|.
Полученное противоречие означает, что G не может содержать циклических ребер и является деревом.
Дата добавления: 2015-09-27 | Просмотры: 505 | Нарушение авторских прав
|