поток в графах
Смотреть что такое "поток в графах" в других словарях:
Поток в графе — Потоком в сети S из вершины s в вершину t называют функцию (где E множество дуг графа S) т.ч. выполнены условия баланса и допустимости. Условие баланса: Условие допустимости … Википедия
Транспортная сеть — В теории графов транспортная сеть ориентированный граф , в котором каждое ребро имеет неотрицательную пропускную способность и поток . Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из … Википедия
Алгоритм Форда–Фалкерсона — решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством… … Википедия
Алгоритм проталкивания предпотока — решает задачу нахождения максимального потока в транспортной сети. Алгоритм не является частным случаем алгоритма Форда Фалкерсона. Реализованный без специальных усовершенствований, алгоритм выполняется за время . Некоторые усовершенствования ещё … Википедия
Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году израильским (бывшим русским) учёным Ефимом Диницем. Временная сложность алгоритма составляет . Получить такую оценку позволяет введение… … Википедия
Алгоритм Форда — У этого термина существуют и другие значения, см. Алгоритм Форда. Алгоритм Форда Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается… … Википедия
основная — 3.2 основная общеобразовательная школа: Школа, организуемая как самостоятельное общеобразовательное учреждение с 1 по 9 класс включительно. Источник: ТСН 31 328 2004: Общеобразовательные школы. Республика Саха (Якутия) Смотри также родственные… … Словарь-справочник терминов нормативно-технической документации
Задача о максимальном потоке — Максимальный поток в транспортной сети. Числа обозначают потоки и пропускные способности. В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сум … Википедия
Алгоритм Малхотры — Алгоритм Малхотры Кумара Махешвари позволяет находить максимальный поток в графе. Описание Рассматривается транспортная сеть, состоящая из ориентированного графа , где множество вершин, множество рёбер, и потока . Для… … Википедия
Алгоритм Эдмондса — Алгоритм Эдмондса Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда Фалкерсона и работает за время . Впервые был опубликован в 1970 году советским учёным Е … Википедия
Boost (библиотека) — Boost Тип библиотека (программирование) Написана на С++ Операционная система Кроссплатформенный Последняя версия Boo … Википедия
