Математическое моделирование на графах. Часть 1. Берцун В.Н. - 29 стр.

UptoLike

Составители:

Рубрика:

Глава 1. Основные понятия теории графов 29

рез центр дерева. Лесом называется несвязный граф, представляю-

щий собой объединение деревьев. Очевидно, что лес является гра-

фом без циклов (ациклическим графом). Дерево с выделенной вер-

шиной (корнем) называется корневым деревом, а без выделенной

вершины – свободным деревом. В дереве с n вершинами можно вы-

брать n различных корней. В табл. 1 приведено множество различ-

ных свободных и корневых деревьев для n = 3, 5.

Таблица 1.2

n Свободные деревья Корневые деревья

Известно, что понятие корневого дерева используется, например,

при организации работы файловой системы компьютеров, где файлы

объединены в особые структуры – папки и каталоги. Помеченным

называется граф, вершинам которого приписаны метки (номера,