Правило Фалкерсона

@AndreyCAD · Регистрация: 09.03.2022

Студворк — интернет-сервис помощи студентам

Здравствуйте. Мне дано задание: Требуется разработать программу топологической сортировки объектных модулей произвольного проекта для формирования из них однопроходной библиотеки на основе известной структуры для связей управления. Исходная информация о структуре проекта должна определять отношение частичного порядка, которое перечисляет все пары модулей, зависимых по передаче управления. Программа топологической сортировки должна превращаться исходный частичный порядок модулей проекта в результирующий линейный по алгоритму, реализующему правило Фалкерсона.

Я не совсем понимаю, зачем тут правило Фалкерсона? Как оно может упорядочить? Или я ошибаюсь, и правило Форда-Фалкерсона и правило Фалкерсона не одно и то же?

@lemegeton · 11.11.2022, 22:43

Сообщение от AndreyCAD

правило Фалкерсона

А что такое правило Фалкерсона? Я с таким не сталкивался.
Даже всезнающий гуголь не хочет признаваться.

@AndreyCAD · 12.11.2022, 00:48 **[ТС]**

lemegeton, если поискать "Fulkerson's rule", то находит совпадения на английском и звучит это правило не как алгоритм Форда-Фалкерсона, но я все еще не могу понять, как мне именно его использовать(

@TheCalligrapher · 13.11.2022, 00:48

Сообщение от AndreyCAD

Я не совсем понимаю, зачем тут правило Фалкерсона?

"Правило Фалкерсона" - это согласно [каким-то неавторитетным] англоязычным источникам, просто естественное правило нумерации для топологической сортировки. Сначала нумеруем узлы без входящих дуг, мысленно удаляем их вместе c их исходящими дугами, повторяем... И т.д.

Правило Фалкерсона, в отличие об каких-нибудь абстрактных алгоритмов топологической сортировки (вроде DFS), навязывает обработку "широком фронтом", то есть интуитивно старается нарезать сеть на "слои" независимых узлов (например, для того, чтобы параллелизовать обработку независимых узлов в сети заданий).

@AndreyCAD · 14.11.2022, 00:03 **[ТС]**

Спасибо за ответ. Нашел описание правила Фалкерсона в книге А.Т. Берзтисса "Структуры данных" 1974 г.
Звучит оно так:
X - множество вершин, занумерованных на некотором частном этапе применения описываемого алгоритма к ацикличному орографу.
1) Положить i = 1.
2)Если нет ненумерованных вершин со степенью захода, равной нулю, то перейти к 5.
3)Присвоить номер i нумерованной вершине со степенью захода, равной нулю.
4)Положить i = i + 1; перейти к 2.
5)Если все вершины перенумерованы, восстановить все вычеркнутые дуги; конец.
6)Если od (X) != 0, вычеркнуть все дуги исходящие из Х, и перейти к 2.
7)Ошибочная ситуация: одновременное наличие ненумерованной вершины и od(X)=0 означает существование цикла в сети.

@EU2 · 01.12.2022, 14:03

AndreyCAD, Ты сделал по итогу, можешь дать глянуть ?

Новые блоги и статьи Все статьи Все блоги /
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .

@AndreyCAD 0 / 0 / 0 Регистрация: 09.03.2022 Сообщений: 5

	Правило Фалкерсона 11.11.2022, 22:08. Показов 1587. Ответов 5 Метки алгоритмы c++, графы, сортировка (Все метки) Здравствуйте. Мне дано задание: Требуется разработать программу топологической сортировки объектных модулей произвольного проекта для формирования из них однопроходной библиотеки на основе известной структуры для связей управления. Исходная информация о структуре проекта должна определять отношение частичного порядка, которое перечисляет все пары модулей, зависимых по передаче управления. Программа топологической сортировки должна превращаться исходный частичный порядок модулей проекта в результирующий линейный по алгоритму, реализующему правило Фалкерсона. Я не совсем понимаю, зачем тут правило Фалкерсона? Как оно может упорядочить? Или я ошибаюсь, и правило Форда-Фалкерсона и правило Фалкерсона не одно и то же? 0

@AndreyCAD 0 / 0 / 0 Регистрация: 09.03.2022 Сообщений: 5
	12.11.2022, 00:48 [ТС]
	lemegeton, если поискать "Fulkerson's rule", то находит совпадения на английском и звучит это правило не как алгоритм Форда-Фалкерсона, но я все еще не могу понять, как мне именно его использовать( 0

@AndreyCAD 0 / 0 / 0 Регистрация: 09.03.2022 Сообщений: 5
	14.11.2022, 00:03 [ТС]
	Спасибо за ответ. Нашел описание правила Фалкерсона в книге А.Т. Берзтисса "Структуры данных" 1974 г. Звучит оно так: X - множество вершин, занумерованных на некотором частном этапе применения описываемого алгоритма к ацикличному орографу. 1) Положить i = 1. 2)Если нет ненумерованных вершин со степенью захода, равной нулю, то перейти к 5. 3)Присвоить номер i нумерованной вершине со степенью захода, равной нулю. 4)Положить i = i + 1; перейти к 2. 5)Если все вершины перенумерованы, восстановить все вычеркнутые дуги; конец. 6)Если od (X) != 0, вычеркнуть все дуги исходящие из Х, и перейти к 2. 7)Ошибочная ситуация: одновременное наличие ненумерованной вершины и od(X)=0 означает существование цикла в сети. 0

@EU2 0 / 0 / 0 Регистрация: 16.11.2022 Сообщений: 1
	01.12.2022, 14:03
	AndreyCAD, Ты сделал по итогу, можешь дать глянуть ? 0

Правило Фалкерсона

Решение