Картинки из квадратов \ Теоретико-множественная математика \ Theoretical Computer Science \ Теория синтаксического анализа, перевода и компиляции. Том 1. (А. Ахо, Дж. Ульман; 1978) \ Предварительные математические сведения \ Некоторые понятия теории графов \

9.7.6.02.5.6. Вложение
частичного порядка в линейный

Начало см. здесь и здесь.
Ахо А., Ульман Дж.
Теория синтаксического анализа, перевода и компиляции. Том 1.
Пер. с англ. М.: Мир 1978, cc. 59 — 60.
Определение частичных порядков см. здесь.
Определение линейных порядков см. здесь.

Определение ациклических графов см. здесь.

Определение вложенности (включения) отношений (в частности, отношений порядка) см. у Ю. А. Шрейдера здесь.
Рассуждение, изложенное в разделе "Метод" данного алгоритма, основано на Теореме 4.2. у Ю. А. Шрейдера; см. ее здесь.
Определение операций над отношениями (в частности, над отношениями порядка) см. у Ю. А. Шрейдера здесь.


Вопросы индукции по ациклическим графам разбираются здесь.
К началу данной страницы
Картинки из квадратов \ Теоретико-множественная математика \ Theoretical Computer Science \ Теория синтаксического анализа, перевода и компиляции. Том 1. (А. Ахо, Дж. Ульман; 1978) \ Предварительные математические сведения \ Некоторые понятия теории графов \