Изменения

<tex>G = (V, E)</tex> {{- --}} [[Определение сети, потока#Определение сети|сеть]] с истоком <tex>s</tex> и стоком <tex>t</tex>, <tex>f</tex> {{--- }} [[Метод проталкивания предпотока#Определения|предпоток]] в <tex>G</tex>, <tex>h</tex> {{--- }} [[Метод проталкивания предпотока#Определения|функция высоты]].

'''Допустимое ребро (admissible edge)''' {{- --}} ребро <tex>uv</tex>, у которого <tex>c_{f}(u, v) > 0</tex> и <tex>h(u) = h(v) + 1</tex>. В противном случае <tex>uv</tex> называется '''недопустимым (inadmissible)'''.

'''Допустимая сеть (admissible network)''' {{--- }} сеть <tex>G_{f, h} = (V, E_{f, h})</tex>, где <tex>E_{f, h}</tex> {{--- }} множество допустимых ребер.}} {{Лемма|id = Лемма1|about = Допустимая сеть является ациклической|statement =Если <tex>G = (V, E)</tex> {{---}} сеть с истоком <tex>s</tex> и стоком <tex>t</tex>, <tex>f</tex> {{---}} предпоток в <tex>G</tex>, а <tex>h</tex> {{---}} функция высоты, тогда допустимая сеть <tex>G_{f, h} = (V, E_{f, h})</tex> является ациклической.|proof =Пусть в <tex>G_{f, h}</tex> существует [[Основные определения теории графов|циклический путь]] <tex>p = \left \langle v_0, v_1, \dots, v_k \right \rangle</tex>, где <tex>k > 0</tex>.  <tex> ~ ~ h(v_{i - 1}) = h(v_{i}) + 1</tex> для <tex>i = 1, 2, \dots, k</tex>, так как каждое ребро данного пути допустимое. Просуммировав равенства вдоль циклического пути, получаем: <tex>\sum \limits_{i = 1}^{k} h(v_{i - 1}) = \sum \limits_{i = 1}^{k} (h(v_{i}) + 1) = \sum \limits_{i = 1}^{k} h(v_{i}) + k</tex> Так как каждая вершина циклического пути <tex>p</tex> встречается при суммировании по одному разу это значит то, что <tex>k = 0</tex>, что противоречит первоначальному предположению. Значит, допустимая сеть является ациклической.