Дуга - путь
Cтраница 1
Дуги пути ранжируются в порядке возрастания величины полученных оценок веса Кш; оптимизация начинается с дуг, обладающих минимальным весом. [1]
При этом некоторая дуга пути р должна начинаться в вершине, не являющейся потомком вершины i, и вести в вершину - потомок i. Тогда w i и все дуги, следующие за ( и, w) в р, имеют оба конца среди потомков г. Так как все потомки вершины i имеют М - номера, большие г, и так как и не является потомком i, то мы можем заменить часть р от начала пути до дуги ( и, w) путем из древесных дуг из s в и и получить путь в Gd), не содержащий i. Но это противоречит определению Sdd, v), поэтому вершина Sdd, v) должна доминировать v в G. [2]
Пусть О - дуга пути Р, непосредственно предшествующая дуге О. Предположим, что вершина 1 ( О) внутренняя. Но так как Р - чередующийся путь, то дуги и имеют разный цвет. Следовательно, дуга О нерегулярна. Это противоречит выбору дуги О. [3]
Уменьшая значения потоков через дуги путей, идущих от XQ к XN, отыскиваем полный поток. [4]
Такая операция делается для всех дуг пути. Инверсия дуги меняет соотношения инцидентности в графе. [5]
Если г не содержится в К, то последняя дуга пути Р является проникающей в К дугой Ое и соответствующее ей ребро Ае графа О есть ребро, проникающее в компоненту К. Следовательно, путь Р представим в виде произведения К ( Ое), где подпуть К не имеет в компоненте К ни ребер, ни вершин. Заметим, что ребро Ае в К не содержится. Из сказанного вытекает, что ребро Ае бикурсальным быть не может. [6]
Путь, соединяющий начальную и конечную вершины граф-схемы, определяет некоторый порядок следования дуг пути, а значит, и соответствующих переменных пути. [7]
На шаге наращивания пути осуществляется с иомощью матрицы проверка того, не является ли очередная дуга пути ао смежной одной из дуг, выделении на предыдущих шагах. Это исключает выделение составных путей. [8]
Если 5 ( Р) 0, то утверждение очевидно: компонента К содержит вершину г и не имеет проникающих в нее ребер. В оставшемся случае последняя дуга пути Р выходит из вершины, не принадлежащей секции В. Значит, ребро, проникающее в К, в 2В не содержится. [9]
 |
Различие в длинах пути при изменении направления движения потока. [10] |
Поскольку длину внешней дуги нельзя сделать меньше некоторой величины, возникла мысль искусственно удлинить внутреннюю дугу и все лежащие между крайними дугами пути до размеров внешней дуги. Поток массы разделяется иа внешней дуге лезвием направляющей стреловидной вставки и, соответственно, на внутренней дуге - лезвием направляющего сердечника. [11]
Последовательность дуг ( без учета их ориентации), соединяющая узлы i и /, называется путем между этими узлами. Если i - /, то путь называется контуром. Сеть является связной при условии, что существует по крайней мере один путь между любой парой узлов. В большинстве приложений сетевые модели представляют собой связные линейные графы. Если все дуги пути, связывающего узлы i и 7, ориентированы так, что единичный поток действительно может пройти по этому пути, то такой путь часто называется ориентированной цепью. [12]
Граф сводим по Хехту и Ульману тогда и только тогда, когда он имеет единственный носитель. Предположим, что граф сводим, но его носитель не единствен. He имеет места ни одно из включений Е, Е2 и ЕгаЕ1 в силу максимальности носителя. Таким образом, Ег - Et не пусто. Она не можег быть прямой дугой, так как все прямые дуги входят в EI, и не может быть поперечной по той же причине; следовательно, ( v, w) - обратная дуга. Так как в D2 существует путь ц из s в v, то вместе с дугой ( v, w) образует контур, что невозможно. Кроме того, путь ц не содержит в ершины w, иначе также был бы контур. Значит, Ег - EI пусто, а отсюда следует единственность носителя для сводимого графа. Докажем, что его носитель не единствен. Из леммы 22 следует, что G содержит по крайней мере одну конструкцию вида, показанного на рис. 2.28. Обозначим эту конструкцию через, а через V, W, X, Y, Z - соответственно множества дуг путей из s в а, пз а в Ь, из а в с, из Ъ в с и из с в Ь в какой-нибудь конструкции JF. Эти пять множеств не пересекаются, а V может быть пусто. [13]
Страницы: 1