Український відповідник для операції "push-relabel" в алгоритмі на графі

Question

Один з алгоритмів на графах складається з двох типів операцій - push, relabel.

Передумови:

1. Кожна вершина має висоту.

2. Потік може йти лише згори донизу.

3. Якщо ми хочемо збільшити вихідний потік з вершини і всі ребра, що йдуть від неї до нижчих вершин заповнені до їх місткості, то нам треба підняти вершину.

push - штовхає додатковий потік по ребру. relabel - підіймає вершину

Росіяни переклали relabel як "підняття", що круто. Відповідає суті. От і питання чи варто нам взяти переклад росіян, чи є варіанти як-от "перепозначення"? У перепозначення теж є переваги, бо ми ж лише уявно підіймаємо вершини, насправді, це просто позначки на них, також це ближче до джерела.

Answer 1

Якщо "перепозначення", то одразу виникає питання "перепозначення чого?". "Перепозначення позначки" мало допомагає, бо ще треба зрозуміти, що позначають за допомогою позначки.

З опису алгоритму:

The push–relabel algorithm uses a nonnegative integer valid labeling function which makes use of distance labels, or heights

Тобто (якщо на мить забути про термін "висота") це не просто "позначка", а "позначка відстані", і "re-label", на мою думку, — просто бажання скоротити задовге "recalculating distances/heights".

Надалі опис продовжує вживати "height" (до прикладу, на схемі позначка має літеру "h"). Ба більше, на відеолекціях я бачу, як викладач пропонує буквально уявляти висоту як умовну третю координату графу. Якщо залишити це поняття, але прибрати близьке за змістом "підняти", це дуже зашкодить аналогії, а отже і розумінню всього процесу.

Answer 2

1. Перепозначення перевантажене префіксами.

2. Перемаркувати або перемітити видаються кращими, але префікс пере- робить похідне слово в півтори-два рази довшим.

3. Аналогія з потоком води (наприклад, англійською тут), наводить на роздуми про гідротехнічні споруди. Якщо не хочеться банально повторюватися за росіянами, то push-relabel можна перекласти як штовхнути-підгатити.