О нумерациях конечных частично упорядоченных множеств

Размещено на http://www.allbest.ru/

РЕФЕРАТ

О НУМЕРАЦИЯХ КОНЕЧНЫХ ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВ

Широко известна проблема линейного упорядочивания частично упорядоченных множеств (Linear Ordering Problem). Она сводится к нахождению нумераций таких множеств. Обобщение одного из известных результатов С.С. Кислицына, связанного с нахождением числа нумераций конечных частично упорядоченных множеств

There is a widely known problem regarding the ordering of the partially ordered sets (Linear Ordering Problem). It boils down to finding the numerations of such sets. The main result of this article is a generalization of one of the known S. S. Kislitsyn's results about finding the number of numerations of finite partially ordered sets

Известные понятия и обозначения теории бинарных отношений и теории групп, например, из источников [1-3]. В работах [4-5] рассматриваются частично упорядоченные множества и соответствующие им множества перестановок (нумераций), указывается алгоритм вычисления количества нумераций. Задача нахождения таких нумераций и определения их количества непосредственно связана с известной проблемой линейного упорядочивания множеств [6] и с близкими к этой проблеме вопросами [7-8].

Основным результатом статьи является теорема, обобщающая один из результатов С.С. Кислицына [5], из которой следует ещё один новый способ определения числа нумераций данного конечного частично упорядоченного множества. нумерация частичный упорядоченный множество

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

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

Теперь введём некоторые новые понятия, необходимые для формулировки основного результата статьи. Пусть и - попарно различные числа из . Матрицу, стоящую на пересечении строк и столбцов матрицы с номерами , обозначаем и называем блоком k-го порядка матрицы на рядах . Ясно, что если , то , т.е. . При блок -го порядка на рядах отличных от назовём дополнительным блоком к блоку и обозначим через . Ясно, что при имеем . Блок назовём блоком с полными столбцами (строками), если при число единиц в -ом столбце (в -ой строке) матрицы равно числу единиц в -ом столбце (-ой строке) этого блока. Ясно, что блок имеет полные столбцы и строки. Оказывается, удобно ввести понятие "пустого блока" (блока нулевого порядка) и считать его блоком с полными столбцами и строками. Пустой блок и блок будем называть тривиальными блоками матрицы .

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

Утверждение 1. Если блок -го порядка матрицы из ( и ) имеет полные столбцы (строки), то дополнительный к нему блок -го порядка имеет полные строки (столбцы).

Утверждение 2. Пусть , где Если блок имеет полные столбцы (строки), то блок тоже имеет полные столбцы (строки).

Утверждение 3. Пусть , где . Если - блок с полными столбцами (строками), то существует подстановка такая, что матрица представима в виде , где - дополнительный блок к блоку в и - нулевая матрица подходящих размеров.

Отметим, что получается так: возьмём наборы и , которые удовлетворяют условиям , где , и , где , а затем положим .

Далее, согласно [5] перестановку символов из называют нумерацией частичного упорядоченного множества с частичным порядком , если из следует для всех . Число нумераций такого частично упорядочиваемого множества обозначают . Понятно, что нумерацией этого частично упорядоченного множества также можно назвать подстановку . Другими словами, подстановку назовём нумерацией для частичного порядка на , если из следует для всех . Имеет место

Утверждение 4. Пусть и - частичный порядок на . Если является нумерацией для , то является нумерацией для .

Доказательство. Предположим, что для некоторых имеем , т.е. . Тогда , т.е. . Так как - нумерация для , то и . Последнее и означает, что - нумерация для .

Утверждение 5. Подстановка является нумерацией для частичного порядка тогда и только тогда, когда матрица имеет верхнетреугольный вид.

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

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

Утверждение 6. Пусть - частичный порядок и . Тогда для любого блока -го порядка матрицы , имеющего полные столбцы или полные строки, бинарное отношение , для которого , тоже является частичным порядком.

Доказательство. Пусть - блок с полными столбцами. Согласно утверждению 3 существует перестановка такая, что . Так как и - тоже частичный порядок на , то на главной диагонали матрицы стоят единицы (рефлексивность) и недиагональные симметричные относительно неё элементы в произведении дают нуль (антисимметричность). Ясно, что тогда матрица тоже удовлетворяет этим условиям. Поэтому отношение на с матрицей является рефлексивным и антисимметричным. Далее, замечаем, что . Так как - транзитивное и рефлексивное отношение, то места расположения нулей у матриц и одни и те же, а, значит, у матриц и также выполнено это условие. Поэтому - тоже транзитивное отношение, т.е., окончательно, - частичный порядок на .

Аналогично доказывается в случае, когда - блок с полными строками. Утверждение доказано.

Отметим, что если - блок -го порядка матрицы частичного порядка , имеющий полные столбцы, то по утверждению 1 дополнительный блок -го порядка имеет полные строки, причём по утверждению 6 существуют частичные порядки и , матрицы которых соответственно равны и . Имеет место

Утверждение 7. Пусть - частичный порядок на , , - блок с полными столбцами, - дополнительный блок к в , , , и - частичные порядки соответственно на и с матрицами и . Если подстановка является нумерацией для и подстановка - нумерацией для , то подстановка является нумерацией для .

Доказательство. Пусть для некоторых имеем , т.е. . Так как , то рассмотрим случаи:

;

;

и ;

и .

В случае 1) найдутся такие, что и . Тогда . Но - нумерация для , поэтому и , т.е. .

В случае 2) найдём , для которых и . Тогда . Т.к. - нумерация для , то и . Откуда получаем .

В случае 3) при имеем , а при имеем , то есть, как и в случаях 1) и 2) получаем .

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

Основным результатом статьи является следующая

Теорема. Пусть - отношение частичного порядка на множестве ; - все блоки -го порядка матрицы , имеющие полные столбцы, и - их соответствующие дополнения. Если и - отношения частичных порядков соответственно на множествах и такие, что и при , то

(1)

Прежде, чем перейти к доказательству теоремы, сделаем некоторые замечания к её формулировке.

В формулировке теоремы условие полноты столбцов для блоков в силу утверждения 1 можно заменить на условие полноты их строк.

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

Существование отношений частичного порядка на и на , для которых и следует из рассуждений, проведённых перед формулировкой утверждения 7.

Если использовать ранее введённое понятие "пустого блока" (блока нулевого порядка), считая, что он имеет полные столбцы и полные строки, а также число нумераций соответствующего ему частичного порядка равно 1, то в формулировке теоремы очевидно можно было бы снять ограничения и (просто положить, что и ).

Доказательство теоремы. Так как - частичный порядок на , то по известной теореме [2, теорема 4, стр. 49] существует нумерация для . Согласно утверждению 5, матрица имеет верхнетреугольный вид. Блок матрицы , стоящий на рядах , имеет полные столбцы, а значит блок матрицы согласно утверждению 2 тоже имеет полные столбцы. Мы показали, что матрица имеет блок -го порядка с полными столбцами, что и аргументирует ранее сделанное замечание 2. Продолжаем свои рассуждения относительно произвольной нумерации для . Пусть - дополнительный блок к в . Ясно, что . Согласно замечанию 3 существуют частичные порядки и соответственно на и на такие, что и . Далее, существуют такие перестановки символов из и символов из , что и . Теперь положим при и при . Тогда и . В силу того, что и имеем . Такая запись нумерации для совпадает с записью в формулировке утверждения 7. Покажем, что подстановки и являются нумерациями для и для соответственно. Действительно, если , где , то в силу имеем (учитываем, что ), а, значит, . Но - нумерация для , поэтому , т.е. и . Это и означает, что - нумерация для . Аналогично показывается, что - нумерация для .

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

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

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

В статье Кислицына С. С. [5] приводится формула, позволяющая находить число нумераций частично упорядоченного множества ( - некоторый частичный порядок на конечном множестве ):

(2)

где - множество минимальных элементов в , и - в наших терминах число нумераций частичного порядка на и число нумераций ограничения частичного порядка на . Ясно, что при мы получаем эту формулу из теоремы при . Аналогичная двойственная формула, упоминаемая в [5], вида

(3)

где - множество максимальных элементов в , следует из доказанной теоремы при .

Таким образом, теорема обобщает указанные формулы (2) и (3) из [5]. Скажем несколько слов о возможных обозначениях числа частично упорядоченного множества . В [5] используется обозначение , хотя понятно, что строже было бы обозначение, например, . У нас в работе - это одно из множеств для некоторых . На этом множестве может быть определён и другой частичный порядок, например . Тогда имеем два частично упорядоченных множества и , различающиеся не основным множеством , а и . Вот почему, по-видимому, обозначения и для числа нумераций этих частично упорядоченных множеств являются более строгими (хотя не обязательно более удобными).

С учётом определённости вида множества можно ввести ещё одно удобное обозначение числа нумераций частично упорядоченного множества - это , где - матрица отношения .

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

Теорема (вторая формулировка).

Пусть - частичный порядок на с матрицей ; - все блоки -го порядка матрицы с полными столбцами и - их соответствующие дополнения. Тогда

(4)

В работе [5], также как и в нашей работе, используются различные обозначения для числа нумераций.

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

В заключение отметим, что теорема во второй формулировке достаточно легко позволяет с использованием формулы (4) построить алгоритм расчёта числа , где - матрица некоторого частичного порядка на .

Используя такой алгоритм, нам до доказательства теоремы удалось компьютерно проверить истинность соответствующей гипотезы при .

Литература

1. Белоусов А. И., Ткачёв С. Б. Дискретная математика / под редакцией В. С. Зарубина, А. П. Крищенко, М., 2001.

2. Биркгоф Г., Барти Т. Современная прикладная алгебра. М., 1976.

3. Каргополов М. И., Мерзляков Ю. И. Основы теории групп. Спб., 2009.

4. Кислицын С. С. Частично упорядоченные множества и k-расщепляемость / Сибирский математический журнал, Т. 8, №5, 1967, с. 1197-1201.

5. Кислицын С. С. Конечные частично упорядоченные множества и соответствующие им множества перестановок / Математические заметки, т. 4, №5, 1968, с. 511-518.

6. Roy T. Search and learning for the linear ordering problem with an application to machine translation / PhD thesis, Johns Hopkins University, 2009.

7. Титов Г. Н. О некоторых критериях триангулируемости матрицы / Вестник Армавирской государственной педагогической академии. Естественные и технические науки, №5, 2011, с. 89-92.

8. Титов Г. Н. Критерий принадлежности бинарного отношения отношению частичного порядка / Известия Кубанского государственного университета. Естественные науки, В. 1, 2012, с. 2-6.

Размещено на Allbest.ru