Русский

Conference publications

Abstracts

XXIV conference

Задание деревьев формулами

Белов Ю.А.

Ярославский государственный университет им. П.Г. Демидова, Ярославль, ул. С-Щедринад. 59 кв.12

1 pp. (accepted)

Рассмотрим сначала операции на частично упорядоченных множествах (ч. у. множества). В работе [1], например, рассматриваются операции на ч. у. множествах: прямая сумма +, порядковая сумма +о. Пусть А и В -- два непересекающихся ч. у. множества. Прямой суммой А+В данных множеств называется объединение указанных множеств, в котором отношение порядка есть объединение отношений на А и на В. Порядковой суммой А+оВ называется объединение множеств А и В, в котором отношение порядка есть объединение отношений порядков в А и в В, дополненное такими парами: все элементы из А предшествуют всем элементам из В.

Класс Р ч. у. конечных множеств, которые могут быть получены из одноэлементного множества (будем его обозначать 1) с помощью операций + и +о называется классом последовательно-параллельных ч. у. множеств -- [2]. Напомним определение диаграммы Хассе. Если задано конечное ч. у. множество А, то диаграммой Хассе множества А называется ориентированный граф, вершины которого совпадают с А, а дуги графа определяются отношением покрытия, получаемым из отношения частичного порядка на А исключением всех пар, являющихся транзитивными следствиями других пар.

С другой стороны, для всякого дерева имеется корневое представление. Выбор корня и соответствующее корневое представление порождают ориентированный граф, использующий для ориентации дуг отношение «отцы-потомки». Теперь можно сформулировать следующее утверждение.

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

Литература.

С. И. Гуров Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры. М., Либроком, 2013 г., 221 стр.

Р. Стенли Перечислительная комбинаторика М., Мир, 1990 г. 438 стр.



© 2004 Designed by Lyceum of Informational Technologies №1533