Топологическая сортировка, подпоследовательности

[mich137]

Если в топологически отсортированной последовательности вершин графа взять подпоследовательность и переставить элементы подпоследовательности с сохранением топологического порядка в подпоследовательности, будет ли полная новая последовательность топологически отсортированной?

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

[Zealint]

Для начала я бы на Вашем месте строго определил все действия, которые совершаются над графом в момент взятия подпоследовательности и установки её обратно.

Например, я не понимаю, как будет работать такой случай. Граф из 3 вершин {1,2,3} и двух рёбер {(1,2), (2,3)}. Топологическая сортировка будет (1,2,3). Заберём вершины 1 и 3. Они не связаны ребром, потому переставим их местами (не нарушая ИХ топологическую упорядоченность). Ставим обратно, получаем (3,2,1) - но это уже не отсортированные топологически вершины в исходном графе.

Однако возможно, Вы что-то другое имели в виду под операцией взятия и сортировки подпоследовательности.

[mich137]

Да, я не упомянул, что подпоследовательность непрерывная. Пусть a_1, ..., a_r,..., a_s, ..., a_n --- топологически упорядоченная последовательность вершин упорядоченного графа без циклов. Рассмотрим подпоследовательность a_r, a_{r+1}, ..., a_s. Пусть b_r, ..., b_s --- какая-либо перестановка элементов a_r, ..., a_s, которая также является топологически упорядоченной. Можно ли тогда утверждать, что последовательность a_1,..., a_{r-1}, b_r, ..., b_s, a_{s+1}, ..., a_n будет топологически упорядоченной?

Мне казалось, что это довольно просто --- прямо применяем определение: последовательность топологически упорядочена, если для любого ребра (xy) элемент x находится в последовательности перед элементом y. Простой перебор случаев, и ответ оказывается положительным. Но хотелось бы уточнить, не пропустил ли я чего-нибудь.

[Zealint]

mich137 в сообщении #531231 писал(а):

Но хотелось бы уточнить, не пропустил ли я чего-нибудь.

Я не вижу того, почему это может оказаться неправильным. Действительно, удалили часть элементов из начала с рёбрами, которые идут в середину последовательности, потом удалили часть элементов из конца с рёбрами, которые идут в них из середины. Перетасовали середину. Добавили удалённые вершины обратно с теми же рёбрами, которые по-прежнему идут упорядоченно. Не вижу глюков...

mich137 в сообщении #531231 писал(а):

подпоследовательность непрерывная

Когда будете кому-то ещё рассказывать про это, придумайте другое слово вместо "непрерывная". Последовательность у Вас всегда будет дискретной - и непрерывной быть не может в принципе. Элементы, которые вы выбираете обычно называют "подряд идущими". Может есть ещё какие-то названия.