О некоторых подграфах графа бинарных отношений Аль Джабри Халид Шиа Хайралла

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Аль Джабри Халид Шиа Хайралла . О некоторых подграфах графа бинарных отношений: диссертация ... кандидата Физико-математических наук: 01.01.06 / Аль Джабри Халид Шиа Хайралла ;[Место защиты: Институт математики и механики им. Н.Н. Красовского Уральского отделения Российской академии наук].- Екатеринбург, 2016.- 80 с.

Содержание к диссертации

Введение

Глава 1. Граф бинарных отношений 18

1. Диаметр графа бинарных отношений 18

2. Граф частичных порядков 30

3. Опорные множества графа частичных порядков 35

Глава 2. Граф рефлексивно-транзитивных отношений и граф конечных топологий 44

4. Граф рефлексивно-транзитивных отношений 44

5. Граф конечных топологий 50

Глава 3. Граф ациклических отношений (ациклических орграфов) .57

6. Граф ациклических отношений 57

7. Опорные множества графа ациклических отношений 63

Заключение 73

Литература 75

Граф частичных порядков
Опорные множества графа частичных порядков
Граф конечных топологий
Опорные множества графа ациклических отношений

Введение к работе

Актуальность темы. Среди нерешенных задач перечисления графов одной из сложнейших является задача перечисления транзитивных орграфов, эквивалентная задаче перечисления конечных помеченных топологий. Последовательность {Т(п)}, где Т{п) — это количество всех помеченных топологий, определенных на конечном множестве из п элементов, подвергалась изучению с разных точек зрения. Сделан ряд¹,²,³ попыток вычисления Т(п) для малых п (благодаря разработке эффективных алгоритмов⁴ в настоящее время известны значения Т{п) для п ^ 18); изучалось асимптотическое поведение⁵,⁶ последовательности {Т(п)}; исследована периодичность вычетов числа конечных помеченных топологий⁷; в независимых работах⁸,⁹ получены соотношения рекуррентного характера между отдельными классами конечных топологий, анализ которых привел к появлению графа бинарных отношений («графа графов»).

Одним из направлений перечисления конечных топологий является ис-

¹Comtet L. Recouvrements, bases de filtre et topologies d’un ensemble fini // C. R. Acad. Sci. 1966. Vol. AB262. P. A1091-A1094.

2Das S.K. A machine representation of finite To topologies // J. Assoc. Comput. Mach. 1977. Vol. 24. № 4. P. 676-692.

³Боревич З.И. К вопросу перечисления конечных топологий // Зап. научн. сем. ЛОМИ. 1977. Т. 71. С. 47-65.

⁴Brinkmann G., McKay B.D. Posets on up to 16 points // Order. 2002. Vol. 19. № 2. P. 147-179.

⁵Kleitman D.J., Rothschild B.L. Asymptotic enumeration of partial orders on a finite set // Trans. Amer. Math. Soc. 1975. Vol. 205. P. 205-220.

⁶Finch S. Transitive relations, topologies and partial orders // 2003. Published electronically at

⁷Боревич З.И. О периодичности вычетов числа конечных помеченных топологий // Зап. научн. сем. ЛОМИ. 1980. Т. 103. С. 5-12.

⁸Родионов В.И. Об одном соотношении в конечных топологиях // Зап. научн. сем. ЛОМИ. 1980. Т. 103. С. 114-116.

⁹Erne M. On the cardinalities of finite topologies and the number of antichains in partially ordered sets // Discrete Mathematics. 1981. Vol. 35. P. 119-133.

следование совокупности чисел {То(п,А;)}, где То(п,к) — это количество То-топологий, определенных на множестве из п элементов и имеющих ровно к открытых множеств. Истоки этих исследований заложены в работах¹⁰'¹¹. Отметим некоторые работы современных авторов¹²'¹³'¹⁴'¹⁵, где исследуется распределение количества открытых множеств в диапазоне от п +1 до 2^П. Ряд ученых исследовали конечные непомеченные топологии¹⁶'¹⁷'¹⁸ и группы автоморфизмов конечных топологий¹⁹.

К тематике тесно примыкает родственная задача перечисления ациклических орграфов того или иного частного вида²⁰'²¹. Настоящая работа посвящена изучению графа бинарных отношений, содержащего не только

¹⁰Sharp H., Jr. Cardinality of finite topologies // Journal of Combinatorial Theory. 1968. Vol. 5. P. 82-86.

¹¹Stanley R.P. On the number of open sets of finite topologies // Journal of Combinatorial Theory. Series A. 1971. Vol. 10. P. 74-79.

¹²Benoumhani M., Kolli M. Finite topologies and partitions // Journal of Integer Sequences. 2010. Vol. 13. Article 10.3.5.

¹³Kolli M. On the cardinality of the To topologies on a finite set // International Journal of Combinatorics. 2014. Vol. 2014. Article ID 798074, 7 pages.

¹⁴Ragnarsson K., Tenner B.E. Obtainable sizes of topologies on finite sets // Journal of Combinatorial Theory. Series A. 2010. Vol. 117. P. 138-151.

¹⁵Величко И.Г., Стеганцева П.Г., Башова Н.П. Перечисление топологий близких к дискретной на конечных множествах // Известия вузов. Математика. 2015. № 11. С. 23-31.

¹⁶Erne M. The number of partially ordered sets with more points than incomparable pairs // Discrete Mathematics. 1992. Vol. 105. P. 49-60.

¹⁷Pfeiffer G. Counting transitive relations // Journal of Integer Sequences. 2004. Vol. 7. Article 04.3.2.

¹⁸Brinkmann G., McKay B.D. Counting unlabelled topologies and transitive relations // Journal of Integer Sequences. 2005. Vol. 8. Article 05.2.1.

¹⁹Kim D., Kwon Y.S., Lee J. Enumerations of finite topologies associated with a finite graph // Kyungpook Math. J. 2012.

²⁰Stanley R.P. Acyclic orientations of graphs // Discrete Mathematics. 2006. Vol. 306. № 10-11. P. 905-909.

²¹Liskovets V.A. More on counting acyclic digraphs // arXiv: 0804.2496v1 [math.CO]. 2008.

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

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

Методы исследований. В работе применяются общие методы теории множеств, комбинаторного анализа, теории графов, алгебры и топологии. Основной технический аппарат — классификация бинарных отношений на отдельные классы и исследование их комбинаторных и иных свойств.

Научная новизна. В работе получены следующие новые научные результаты. Определен основной объект исследований — граф бинарных отношений, и доказано, что диаметр нетривиального графа равен 2. Показано, что если одно из смежных отношений графа является частичным порядком, то и другое — частичный порядок. Получена явная формула для числа связных компонент графа частичных порядков. Показано, что если одно из смежных отношений графа является рефлексивно-транзитивным отношением, то и другое отношение — рефлексивно-транзитивное. Получена явная формула для числа связных компонент графа конечных топологий. Показано, что если одно из смежных отношений графа является ациклическим отношением, то и другое отношение — ациклическое. Получена явная формула для числа связных компонент графа ациклических отношений.

Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты и методы могут быть использованы при дальнейшем изучении строения графа бинарных отношений. Наибольшие перспективы имеет исследование структурных свойств опорных множеств различных семейств бинарных отношений.

Апробация работы. Основные результаты работы представлены на:

- XLI итоговой студенческой научной конференции (Ижевск, Удмуртский государственный университет, 2013);

45-й Международной молодежной школе-конференции «Современные проблемы математики и её приложений» (Екатеринбург, Институт математики и механики УрО РАН, Уральский федеральный университет, 2014);

Всероссийской конференции с международным участием «Теория управления и математическое моделирование» (Ижевск, Удмуртский государственный университет, 2015);

Российской научной конференции «Алгебра, анализ и смежные вопросы математического моделирования» (Владикавказ, Северо-Осетинский государственный университет, 2015);

International conference «Groups and graphs, algorithms and automata» (Yekaterinburg, Ural federal university, IMM UB RAS, IM SB RAS, 2015).

Публикации. По теме диссертации опубликовано 8 печатных работ, из них 3 — в ведущих научных журналах, рекомендованных ВАК, 3 — в материалах международных и всероссийских конференций (РИНЦ).

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, библиографического списка, содержащего 54 наименования, и списка обозначений. Объем работы составляет 80 страниц.

Граф частичных порядков

В настоящей главе на множестве всех бинарных отношений произвольного множества X вводится бинарное рефлексивное отношение смежности и определяется основной объект исследований — граф бинарных отношений («граф графов»). Первый параграф носит подготовительный характер: определяется отношение смежности бинарных отношений и излагаются основные понятия, конструкции и обозначения. В параграфе доказано, что диаметр нетривиального графа бинарных отношений равен 2. В 2 определяется граф частичных порядков — подграф графа бинарных отношений. Если cardX = п оо, то существует взаимно-однозначное соответствие между множеством всех частичных порядков и множеством всех помеченных транзитивных ориентированных графов, определенных на X, в свою очередь, существует взаимно-однозначное соответствие между этим множеством и множеством всех помеченных То-топологий, определенных на X. Если То(п) — число таких топологий, то число связных компонент графа частичных порядков равно То(п —1). В 3 вводится понятие опорного множества частичного порядка и исследованы структурные свойства совокупности опорных множеств частичных порядков связной компоненты графа.

Пусть В = { 0,1 } — булево множество, X — произвольное множество, а X2 = X х X — прямое произведение. Функции X2 — В будем называть характеристическими. Всякое подмножество и С X2, называемое бинарным отношением (или просто отношением) на множестве X, порождает характеристическую функцию

Так как a(x,y) = 0 для всех (ж, у) Є Y х Z, то в блоке YxZ записан «обобщенный» ноль (аналогично в блоке Z х Y отношения г). В остальных блоках значения неизвестны, и там мы поступаем следующим образом. Берем за основу, например, отношение а и проставляем в его блоках условный символ Є] так как ту2 = ту2 и т 2 = (j\z2- то в диагональных блоках отношения г тоже пишем символ Є] наконец, в блоке YxZ отношения г пишем символ є , означающий, что т(х,у) = 1 — а(у,х) для всех (ж, у) Є Y х Z :

На протяжении работы мы представляем диаграммы в виде (1.1). Заметим, что за основу можно брать и отношение г (тогда в его блоке YxZ следует писать символ є, а в блоке Z xY отношения а — символ є ). Еще заметим, что довольно часто мы применяем «обобщенную» единицу (в случае, если априори известно, что все элементы блока равны 1).

Таким образом, X порождает пару (2 ,Е(Х)\ где через 2х2 обозначено множество вершин, состоящее из всех бинарных отношений множества X, а Е(Х) — это множество ребер, состоящее из неупорядоченных пар смежных бинарных отношений множества X (так как допускается, что Y = 0, то Е{Х) содержит все петли). Пару G{X) = ( 2х , Е(Х)} будем называть (неориентированным) графом бинарных отношений множества X.

Будем говорить, что бинарные отношения а и г принадлежат одной компоненте связности графа G(X), если существует конечная последовательность отношений О" = 0"1,0"2, , (Тт = Т, в которой отношения (Jk-\ и o k смежны при всех к = 2,... , т. Через Ga(X) будем обозначать ту компоненту связности графа G(X), которая содержит данное отношение а. Так как а', а" Є Ga(X), то существует конечная цепочка а' = <7о, <7i,... , (Tjj, = а", в которой отношения <7fc_i и (Т/с смежны при всех к = 2,...,/І. Если цепочка не каноническая, то осуществим следующую процедуру удаления лишних узлов: просматривая цепочку слева направо и обнаружив при некотором к равенство (Jk-i = &k, удаляем из цепочки отношение (Тк-і'і вновь просматривая цепочку слева направо и обнаружив при некотором к равенство (Тк-l = <7/г+Ъ удаляем из цепочки отношения (Jk-l и (Tk- В итоге мы получим каноническую цепочку О"' = <7о, <7i, . . . , <7т = о7' из семейства Q. Далее рассматриваем только канонические цепи.

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

В настоящей главе изучается граф рефлексивно-транзитивных отношений, подграфом которого является граф частичных порядков, определенный в главе I. В 4 исследованы особенности строения графа рефлексивно-транзитивных отношений произвольного множества X. В частности, установлен изоморфизм между отдельными связными компонентами этого графа и связными компонентами индуцированного им графа частичных порядков. В 5 исследуется граф конечных топологий (в случае X = {1,..., п}). Доказано, что количество компонент связности этого графа равно где S(n,m) — это числа Стирлинга 2-го рода, а То(п) — число помеченных То-топологий, определенных на множестве X. Хорошо известно (см., напри

Через У{Х) обозначим совокупность всех рефлексивно-транзитивных отношений, определенных на множестве X. Другими словами, отношение о" С X2 принадлежит множеству V(X), если оно удовлетворяет аксиомам рефлексивности и транзитивности. В терминах характеристических функций справедливо легко проверяемое утверждение: а Є V(X) тогда и только тогда, когда а(х,х) = 1 для всех х Є X, а (ж, у) а (у, z) о"(ж, z) для всех x,y,z Є X. (Аналогично формулам (2.1).) Для любых а Є V(X) и х Є X множество Ua(x) = { у єХ: а(х,у) = 1} (4.1) не пусто (так как х Є Ua(x)). Предложение 3. Пусть а Є V(X), ж, у Є X. Включение у Є Ua(x) имеет место тогда и только тогда, когда Ua(y) С Ua(x). Доказательство. Пусть у Є Ua(x), тогда а(х,у) = 1. Если

Отношение о" Є V(X) порождает на множестве X отношение эквивалентности: пишем х у (или х у) тогда и только тогда, когда Ua(x) = Ua(y). Класс эквивалентности, содержащий элемент х Є X, обозначаем [х]а (или ж). i 7]) = 1 для всех Є [х]аі Ц Є [у]а 5. Предположим противное, то есть 7 (,??) = 1, 7(?7,) = 1. Тогда справедливы включения Г] Е Ua( ), Є Ua{rf) и Ua{rf) С Ua( ) С Ua(rj), значит, ту, что противоречит условию []ст = [ж]а [?/]ег = [??]сг Теорема 4. Пусть отношения а и г смежны. Включение o EV(X) имеет место тогда и только тогда, когда г Є V(X). Утверждение доказывается по аналогии с теоремой 2. Таким образом, множество V(X) порождает подграф (V(X),E(X)} графа G(X). Будем называть его графом рефлексивно-транзитивных отношений. Очевидно, (Vo(X),E(X)} — это подграф графа (V(X),E(X)}.

Пусть о" Є V(X). Через [Х]а обозначим совокупность всех классов эквивалентности множества X, то есть [Х]а = { [ж] о-} х = {ж} х. В соответствии с пунктом 4 предложения 4 определена характеристическая функция а: [Х] — В такая, что

Значит, о" порождает на множестве [Х]а частичный порядок т (см. аксиомы (2.1)). Более того, о- порождает граф Go([X]a) = Vo([X]a), Е([Х]а)}, где Vo([X]a) — это множество частичных порядков, определенных на множестве [Х]а, а Е([Х]а) — множество ребер, состоящее из неупорядоченных пар смежных частичных порядков множества [Х]а. Таким образом, а Є Vo([X]a) и определена компонента связности графа Go([X]a), содержащая частичный порядок т (обозначим ее Go([X]a)). Л/ { 111

Будем говорить, что отношения о ,т Є У(X) являются рефлексивно-транзитивными отношениями одного и того же типа, если [Х]а = [Х]Т. Предложение 5. Если GиT — смежные рефлексивно-транзитивные отношения, определенные на множестве X, то [Х]а = [Х]Т. Доказательство. В силу смежности отношений а и т суще ствует дизъюнктное объединение Y U Z = X такое, что а т. Пусть ж, у Є X. В силу симметрии утверждения достаточно показать импликацию а т г -і -і г -і г -і X у = х у или [rrjcr = [yjcr =Ф- [жт = г/т. Пусть [ж]ст = [г/]о-, и предположим, что [х]т ф [у]т. Тогда в соответствии с пунктом 5 предложения 4 имеет место равенство т(х,у)т(у,х) = 0. С другой стороны, в силу пункта 3 этого же предложения справедливы равенства а(х,у) = а(у х) = 1, следовательно, (ж,у) Y х Z и (у, х) Y х Z. Значит, (ж, у)} (у} х) Є Y2UZ2} поэтому т(х,у) = и(х, у) = 1, т(у,х) = а(у х) = 1. Полученное противоречие доказывает утверждение.

Замечание 5. В процессе доказательства мы показали, в частности, что если о" т, то для любого х Є X = Y UZ имеет место альтернати ва: либо ЇСУ либо х С Z. Другими словами, множество [X] = [Х]а = [Х]т представимо в виде дизъюнктного объединения [X] = [Y] U [Z], [Y] = {х Є [X]: ж С Y}, [Z] = {х Є [X]: ж С Z}. (4.3) Замечание 6. В конечном счете мы установили, что всякое отношение о" Є V(X) порождает компоненту связности Ga(X) графа С(Х), совокупность [Х]а классов эквивалентности, частичный порядок а Є Vo([X]a), граф Go([X]a) и его компоненту связности Go([X]a). Кроме того, если г Є Ga(X), то GT(X) = Ga(X) и [Х]т = [Х]а, а в приводимом ниже предложении 6 доказано равенство GQ([X]T) = GQ([X](J).

Граф конечных топологий

Через У{Х) обозначим совокупность всех рефлексивно-транзитивных отношений, определенных на множестве X. Другими словами, отношение о" С X2 принадлежит множеству V(X), если оно удовлетворяет аксиомам рефлексивности и транзитивности. В терминах характеристических функций справедливо легко проверяемое утверждение: а Є V(X) тогда и только тогда, когда не пусто (так как х Є Ua(x)). Предложение 3. Пусть а Є V(X), ж, у Є X. Включение у Є Ua(x) имеет место тогда и только тогда, когда Ua(y) С Ua(x). Доказательство. Пусть у Є Ua(x), тогда а(х,у) = 1. Если Отношение о" Є V(X) порождает на множестве X отношение эквивалентности: пишем х у (или х у) тогда и только тогда, когда Ua(x) = Ua(y). Класс эквивалентности, содержащий элемент х Є X, обозначаем [х]а (или ж).

Если J(,77) = 0 для всех Є [ж]а, ту [?/]о-5 то утверждение очевидно. Предположим теперь, что a(z,w) = 1 для некоторых z Є [rrjer и if Є [j/Jer, тогда w Є Ua(z). Следовательно, [if]CT С Ua(w) С Ua(z), значит, ту Є Ua(z) для любого ту Є [j/Jer = [ifjo-. Так как Є [х]а = [z]a, то имеет место равенство Ua() = Ua(z), поэтому ц Є Ua(). Таким образом, i 7]) = 1 для всех Є [х]аі Ц Є [у]а 5. Предположим противное, то есть 7 (,??) = 1, 7(?7,) = 1. Тогда справедливы включения Г] Е Ua( ), Є Ua{rf) и Ua{rf) С Ua( ) С Ua(rj), значит, ту, что противоречит условию []ст = [ж]а [?/]ег = [??]сг Теорема 4. Пусть отношения а и г смежны. Включение o EV(X) имеет место тогда и только тогда, когда г Є V(X).

Утверждение доказывается по аналогии с теоремой 2. Таким образом, множество V(X) порождает подграф (V(X),E(X)} графа G(X). Будем называть его графом рефлексивно-транзитивных отношений. Очевидно, (Vo(X),E(X)} — это подграф графа (V(X),E(X)}. Пусть о" Є V(X). Через [Х]а обозначим совокупность всех классов эквивалентности множества X, то есть [Х]а = { [ж] о-} х = {ж} х. В соответствии с пунктом 4 предложения 4 определена характеристическая функция а: [Х]

Пусть [ж]ст = [г/]о-, и предположим, что [х]т ф [у]т. Тогда в соответствии с пунктом 5 предложения 4 имеет место равенство т(х,у)т(у,х) = 0. С другой стороны, в силу пункта 3 этого же предложения справедливы равенства а(х,у) = а(у х) = 1, следовательно, (ж,у) Y х Z и (у, х) Y х Z. Значит, (ж, у)} (у} х) Є Y2UZ2} поэтому т(х,у) = и(х, у) = 1, т(у,х) = а(у х) = 1. Полученное противоречие доказывает утверждение.

Предложение 6. Пусть рефлексивно-транзитивные отношения а и г определены на множестве X, а а и г — это порожденные ими частичные порядки, определенные на множествах [Х]а и [Х]Т соответственно. Отношения GиT смежны тогда и только тогда, когда смежны отношения а и т.

Опорные множества графа ациклических отношений

Очевидно, S = S((j) С 5 2 U 5 з U 5 4 и S = S(r) С Si U S2 U S3, поэтому 5 С 5 2 U 5 з. Предположим, что 5 4 ф 0. В силу (6.1) имеем S(a\s ) ф 0, следовательно, S П 5 4 = S cr) 0 5 4 0 (см. представление для т), что противоречит включению S С 5 2 U 5з. Значит, S4 = 0. Предположим, что Si 0- В силу (6.1) имеем (г г) ф 0, поэтому SnSi = S(r)nSi Ф 0 (см. представление для г), что противоречит включению S С 5 2 U 5 з. Значит, 5 1 = 0, а представления принимают вид

Итак, а = т. Обратное утверждение очевидно. В силу диаграммы (6.3) для любого а Є А(Х) определены отношения ак, к = 1,... ,р, а в силу теоремы 6 имеем ак Є А(Х), поэтому определены опорные множества S(ak). Предложение 9. Для любого к = 1,... ,р справедливы включения Xk Q S(ak) С S(a) U Х . Доказательство. Так как Х\ = S(a) и а1 = т, то при к = 1 утверждение очевидно. Пусть к 2. Тогда р 2. В соответствии с диаграммой (6.3) справедливы равенства

Включение Щ С Yk2 очевидно, поэтому ак(х,у) = а(х,у) = 0 для всех (ж, у) Є Щ. Пусть, далее, U k = Zk х X/;. Очевидно, И к С Zk х Yk, поэтому ак(х,у) = 0 для всех (ж, у) Є П ,. Таким образом, ак(х,у) = 0 для всех (ж, у) Є Щ U П , = X х X/;. Значит, Xk Q S(ak). p 1. Пусть к = 2, р 3. Тогда І2 = У Xj, Z2 = Xi и Xj_i х Jj с if г=2 для всех і = 3, ...fP. В силу (7.1) имеем т2х;_1хХ; = clxj-ixXj, поэтому блоки Xj_i х Х{ отношения о-2 — невырожденные. Следовательно, для лю р бого у Є [J Xj = X\(XiUX2) найдется ж такое, что а2(х,у) = 1, поэтому

Предложение 10. Для любого а Є 4(Х) и для любого непустого подмножества S С S cr) существует единственное т Є Ga(X) такое, что S{T) = S, причем г смежно с а. Доказательство. Отношение а и множество S С S cr) = Xi порождают (рекурсивным образом) три семейства множеств: Пусть Y= У Yi, Z= У Zj и (ж, у) Є Y х Z. Существуют і и j такие, что (ж,у) Є Yi х Zj. Если і j, то (ж,у) Є Yi х Zj С Xj х Xj, а в силу (6.2) справедливо а(х,у) = 0. Если же і j, то (ж,у) Є Y{ х Zj С У-7 х Zj, поэтому т(ж, у) = 0. Таким образом, т(ж, у) = 0 для всех (ж, у) Є У х Z. Очевидно, У UZ = X — дизъюнктное объединение, поэтому оно порождает

Таким образом, т(х,у) = 0 для всех (ж, у) Є ХхУі, значит Y\ С S(T), поэтому S(T) = 5 . Единственность г следует из леммы 7. Предложение 11. Для любого а Є 4(Х) и для любого х Є X существует единственное отношение т Є Ga(X) такое, что S(r) = {х}. Доказательство. Так как отношение а порождает разбиение (Xi,... ,Хр) множества X, то существует к такое, что х Є Х . В силу предложения 9 справедливо включение Х С S(ak), где ак Є Ga(X) — это отношение, определенное диаграммой (6.3). Так как {ж} С Х С S(ak), то в силу предложения 10 существует г Є Gafc(X) = Ga(X) такое, что S(T) = { х }. Через S(Ga) = { S(T) С X: т Є Ga(X) } обозначим совокупность всех опорных множеств ациклических отношений, принадлежащих компоненте Ga(X). В силу предложений 10-11 справедливо: 1) 0 S(Ga); 2) если 0 «С/ЗСХ и /3 є S(Ga), то а Є S(Ga); 3) если аСІ и а: = 1, то а Є S(Ga). Другими словами, совокупность S(Ga) является частично упорядоченным множеством относительно естественного отношения включения множеств со следующей спецификой: 1) вместе с каждым элементом множество S(Ga) содержит все его непустые подмножества; 2) S(Ga) содержит все одноэлементные подмножества множества X. Таким образом, для описания частично упорядоченного множества S(Ga) достаточно указать все его максимальные элементы. Заметим еще, что в соответствии с замечанием 3 в аналогичной совокупности S(Ga), определенной для частичных порядков, в обязательном порядке содержатся все двухэлементные подмножества. Последнее обстоятельство может сыграть существенную роль в процессе дальнейшего исследования транзитивных и ациклических графов.