Cтраница 2
Для вершин орграфа существуют параметры, называемые полустепенью исхода, полу-степенью захода и степенью вершины. Полустепеныо исхода р вершины х называется число исходящих из нее ребер. Полустепеныо захода q вершины х называется число входящих в нее ребер. [16]
В ориентированных графах используются также термины полустепень захода и полустепень исхода. Первый означает число дуг, входящих в данную вершину, а второй - число дуг, исходящих из нее. [17]
Поскольку каждое из Di есть дерево, в котором полустепень исхода любой вершины равна 2, то в Di будет ровно 2 - ( / 1) - 2 ребра. [18]
Поскольку каждое из Di есть дерево, в котором полустепень исхода любой вершины равна 2, то в DJ будет ровно 2 - ( 1) - 2 ребра. [19]
Таким образом, если в графе нет вершин с полустепенью исхода больше 1, то, значит, в графе нет лишних ребер. [20]
Поскольку D1 ( T) есть дерево, в котором полустепень исхода любой вершины равна 2, кроме, быть может, одной вершины, то если в дереве Dl ( V) нет вершины с полустепенью исхода 1, то в Dl ( V) будет ровно 2 k - 2 ребра, а если в дереве Dl ( V) есть вершина с полустепенью исхода 1, то в Dl ( V) будет 2 k - 1 ребро. [21]
Теорема 16.2. Бесконтурный орграф содержит по крайней мере одну вершину с нулевой полустепенью исхода. [22]
Таким образом, антибаза конденсации О есть множество вершин в О, полустепени исхода которых равны 0, и антибазы самого графа О строятся из антибазы графа & путем выбора по одной вершине в каждой вершине-множестве антибазы В - подобно тому, как это делалось раньше для баз. [23]
С / о ровно k листьев, и каждый из них имеет полустепень исхода 0 и в каждый из них ведет единственное ребро. [24]
Таким образом, антибаза конденсации G есть множество вершин в G, полустепени исхода которых равны 0, и антибазы самого графа G строятся из антибазы графа G путем выбора по одной вершине в каждой вершине-множестве антибазы В - подобно тому, как это делалось раньше для баз. [25]
Пусть у вершины v турнира Т полустепень исхода не меньше, чем полустепень исхода каждой другой вершины турнира. [26]
С / о ровно k листьев, и каждый из них имеет полустепень исхода 0 и в каждый из них ведет единственное ребро. Очевидно, что такая вершина есть. Отметим также, что часть цепи С [ между вершинами 7г и сч не принадлежит никакой другой цепи. [27]
Ясно, что аналог орлеммы о рукопожатиях принимает следующий вид: сумма полустепеней исхода всех вершин в сети равна сумме их полустепеней захода. В дальнейшем будем предполагать ( если не оговорено противное), что орграф D содержит ровно один источник v и один сток w, общий случай, когда имеется несколько источников и стоков ( в разобранном выше первом примере это соответствует более чем одному изготовителю и более чем одному рынку), легко свести к этому частному ( см. упр. [28]
Привести пример 7-вершинного орграфа без петель и кратных дуг, опровергающий следующее утверждение: если полустепени исхода и захода любой вершины орграфа положительные и четные, то для каждой вершины орграфа найдется контур, содержащий ее. [29]
Следующая теорема дает верхнюю оценку объема перебора при установлении изоморфизма графов, имеющих различные пары полустепеней исхода и захода каждой вершины. [30]