14

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

Передумови:

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

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

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

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

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

3

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

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

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"). Ба більше, на відеолекціях я бачу, як викладач пропонує буквально уявляти висоту як умовну третю координату графу. Якщо залишити це поняття, але прибрати близьке за змістом "підняти", це дуже зашкодить аналогії, а отже і розумінню всього процесу.

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.