Инструменты пользователя

Инструменты сайта


examination:diskretka:question17

Вопрос №17. Деревья и их свойства

Пусть Г - неориентированный граф без циклов, петель и кратных ребер. Тогда Г называют лесом. Если Г связен, то он является деревом.

Поскольку ни какое дерево не содержит циклов, то всякая цепь является простой.

Свойства деревьев:

1) Любые 2 вершины дерева связаны одной цепью. Наглядным представлением дерева (Т) можно получить при помощи следующей конструкции:

  • выберем произвольную вершину v0 и назовем корнем;
  • от корня проведем все ребра к вершинам, находящимся на расстоянии 1;
  • от этих вершин проведем ребра к вершинам, находящимся на расстоянии 2 от корня;

Вершина графа называется концевой (висящей), если степень вершины =1

2) Если конечное дерево имеет хотя бы 2 вершины, то оно имеет по крайней мере 2 концевых вершины и 1 концевое ребро.

В дереве с корнем v0 можно естественным образом ориентировать ребра. Вершина v соединена с корнем ровно 1 цепью. Если эта цепь не содержит ребро (v,w) , то данное ребро ориентировано от v к w, в противном случае наоборот.

3) В конечном дереве число вершин на 1 больше числа ребер.

Иногда удобно выделить в дереве некоторую цепь - ствол дерева. Стволом дерева называется всякая максимальная цепь этого дерева.

examination/diskretka/question17.txt · Последние изменения: 2014/01/15 08:14 (внешнее изменение)