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

Как построить вум по такому графу?

задан 15 Сен 13:58

10|600 символов нужно символов осталось
1

Граф из условия задачи задаёт строгий частичный порядок на множестве вершин. При этом v < w означает, что из v в w выходит стрелка.

Известно, что любой частичный порядок на множестве можно продолжить до линейного. На форуме об этом не один раз говорилось, но имеет смысл дать явное описание. Прежде всего, надо сделать оговорку, что граф конечен -- в противном случае само утверждение неверно. На конечном множестве всякий линейный порядок является полным, что очевидно (любое непустое подмножество имеет наименьший элемент ввиду конечности).

Для каждой вершины v будем рассматривать все исходящие из них пути по стрелкам. Ввиду ацикличности, в таком пути не могут повторяться вершины. Поэтому все эти пути имеют ограниченную длину. В частности, среди них есть самый длинный. Его длину назовём рангом вершины v. При этом ранг 0 будут иметь те и только те вершины, из которых не исходят стрелки. Ранг 1 приобретут те вершины, из которых стрелки исходят, но только в вершины ранга 0. Из вершин ранга 2 все стрелки идут в вершины меньшего ранга (1 или 0), причём хотя бы одна стрелка ведёт в вершину ранга 1, и так далее.

Легко видеть, что если из v и w идёт стрелка, то ранг v строго больше ранга w. В самом деле, если самый длинный путь из w имеет длину d, то из v имеется путь длиной как минимум d+1, то есть ранг v строго больше d -- ранга w.

Теперь расположим в произвольном порядке вершины максимального ранга, затем то же сделаем со следующим рангом, и так далее, и в конце пойдут вершины ранга 0 в произвольном порядке. Это линейный порядок, и он продолжает исходный, так как если v < w, то ранг v больше ранга w, и в списке v встретится раньше.

ссылка

отвечен 15 Сен 23:57

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×548
×2

задан
15 Сен 13:58

показан
36 раз

обновлен
15 Сен 23:57

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

по почте:

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

по RSS:

Ответы

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

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