2015-04-01
461
. Причем, если
, то граф не имеет циклов, то есть является деревом или лесом;
, то граф имеет ровно 1 цикл.
Число внутренней устойчивости графа G обозначается 
– это максимальное число несмежных вершин графа.
Множеством внешней устойчивости графа G (внешне устойчивым множеством)называется любое множество вершин Q такое, что из каждой вершины множества 
хотя бы одна дуга ведет в вершину множества Q. Если граф неориентированный, то число внешней устойчивости ищется для канонически соответствующего ориентированного графа.
Число внешней устойчивости графа G обозначается 
– это мощность минимального внешне устойчивого множества.
Сетью называется любой частично-ориентированный граф S, некоторые вершины которого помечены.
Некоторые помеченные вершины называются входными полюсами, другие – выходными полюсами. Непомеченные вершины называются внутренними. Простая цепь, связывающая входной и выходной полюс будет называться цепью.
Если сеть содержит k входных и n выходных полюсов, то она называется ( k, n)- полюсником.
Двухполюсной сетью называется сеть, являющаяся (1, 1)-полюсником.
Пусть дана частично ориентированная двухполюсная сеть. Пусть для каждого ребра сети определена пропускная способность ребра 
.
Потоком в сети называется пара объектов 
, где 
– некоторая ориентация неориентированных ребер сети, f = f(e), функция значения потока на ребре е, которая удовлетворяет следующим условиям:
1. ограничение:
2. для каждой внутренней вершины выполняется закон Киргоффа:
,
где 
– множество ребер выходящих из вершины 
,
где 
– множество ребер входящих в вершину .
Если 
– входной полюс сети, а 
– выходной полюс, то
.
Величиной потока в сети назовем число 
. Очевидно, что величина потока в сети зависит и от ориентации ребер , и от задания функции f(e), то есть является величиной переменной.
Сечением в сети называется совокупность ребер, при удалении которых сеть становится несвязной. Сечение называется простым, если при удалении из него хотя бы одного ребра, оно перестает быть сечением.
Утверждение:
Для каждого ребра простого сечения найдется цепь, проходящая только через это ребро простого сечения.
Если эта цепь идет в направлении этого ребра, то оно называется прямым, если против направления ребра, то обратным. Неориентированные ребра цепи всегда прямые.
Пропускной способностью сечения W называется сумма W(c) пропускных способностей его прямых ребер.
