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

UptoLike

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

Рубрика:

28 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

1.8. Деревья и их свойства

Простейшим классом графов являются деревья, которые играют

важную роль в современных компьютерных технологиях и про-

граммировании [23, 24]. Это понятие в теорию графов было введено

еще в XIX в. Г. Кирхгофом для анализа электрических цепей и

А. Кэли при анализе структур химических формул. Деревья – очень

удобный инструмент представления информации самого разного ви-

да. Деревом называется всякий связный граф, не имеющий циклов

[17, 25]. Изолированную вершину также можно считать деревом.

Деревом является, например, изображение на карте реки с ее прито-

ками. Примеры деревьев представлены на рис. 1.31.

Рис. 1.31

Если ребрам (дугам) графа приписаны некоторые веса, то он на-

зывается взвешенным. Каждое ребро дерева является мостом, а вер-

шины степени 1 называются висячими.

Утверждение 1.7. Дерево с n вершинами имеет n – 1 ребро.

Доказательство. Для изолированной вершины доказательство

очевидно. Если G – дерево (см. рис. 1.31), то удалив из G одно реб-

ро, получим два дерева с теми же вершинами. Для получения трех

деревьев необходимо удалить два ребра. Для того чтобы из дерева с

n вершинами получить n изолированных вершин, необходимо уда-

лить n – 1 ребро. ■

Отметим, что любые две различные вершины дерева соединяет

единственная простая цепь. Центр дерева содержит одну или две

смежные вершины, и каждая цепь наибольшей длины проходит че-