Деревья

В теории графов деревом называется связный граф без циклов. Но взгляните на любое дерево за окном: если точки, где ветки соединяются, принять за вершины графа, то получится именно граф без циклов. Деревья - это те графы, с которыми вы в курсе информатики, да и других предметов, чаще всего имеет дело. Дерево каталогов и генеалогическое дерево, да и вообще любая иерархическая система с точки зрения своей структуры представляют собой именно дерево. Применяя алгоритмы поиска в глубину или в ширину, вы из исходного графа извлекаете дерево - вершинами в нем являются вершины исходного графа, и эти вершины соединяются ребром, если при исполнении алгоритма переход от одной вершины к следующей осуществлялся по этому ребру. На рисунке 1.4, а) представлено дерево, полученное применением поиска в глубину в соответствии с рисунком 1.3, а; на рисунке 1.4 б) представлено дерево, полученное применением поиска в ширину. Дерево, которое содержит все вершины некоторого заданного графа G и ребра которого являются ребрами этого графа, называется каркасом графа G. Так что можно сказать, что на рисунке 1.4 представлены два каркаса одного и того же графа. По-другому каркас называют остовом или стягивающим деревом.

Дерево, как правило, изображают некоторым стандартным образом. Для этого фиксируют одну из вершин, ее называют корнем. Корень обычно изображают внизу, а все остальные вершины распределяют по уровням. На первом уровне размещаются вершины, смежные с корнем, на втором - смежные с вершинами первого уровня, отличные от корня, на третьем - смежные с вершинами второго уровня, отличные от вершин первого уровня, и т.д.

На рисунке 1.5 приведены два изображения одного и того же дерева, взятого с рисунка 1.4, б), при разном выборе корневой вершины: в первом случае корнем служит вершина, обозначенная числом 6. Впрочем, нередко бывает удобнее рисовать дерево сверху вниз или слева направо. Выбор корня фактически превращает дерево в ориентированный граф: на каждом ребре направление выбирается от меньшего уровня к большему. Там же вершины степени 1, отличные от корня, были названы листьями. Легко видеть, что, удаляя лист вместе с ведущим в него ребром, мы одновременно уменьшаем на 1 количество вершин и количество листьев. Проделав это столько раз, сколько ребер в деревне, мы останемся один на один с корнем. Следовательно, в любом дереве вершин всегда на 1 больше, чем ребер. На самом деле справедливо и обратное утверждение: если в связном графе количество вершин на 1 больше числа ребер, то это - дерево.

Вопросы и Задания!

1. Какой граф называют деревом?

2. Как связаны количество ребер и вершин в дереве?

3. Для графа, изображенного на рисунке 1.4, а), нарисуйте дерево, взяв в качестве корня вершину, обозначенную: а) числом 5; б) числом 10.

4. Изобразите все деревья с четырьмя и пятью вершинами.

Назад В начало Далее

Календарь

Калькулятор

Поиск

Друзья сайта

Дискретная математика

Деревья