Дискретная математика и теория графов

ИДЗ

ИДЗ по бинарным отношениям

Пояснение к заданию 4. Эффективный алгоритм топологической сортировки мы узнаем позже. Пока требуется сделать топологическую сортировку максимально простым методом. Если вы поняли, что ваше отношение — это отношение частичного порядка, значит, алгоритм топологической сортировки применим, и с его помощью вы можете дополнить свое отношение до отношения полного (линейного) порядка. На самом деле, алгоритм топологической сортировки может быть применим и в других случаях. Чтобы понять, применим или нет, просто начните его выполнять.

  1. Найдите «минимальный» элемент отношения, это элемент x, который не входит в отношение ни с одним другим, другими словами, $\forall y\ne x$ неверно, что $x\,R\,y$. Еще более простыми словами, минимальный элемент — это тот элемент, из которого в графе отношения не выходит ни одного ребра в другие элементы.
  2. Поместите минимальный элемент в ответ и удалите из отношения. Если вы проделываете все действия на графе, удалите вершину из графа и все связанные с ней ребра.
  3. Снова найдите минимальный элемент и снова припишите его в ответ.
  4. Продолжайте искать и приписывать в ответ минимальные элементы, пока не выпишите все элементы исходного отношения.
  5. Если вы будете проделывать это действие не с отношением частичного порядка, скорее всего возникнет ситуация, что вы не можете выбрать минимальный элемент — из всех элементов выходят ребра. Это значит, что алгоритм не применим к вашему отношению.
  6. Ответ — это последовательность элементов исходного отношения, от минимального к максимальному.