push-relabel
Додано: Чет вересня 01, 2016 5:21 am
Один з алгоритмів на графах складається з двох типів операцій - push, relabel.
Передумови:
1. кожна вершина має висоту,
2. потік може йти лише згори донизу.
3. якщо ми хочемо збільшити вихідний потік з вершини і всі ребра, що йдуть від неї до нижчих вершин заповнені до їх місткості, то нам треба підняти вершину.
push - штовхає додатковий потік по ребру.
relabel - піднімає вершину
Росіяни переклали relabel як "підняття", що круто. Відповідає суті. От і питання чи варто нам взяти переклад росіян, чи є варіанти як-от "перепозначення"? У перепозначення теж є переваги, бо ми ж лише уявно підіймаємо вершини, насправді, це просто позначки на них, також це ближче до джерела.
Здається, я себе майже переконав за "перепозначення":)
Передумови:
1. кожна вершина має висоту,
2. потік може йти лише згори донизу.
3. якщо ми хочемо збільшити вихідний потік з вершини і всі ребра, що йдуть від неї до нижчих вершин заповнені до їх місткості, то нам треба підняти вершину.
push - штовхає додатковий потік по ребру.
relabel - піднімає вершину
Росіяни переклали relabel як "підняття", що круто. Відповідає суті. От і питання чи варто нам взяти переклад росіян, чи є варіанти як-от "перепозначення"? У перепозначення теж є переваги, бо ми ж лише уявно підіймаємо вершини, насправді, це просто позначки на них, також це ближче до джерела.
Здається, я себе майже переконав за "перепозначення":)