2.6. Деревья и разрезы
При использовании терминов «дерево», «лес», «разделяющее множество», «разрез» и «простой разрез» без специальной оговорки считается, что направления дуг не учитываются и рассматривается соответствующий неориентированный граф. Однако, при учете направления дуг, возникает несколько дополнительных понятий.
Ориентированный граф является ориентированным деревом, растущим из корня 
если (1) он образует дерево в неориентированном смысле и (2) — единственная цепь между 
и любой другой вершиной 
является путем из 
Очевидно, что дерево может иметь самое большее один корень и что, вообще говоря, деревья в ориентированном графе могут быть неориентированными. На рис. 2.5, а, например, нельзя найти ориентированное дерево, покрывающее граф (почему?). С другой стороны, на рис. 
утолщенные дуги показывают ориентированное дерево с корнем в вершине 
покрывающее изображенный ориентированный граф. В главе 3 будет рассмотрена систематическая процедура нахождения
ориентированного дерева с корнем в заданной вершине 
Для которого пути ко всем остальным вершинам являются кратчайшими с точки зрения некоторой функции расстояния, определенной на дугах.
Напомним, что разрез и, в частности, простой разрез являются множеством ребер, соединяющих 
где 
является разбиением вершин связного графа на два непересекающихся непустых множества.
Рис. 2.5.
Удаление разреза приводит к тому, что граф распадается на две или более компоненты. Удаление простого разреза разделяет граф точно на две компоненты. В ориентированном графе дуги разреза могут быть разделены на два множества: дуги, направленные из 
и дуги, направленные из 
Рис. 2.6.
Удаление первого множества разрывает все пути из 
в то время как удаление последнего разрывает все пути из 
Позже (в частности, в разделе о потоках в сетях) мы рассмотрим эти два множества отдельно. Назовем первое множество разрезом 
а второе — разрезом 
На
рис. 2.6, b и с представлены эти множества для разреза, изображенного на рис. 2.6, а.
Заметим, что если 
сильно связен, то оба ориентированных разреза для любого разбиения 
всегда будут непустым» (см. упражнение 2.11, где содержится утверждение, обратное данному).
Упражнения
(см. скан)
