|
Математические заметки, 1981, том 29, выпуск 1, страницы 75–82
(Mi mzm10049)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Число допустимых линейных упорядочений частично упорядоченного множества как функция его графа несравнимости
А. Ф. Сидоренко
Аннотация:
Число лексикографий $m(P, R)$ конечного множества $P$ с антисимметричным
транзитивным отношением $R$ однозначно определяется структурой
шпернеровых семейств. Если $G(P, R)$ — граф несравнимости,
т. е. граф, чьи клики совпадают со шпернеровыми семействами в $(P, R)$,
то $m(P, R) = \mu (G (R, R))$, где $\mu$ — функция на графах, рекурсивно
определяемая сотношениями: $\mu(G_0)=1$, где $G_0$ — тривиальный граф,
$$
\mu(G)=\max_B\sum_{p\in B}\mu(G\setminus p),
$$
где максимум берется по всем кликам $B$ графа $G$. Библ. 8 назв.
Поступило: 03.10.1978
Образец цитирования:
А. Ф. Сидоренко, “Число допустимых линейных упорядочений частично упорядоченного множества как функция его графа несравнимости”, Матем. заметки, 29:1 (1981), 75–82; Math. Notes, 29:1 (1981), 40–44
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm10049 https://www.mathnet.ru/rus/mzm/v29/i1/p75
|
Статистика просмотров: |
Страница аннотации: | 144 | PDF полного текста: | 81 | Первая страница: | 1 |
|