338
правок
Изменения
м
→Допустимые ребра
{{Определение
|definition=
'''Допустимое ребро (admissible edge)''' {{---}} ребро <tex>uv</tex>, у которого <tex>c_{f}(u, v) > 0</tex> и <tex>h([u) ] = h([v) ] + 1</tex>. В противном случае <tex>uv</tex> называется '''недопустимым (inadmissible)'''.
}}
Пусть в <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>
