Cтраница 2
Обходим границу Ki против часовой стрелки, начиная с FJ, до тех пор, пока не достигнем единственного ребра Wt - wt из Ki, которое пересекает луч Ле - 1а - ь или пока не достигнем L, не найдя подобного ребра. [16]
В конце предыдущего раздела было отмечено, что графы GP и GQ не могут содержать цикла, ограниченного единственным ребром. [17]
С / о ровно k листьев, и каждый из них имеет полустепень исхода 0 и в каждый из них ведет единственное ребро. Очевидно, что такая вершина есть. Отметим также, что часть цепи С [ между вершинами 7г и сч не принадлежит никакой другой цепи. [18]
С / о ровно k листьев, и каждый из них имеет полустепень исхода 0 и в каждый из них ведет единственное ребро. [19]
Наконец, докажем, что для всякого г, 0 z р - 2, если е, uv есть то самое единственное ребро дерева Т, которое принадлежит разрезу С -, то С является ( и, и) - разрезом в графе G, имеющим минимальную пропускную способность. [20]
Кроме того, отсюда следует, что либо запись yi подпадает под случай 3.1 алгоритма построения соответствия и тогда части разбиения, состоящей из одной записи yi, сопоставляется одно единственное ребро ( А j 7)) либо запись у подпадает под случай 3.2 алгоритма построения соответствия, где параметр t принимает значение 1, и тогда части разбиения, состоящей из одной записи у, сопоставляется два ребра: ребро ( / 3j 7i) и ребро, входящее в / 5j и принадлежащее цепи Ci. Следовательно, согласно приведенному выше замечанию и свойству 10, и в этом варианте совокупность ребер, соответствующая части разбиения, содержащей запись yj, не пересекается с образами никаких других частей разбиения. [21]
Кроме того, отсюда следует, что либо запись yi подпадает под случай 3.1 алгоритма построения соответствия и тогда части разбиения, состоящей из одной записи у, сопоставляется одно единственное ребро ( А. Следовательно, согласно приведенному выше замечанию и свойству 10, и в этом варианте совокупность ребер, соответствующая части разбиения, содержащей запись у, не пересекается с образами никаких других частей разбиения. [22]
Отличное от одноточечного графа дерево, некоторая концевая точка которого воспринимается как отличающаяся от всех других точек, называют посаженным деревом3; выделенную, единственную в своем роде, концевую точку называют корнем и единственное ребро, ограниченное корнем, - стволом посаженного дерева. [23]
Графом п домиков и m колодцев будем называть граф, у которого n m вершин разбиты на две непересекающиеся группы из п и m элементов соответственно, причем каждая вершина из одной группы соединена единственным ребром с каждой вершиной другой группы. [24]
Полученный таким образом граф обозначим С / 2 - Мы получили, что T ( U-2) T ( t / i), С / 2 разрешает задачу /, и число вершин с полустепенью захода более 1 в t / 2 по крайней мере на 1 меньше чем в U, поскольку теперь в вершину J3 ведет единственное ребро, а новых вершин с полустепенью захода более 1 образоваться не могло. [25]
Полученный таким образом граф обозначим С / 2 - Мы получили, что T ( U %) T ( C / i), U2 разрешает задачу /, и число вершин с полустепенью захода более 1 в С / 2 по крайней мере на 1 меньше чем в C / i, поскольку теперь в вершину J3 ведет единственное ребро, а новых вершин с полустепенью захода более 1 образоваться не могло. [26]
Деревом называется связный ориентированный граф, не содержащий петель. Каждая пара его вершин соединяется единственным ребром. [27]
Теорема доказывается по индукции. Теорема справедлива, если цепь состоит из пары вершин, связанных единственным ребром. По предположению индукции, v0 и vm связаны двумя цепями U и Uz, удовлетворяющими условиям теоремы. [28]
Тогда в G найдется путь Р из г в w, не содержащий у. Очевидно, что этот путь должен идти по ребру ( a, d), поскольку это единственное ребро в G, которого нет в G. [29]
Конечным автоматом называется ориентированный граф ( см. 5.6), в котором выделено два ( возможно пересекающиеся) множества вершин, называемых начальными и финальными и каждое ребро помечено буквой из конечного алфавита X. Автомат называется детерминированным, если начальная вершина ровно одна и в каждой вершине для каждой буквы существует единственное ребро, начинающееся в этой вершине и помеченное данной буквой. Язык, задаваемый автоматом, состоит из множества всех слов, получающихся при прочтении маршрута из какой-либо начальной верши -, ны в какую-либо финальную. [30]