Применение поиска контуров в оргафах

[Грымзик]

Может не совсем по месту пишу, но ОЧЕНЬ СРОЧНО!!! Кто-нибудь знает
примеры практических задач, для решения которых требуется выделение контуров в орграфе?

[Сомик]

Думаю, что в задаче коммивояжера(ориентрировааной), если вы можите как то эффекивно перебирать котнуры и определять их дины.

[Yuri Gendelman]

Грымзик писал(а):

Может не совсем по месту пишу, но ОЧЕНЬ СРОЧНО!!! Кто-нибудь знает
примеры практических задач, для решения которых требуется выделение контуров в орграфе?

* Узлы графа - фирмы.
* Дуга - долг одной фирмы другой; вес дуги - сумма долга.
* Задача: найти все цепочки взаимно погашаемых долгов. Критерий оптимальности - максимальная сумма списываемых долгов.

Во времена банковского кризиса начала 90-х задача была очень даже актуальной.

[abc_qmost]

Грымзик писал(а):

Может не совсем по месту пишу, но ОЧЕНЬ СРОЧНО!!! Кто-нибудь знает
примеры практических задач, для решения которых требуется выделение контуров в орграфе?

Есть неплохая книга В. Липского "Комбинаторика для программистов". Думаю, что Вы найдете там все, что Вас интересует.

[abc_qmost]

Еще могу привести один конкретный пример. В свое время принимал участие в проекте по расчету токов короткого замыкания (в реальной сети происходит короткое замыкание). Отвечал за математику. Использовал модель орграфов. Дуги являлись всяческими активными и пассивными элементами. Там возникала еще одна интересная задача - решение СЛАУ на орграфах. СЛАУ являются разреженными и для их решения используютс особые методы (см. книгу С. Писсанецки "Технология разреженных матриц").

[VLarin]

А у меня следующий пример:)))
Может уже и поздно, но все равно:)
Расчет полей. Геометрия задана набором точек и набором соединяющих их векторов (линий и арок), по сути тот самый орграф и есть.
Требуется из заданного набора векторов, являющихся по сути сегментами границ подобластей, определить подобласти и ограничивающие их границы.
Решал последовательным поиском контуров в орграфе (с их последующим удалением из графа).