Требуется решить следующую задачу, которая вытекает из задачи построения сетевого графика.

Дан список меток ребер некоторого ориентированного ациклического графа, их весов, а также ссылок на метки других ребер - в таком случае говорят, что ребро "зависит" от других ребер. Зависимость выражается в следующем - для каждого ребра, от которого зависит данное ребро, существует путь из его конечной вершины в начальную вершину зависимого ребра. Если пути на перечисленных ребрах не существует, то добавляется ребро нулевого веса, такое чтобы путь появился.

На граф накладывается условие - в нем ровно одна вершина (исток), в которую не входят ребра и ровно одна вершина (сток), из которой ребра не выходят.

Пример исходных данных: https://prnt.sc/mv8x50

Соответствующий примеру граф: https://prnt.sc/mv8xq5

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

В примере несложно дойти до построения графа с перечисленными в исходных данных ребрами, но сложность заключается в том, как учесть непрямые связи (ребра $% 2 \rightarrow 3 $%, $%3 \rightarrow 4 $%). Вопрос - как построить такой граф?

UPD. Похоже, нашел одно из решений. Считаю, что вопрос можно оставить открытым - возможно, появятся другие интересные идеи.

задан 9 Мар '19 2:15

изменен 9 Мар '19 18:17

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×544
×239
×42

задан
9 Мар '19 2:15

показан
223 раза

обновлен
9 Мар '19 18:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru