Ученые записки математических кафедр вып. 1970 г.

- 2 9 6 - * ^ 0 * 3 , (5 .2 ) для всех внутренних верхних Дуг граней Л ( М * $ , ( 5 . Э ) ДЛЯ всех внутренних нижних дуг д граней <*>. # ДОИ^ЛТЕЛЬСТВО. Покажем прежде существование ^ -разбиения сети переводящего ее в граф £ . где выполнены (5 :1 ) и (5 .2 ), который получен за счет внесения фиктивных вершин только в верхние внутренние дуги ^ . Доказательство проведем индукци­ ей по числу к граней сети З к В сети 3< дуга ° в н е ш н я я , поэтому противоречия с (5 .2 ) не получаем. В приведенной сети $к « = У, , , , т - неравенство (5 .1 ) выполняется всегда, поскольку каждая ее вершина ^ I за исключением быть модет начальной Р и конечной О. имеет степень Ы. (РА * 3 т _„ „»л г •• 1 */ ° • 1ак что о , является иско­ мым » Предполагая полученным Нижний путь К-1 К - , графа 3, нижним путем V сети 3 . , перейдем к построению 5^ к -1 полностью совпадает с . Действительно,- поскольку не содержит ребер верхних дуг граней 2,- , ^ < к не содержит фиктивных вершин. Отсюда присоединение гр ни £)к к £>к -1 ничем не отличается от присоединения К , В частности, <1 (ы.к ) имеет одно и то же значение в обоих случаях, « Обозначим через 6 К граф, полученный присоединением При переходе от 5 К.( к 5 * , если 0ДИн ИЗ концов Р£ дуги _ оСк совпадает с некоторой вершиной пути ' к-\ , то в о* степень ее увеличивается на У , если Л . ваовь образованная вершина при данпом переходе, то в