Читать «Математический аппарат инженера» онлайн - страница 35

Рис. 16. Существенно различные деревья с шестью вершинами.

Рис. 17. Прадерево с корнем v₀.

Рассматриваются также деревья с ориентированными ребрами (дугами). Ориентированное дерево называется прадеревом с корнем v₀ , если существует путь между вершиной v₀ любой другой его вершиной (Рис. 17). Ясно, что прадерево имеет единственный корень.

До сих пор рассматривались деревья как минимальные связные графы на множестве р вершин. Важное значение имеет и другая точка зрения, когда деревья или лес являются частями некоторого графа, т. е. образуются из его ребер. Любая связная совокупность ребер, не содержащая контуров, вместе с инцидентными им вершинами образует дерево графа (Рис. 18, а). Если такое дерево является суграфом (содержит все вершины графа), то оно называется покрывающим деревом или остовом (Рис. 18, б). Так как петля

- 56 -

представляет собой простейший цикл, состоящий из единственного ребра, то она не может входить в состав любого дерева графа.

Ребра графа, которые принадлежат его дереву, называют ветвями. Если дерево покрывает граф, то множество ребер графа разбивается на два подмножества: подмножество ветвей и подмножество ребер дополнения дерева, называемых хордами. При этом связный (р, q) - граф содержит v = р - 1 ветвей и σ = q - р + 1 хорд. Если граф несвязный, то совокупность, остовов R его компонент образует покрывающий лес. В этом случае ν = р - R и σ = q - р + R.

Рис. 18. Дерево как часть графа (выделено жирными линиями):

а — дерево; б — остов (покрывающее дерево).

Деревья играют важную роль в различных прикладных задачах, когда, например, речь идет о связи каких-либо объектов минимальным числом каналов (линий связи, дорог, коммуникаций) с определенными свойствами. С помощью дерева определяется система координат при моделировании цепей и систем различной физической природы. Деревья используются в качестве моделей при рассмотрении иерархических систем объектов, структурных формул органических соединений и т. п.

13. Планарность. Граф называют плоским (планарным), если существует изоморфный ему граф (геометрическая реализация), который может быть изображен на плоскости без пересечения ребер. Например, хотя в одном из графов на Рис. 10 ребра пересекаются, изоморфные ему не имеют пересечений, следовательно, он плоский.

На Рис. 19 показаны два неплоских графа, играющие фундаментальную роль в теории планарности и называемые графами Понтрягина - Куратовского. Полный пятиугольник (Рис. 19,а) представляет собой простой неплоский графе минимальным числом вершин (полный графе четырьмя вершинами - плоский, а удаление из пятиугольника хотя бы одного ребра также превращает его в плоский граф). Двудольный граф (Рис. 19, б) является моделью известной задачи о трех домах и трех колодцах: можно ли проложить от домов к каждому колодцу дороги так, чтобы они не пересекались (враждующие соседи должны иметь возможность пользоваться всеми колодцами, но не хотят встречаться на дорогах).