Лекции по прикладной алгебре. v2.0 (1127112), страница 25
Текст из файла (страница 25)
множества P.343 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПредставление P = h P, 6 i в виде пересечения цепейТеорема (Шпильрайна, принцип продолжения порядка)12Любой частичный порядок 6 может быть продолжен долинейного на том же множестве.Каждый порядок есть пересечение всех своих линейныхпродолжений (линеаризаций).P → L,P = L1 ∩ . . . ∩ Le(P) ,где e(P) — множество всех линеаризаций ч.у. множества P.Доказательство (для конечного случая, |P | = n)1Если P — не цепь, то в P найдутся несравнимые элементы;произвольно определим порядок на них и продолжим его потранзитивности. Если получившиеся ч.у. множество ещё нецепь, то выберем новую пару несравнимых элементов ипоступаем, как указано выше.
Через конечное число шаговполучаем линейный порядок.343 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияТопологическая сортировка12(продолжение). Т.к. возможен различный выбор парнесравнимых элементов и при каждом выборе можнополагать любой их порядок, то можно получить всевозможные линейные продолжения исходного частичногопорядка.Пересечение всех таких цепей даст исходное ч.у. множество:если x 6 y, то аналогичное следование будет и во всехполученных линейных порядках, а при x y всегда найдётсяпара цепей с противоположным их следованием, что впересечении цепей и даст несравнимость этих элементов.Для конечных ч.у. множеств заданных парами вида a l b, поисктакого линейного продолжения в теоретическомпрограммировании называют топологической сортировкой.Задача решается за линейное время.344 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация345 / 432Представление ч.у.
множества пересечением цепейcd[[[ ba=dccdba∩baПрикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация346 / 432Некоторые ч.у. множества◦◦...◦hhhh◦hhhh . . .hhh◦◦Рис. 8. Малая корона sn['['hb 4[4'['hb 4[4 [[hb 4A4 [Ahb'4h'['[A4 Ah [A[4 h4 h ['hh44 [[[h'hA4[4'A'[A[[h'h4[4''[hh44h[A[A[4AhA[[[[[4 h'['[4h'['[4aaaaab144123452345Рис. 9. Корона S5Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация«e(P)= ?» — NP-полная задача, но:n+me(P + Q) =e(P)e(Q), n = |P|, m = |Q|;n 12ne(2 × n) =— числа Каталана;n+1 nX e(Zn ) xnn>0n!= tg x + sec x ,значения Zn при чётных n — числа секанса, а при нечётных —числа тангенса;e(Sn ) = (n + 1)!(n − 1)! ;X e(sn )xxn =;n!cos2 xn>1log(e(B n ))n3= log− log e + o(1) .n2bn/2c2347 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияВероятностное пространство на линеарезацияхПри решении задач комбинаторики, дискретной оптимизации идр.
часто рассматривают связанное с ч.у. множеством Pвероятностное пространство на множестве всех e(P) еголинеаризаций, в котором каждая линеаризация равновероятна.348 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияВероятностное пространство на линеарезацияхПри решении задач комбинаторики, дискретной оптимизации идр. часто рассматривают связанное с ч.у. множеством Pвероятностное пространство на множестве всех e(P) еголинеаризаций, в котором каждая линеаризация равновероятна.В этом пространстве для элементов x, y, z, . . .
данного ч.у.множества рассматривают события E вида x 6 y,(x 6 y) N (x 6 z) и т.д.348 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияВероятностное пространство на линеарезацияхПри решении задач комбинаторики, дискретной оптимизации идр. часто рассматривают связанное с ч.у. множеством Pвероятностное пространство на множестве всех e(P) еголинеаризаций, в котором каждая линеаризация равновероятна.В этом пространстве для элементов x, y, z, . .
. данного ч.у.множества рассматривают события E вида x 6 y,(x 6 y) N (x 6 z) и т.д. Вероятность Pr [E] такого события:Pr [E] =число линеаризаций, в которых имеет место E.e(P)348 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияВероятностное пространство на линеарезацияхПри решении задач комбинаторики, дискретной оптимизации идр. часто рассматривают связанное с ч.у. множеством Pвероятностное пространство на множестве всех e(P) еголинеаризаций, в котором каждая линеаризация равновероятна.В этом пространстве для элементов x, y, z, .
. . данного ч.у.множества рассматривают события E вида x 6 y,(x 6 y) N (x 6 z) и т.д. Вероятность Pr [E] такого события:Pr [E] =число линеаризаций, в которых имеет место E.e(P)Теорема (XYZ-теорема)Пусть h P, 6 i — ч.у. множество и x, y, z ∈ P . ТогдаPr [ x 6 y ] · Pr [ x 6 z ] 6 Pr [ (x 6 y) N (x 6 z) ] .348 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПроблема сортировки и «1/3 – 2/3 предположение»— определить линейный порядк L с помощью минимальногоколичества вопросов «верно ли, что x < y в L?».Обобщение: L — зафиксированная, но неизвестнаялинеаризация ч.у. множества P.Оптимальная процедура поиска L включает в себя нахождениеэлементов x и y, для которых Pr [ x < y ] ≈ 12 .349 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПроблема сортировки и «1/3 – 2/3 предположение»— определить линейный порядк L с помощью минимальногоколичества вопросов «верно ли, что x < y в L?».Обобщение: L — зафиксированная, но неизвестнаялинеаризация ч.у.
множества P.Оптимальная процедура поиска L включает в себя нахождениеэлементов x и y, для которых Pr [ x < y ] ≈ 12 .С.С. Кислицын (1968) высказал «1/3 – 2/3 предположение»:“любое не являющееся цепью ч.у. множество содержит парунесравнимых элементов x и y, для которых126 Pr [ x 6 y ] 6”.33Позднее это утверждение независимо выдвинули американскиеисследователи М. Фредман и Н. Линал.349 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация1/3 – 2/3 предположениеПример 2 + 1 показывает,что указанные границынесужаемы (имеется и примердесятиэлементного ч.у.
множествасо связанной диаграммой Хассе).350 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация1/3 – 2/3 предположениеПример 2 + 1 показывает,что указанные границынесужаемы (имеется и примердесятиэлементного ч.у. множествасо связанной диаграммой Хассе).Данное предположение до сих пор успешно противостоит всемпопыткам его доказать и представляет собой одну из наиболееинтригующих проблем комбинаторной теории ч.у.
множеств(С. Фелснер и У.Т. Троттер).350 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация1/3 – 2/3 предположениеПример 2 + 1 показывает,что указанные границынесужаемы (имеется и примердесятиэлементного ч.у. множествасо связанной диаграммой Хассе).Данное предположение до сих пор успешно противостоит всемпопыткам его доказать и представляет собой одну из наиболееинтригующих проблем комбинаторной теории ч.у.
множеств(С. Фелснер и У.Т. Троттер).На сегодняшний день наиболее сильный результат:√√5− 55+ 50, 2764 ≈6 Pr[x 6 y] 6≈ 0, 7236 .1010350 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация351 / 432Ч.у. множества: спектрОпределение:Spec (P) =Pr [ a 6 b ] | a, b ∈ P, a 6= bПрикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация351 / 432Ч.у. множества: спектрОпределение:Spec (P) =Pr [ a 6 b ] | a, b ∈ P, a 6= bЯсно, чтопоскольку Pr [ a 6 b ] = 1 − Pr [ b 6 a ], спектрсимметричен относительно 21 ;для всех неодноэлементныхтривиально упорядоченных1множеств Spec = 2 ; 1 0, 2 , 1 — единственный трёхэлементный спектр;все четырёхэлементные спектры должны иметь вид{ 0, α, 1 − α, 1 }, где 0 < α < 21 ;Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация351 / 432Ч.у.
множества: спектрОпределение:Spec (P) =Pr [ a 6 b ] | a, b ∈ P, a 6= bЯсно, чтопоскольку Pr [ a 6 b ] = 1 − Pr [ b 6 a ], спектрсимметричен относительно 21 ;для всех неодноэлементныхтривиально упорядоченных1множеств Spec = 2 ; 1 0, 2 , 1 — единственный трёхэлементный спектр;все четырёхэлементные спектры должны иметь вид{ 0, α, 1 − α, 1 }, где 0 < α < 21 ;Гипотеза (2002): α = 13 .Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у.
множества: размерностьПо теореме Шпильрайна ч.у. множество P совпадает спересечением всех e(P) своих линеаризаций.Однако тот же результат можно получить, взяв значительноменьшее число линейных продолжений. Например, ч.у.множество Pcbd[[[ aимеет 6 линеаризаций, но P = [ a, b, c, d ] ∩ [ a, d, c, b ].352 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у. множества: размерностьПо теореме Шпильрайна ч.у. множество P совпадает спересечением всех e(P) своих линеаризаций.Однако тот же результат можно получить, взяв значительноменьшее число линейных продолжений. Например, ч.у.множество Pcbd[[[ aимеет 6 линеаризаций, но P = [ a, b, c, d ] ∩ [ a, d, c, b ].Пусть P — ч.у.
множество и R = { L1 , . . . , Lk } —совокупность цепей такая, что P = L1 ∩ . . . ∩ Lk , то говорят,что R реализует P.352 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у. множества: размерность...ОпределениеНаименьшее число линейных порядков, дающих в пересечении данноеч.у. множество P называется его (порядковой) размерностью(символически dim(P )).353 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у. множества: размерность...ОпределениеНаименьшее число линейных порядков, дающих в пересечении данноеч.у. множество P называется его (порядковой) размерностью(символически dim(P )).Теорема (Оре)Порядковая и мультипликативная размерности ч.у.
множествасовпадают.353 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация353 / 432Ч.у. множества: размерность...ОпределениеНаименьшее число линейных порядков, дающих в пересечении данноеч.у. множество P называется его (порядковой) размерностью(символически dim(P )).Теорема (Оре)Порядковая и мультипликативная размерности ч.у. множествасовпадают.[ 1, 2, 3, 4, 5 ] ∩ [ 2, 4, 1, 3, 5 ]:— [ a, b, c ] × [ d, e ]Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияdim(P) — более тонкая оценка ч.у.
множества, чем e(P)Размерность ... имеют:1 — только цепи;2 — тривиально упорядоченные множества(т.е. размерность не может интерпретироваться как мераотличия данного ч.у. множества от линейного);— Zn ;— все отличные от цепей ч.у. множеств, при |P | 6 6, кроме3 — s3 , sh и shd (см. диаграммы) :n — Sn .354 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияО размерности ч.у. множества P = h P, 6 i∅ 6= Q ⊆ P ⇒ dim(Q) 6 dim(P), при удалении 1-гоэлемента его размерность уменьшается не более, чем на 1;dim(P + Q) = max dim(P), dim(Q) , если хотя быодно из множеств не является цепью и dim(P + Q) = 2;dim(P × Q) 6 dim(P) + dim(Q);dim(P) 6 |P|/2 при |P| > 4 (теорема Хирагучи).355 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияО размерности ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
