Cтраница 4
Поскольку D1 ( T) есть дерево, в котором полустепень исхода любой вершины равна 2, кроме, быть может, одной вершины, то если в дереве Dl ( V) нет вершины с полустепенью исхода 1, то в Dl ( V) будет ровно 2 k - 2 ребра, а если в дереве Dl ( V) есть вершина с полустепенью исхода 1, то в Dl ( V) будет 2 k - 1 ребро. [46]
V) есть дерево, в котором полустепень исхода любой вершины равна 2, кроме, быть может, одной вершины, то если в дереве Dl ( V нет вершины с полустепенью исхода 1, то в Dl ( V будет ровно 2 k - 2 ребра, а если в дереве Dl ( V) есть вершина с полустепенью исхода 1, то в Dl ( V ] будет 2 k - 1 ребро. [47]
Поскольку D1 ( T) есть дерево, в котором полустепень исхода любой вершины равна 2, кроме, быть может, одной вершины, то если в дереве Dl ( V) нет вершины с полустепенью исхода 1, то в Dl ( V) будет ровно 2 k - 2 ребра, а если в дереве Dl ( V) есть вершина с полустепенью исхода 1, то в Dl ( V) будет 2 k - 1 ребро. [48]
Для данной сети N ( D, ф) определим поток через N как функцию ф, сопоставляющую каждой дуге а из D неотрицательное действительное число ф ( а) ( называемое потоком через а) таким образом, что ( i) ф ( д): ф ( а) для любой дуги а; ( и) по отношению к сети ( D, ф) полустепень исхода и полустепень захода любой вершины ( отличной от у и да) равны между собой. Говоря неформально, это означает, что поток через любую дугу не превосходит ее пропускной способн эс-ти и что полный поток, входящий в любую вершину ( отличную от v и w), равен полному потоку, выходящему из нее. Для удобства назовем дугу а, для которой ф ( а) ф ( а), насыщенной ( на рис. 29.2 насыщенными являются дуги ( v, z), ( х, z), ( у, z), ( х, w) и ( z, w)); остальные дуги называются ненасыщенными. [49]
Так как А и Ву являются графами, то к ним можно применить теорему 1.1. В дальнейшем граф Ах будем называть графом класса X, а Ву - графом класса У. Полустепени исхода Ti захода вершин q Q и Vj V обозначим соответственно через st, Uj и pt, Wj. Из теоремы 1.1 и леммы 5.3 вытекает следующая теорема. [50]
Если каждому ребру графа приписана ориентация, то граф называется ориентированным. Аналогично, полустепень исхода вершины v ( обозначается deg ( г)) есть число ребер, имеющих v своей первой вершиной. Определения маршрута, цепи, простой цепи и цикла должны быть несколько изменены для случая ориентированных графов. В каждой из этих чередующихся последовательностей вершин и ребер нужно потребовать, чтобы каждое ориентированное ребро соединяло в этой последовательности вершину, предшествующую ему, с вершиной, следующей за ним. Ациклический орграф есть орграф, не содержащий ориентированных циклов. [51]
Что называется степенью графа. Что называется полустепенями исхода и захода графа. [52]
Из определения изоморфизма следует, что изоморфные графы отличаются друг от Друга только упорядоченностью в обозначениях вершин. Однако перенумерация вершин не изменяет полустепени исхода s и полустепени захода р каждой вершины. [53]