Главная > Документ


(Комбинаторика, 29.11.03) Семинар 12.

Бинарное отношение R на множестве А называется:

а) рефлексивным, если (x, x) R для всех x А;

б) иррефлексивным, если (x, x) R для всех x А;

в) симметричным, если (x, y) R  (y ,x)R;

г) антисимметричным, если (x, y) R и (y ,x)Rx=y;

д) транзитивным, если (x, y) R и (y, z)R (x, z)R;

e) линейным, если (x, y) R или (y, x)R .

Рефлексивное, транзитивное и антисимметричное отношение на множестве А называется частичным порядкомнаА. Частичный порядок часто обозначается . Порядок –1 называется двойственным к  и обозначается символом . Будем писать x/I>y, если xy и xy. Частичный порядок на множестве А называется линейным, если любые два элемента из Асравнимы по , т.е. xy и yxдля любых x,yА.

Множество А с заданным на нем частичным (линейным) порядком  называется частично (линейно) упорядоченным. Частично упорядоченное множество обозначается (А,  ).

Диаграмма частично упорядоченного множества А (диаграмма Хассе) – ориентированный граф, множество вершин которого совпадает с множеством А, а пара (a, b) является дугой тогда и только тогда, когда a/I>b, и не найдется отличного от a, b элемента cА такого, что aсb.

Цепью называется частично упорядоченное множество, любые два элемента которого сравнимы. Подмножество B частично упорядоченного множества А называется цепью, если B, рассматриваемое как частично упорядоченное множество, есть цепь. Длина l(B) конечной цепи определяется равенством l(B)=|B|–1. Подмножество B частично упорядоченного множества А называется антицепью (семейством Шпернера), в котором любые два элемента несравнимы.

Элемент a частично упорядоченного множества А называется максимальным (минимальным), если из того, что ax(xa) следует a=x.

Если B– непустое подмножество частично упорядоченного множества А, то элемент b А называется точной верхней гранью множества B, если bx для всех xB и если из справедливости соотношения vx для всех xB вытекает vb.Элемент b А называется точной нижней гранью множества B, если bx для всех xB и если из справедливости соотношения vx для всех xB вытекает vb.

Частично упорядоченное множество А называется решеткой, если для любых двух элементов из А существует точная нижняя и верхняя грань. Решетки А и А’ называются изоморфными, если существует взаимно однозначное соответствие между множествами А и А’ такое, что ab в А (a) (b) в А’.

Задачи

0. Доказать, что множество всех подмножеств данного множества частично упорядоченно отношением .

1. a) Пусть ABP и существуют sup A, sup B(inf A, inf B). Доказать, что sup AsupB (inf Binf A).

б) Доказать, если ab, то sup{a,b}=b и inf{a,b}=a.

2. Найти все частичные порядки и соответствующие диаграммы Хассе на множестве L={a, b, c}. Выделить среди них линейные порядки.

3. Найти все неизоморфные решетки и соответствующие им диаграммы Хассе на множестве Z для n=3, 4, 5, 6. Ответ: 1, 2, 5, 15.

4. Пусть ab тогда и только тогда, когда a,bN и aделит b. Считаем, что 0 делит 0.

а) Доказать, что частичный порядок на N.

б) Пусть D(n)– множество всех делителей натурального числа n. Показать, что (D(n), ) есть решетка, найти его 0 и 1, изобразить диаграмму Хассе и описать ее уровни.

в) Является ли D(18) подрешеткой решеток D(288), D(124)?

г) Является ли D(18)D(63) подрешеткой решеток D(80), D(360)?

д) Какова длина и ширина решеток D(45), D(105), D(189),D(768)?

е) Изоморфны ли решетки D(210) и D(1430)?

ж) Существует ли в решетки D(1155) антицепь мощности 6?

5. Пусть С–множество комплексных чисел z=x+iy с рациональными x, y. Определим на С частичный порядок , положив x1+iy1x2+iy2 тогда и только тогда, когда y1y2. Существует ли в (С, ) минимальный и максимальный элемент? Какие требуются дополнительные условия, чтобы превратить (С, ) в цепь.

6. Оценить длину и ширину решетки D(n) через характеристики канонического разложения n на сомножители. Какова мощность множества D(n)?

7. Докажите, что любая конечная решетка обладает наибольшим и наименьшим элементом. Приведите пример решетки без наибольшего и наименьшего элемента.

8. Пусть (Vn(q), )– множество всех подпространств n-мерного пространства Vn над конечным полем с q элементами, частично упорядоченное по включению. Доказать, что множество частично упорядоченно, и описать его диаграмму Хассе.

9. а) Является ли (Vn(q), ) решеткой, сколько в нем элементов, сколько элементов данного уровня?

б)* каково число максимальных цепей в (Vn(2), ) между нулем и единицей, каково максимальное число цепей между нулем и единицей, проходящих через фиксированный элемент p(Vn(2), )? Указание. Воспользоваться теоремой Шпернера (см. В. Н. Сачков “Введение в комбинаторные методы дискретной математике”).

Ответ: | (Vn(q), )k|=–гаусовский q-биномиальный коэффициент.

10. Пусть T­– множество n–1 транспозиций из Sn и пусть GT– граф с множеством вершин {1,…,n}, в котором вершины i и j смежны только в том случае, когда (i, j)T. Доказать, что T порождает Sn тогда и только тогда, когда GT–дерево.

11. Пусть T­={t1,…,tn}– множество транспозиций из Sn. Показать, что g= – циклическая подстановка тогда и только тогда, когда граф GT из задачи 10 является деревом.

12. Пусть Xn={} и hSn задана в виде слова h=a1a2an, ajXn. Положим, Eh={( ai, aj): i/I>j, ai< aj}. Показать, что отношение hg тогда и только тогда, когда EhEg задает на Sn частичный порядок и что это упорядоченное множество– решетка, обозначаемая через P(Sn).

13. Пусть Xn={} и hSn, h: jh(j). Показать, что выражение (h,g)= , h, gSn, есть метрика на множестве Sn. Показать, что числа ah(n,r)=|{gSn: (g, h)r}| не зависит от выбора hSn и удовлетворяет рекуррентному соотношению

a(n,2)=2a(n–1,2)+2 a(n–3, 2)– a(n–5, 2), n6.

Напоминание. Функция d, определенная на множестве всех упорядоченных пар (x,y) элементов множества X и принимающая неотрицательные вещественные значения d(x,y) называется метрикой, если она обладает следующими свойствами:

  1. d(x,y)=0  x=y;

  2. d(x,y)= d(y,x);

  3. d(x,y)=d(x,z) +d(z,y) для всех zZ.

14. Для hSn пусть (h)=|{ j{}: h(j)j}|. Показать, что d(h, g)=|(hg1)|– метрика на Sn. Описать шары {gSn: d(h, g) )r}.




Похожие документы:

  1. Множество -совокупность объектов

    Закон
    ... : отношение // намножестве прямых плоскости) *Бинарноеотношение R намножестве M называется антисимметричным, если из условия R следует, что x=y *Бинарноеотношение R намножестве M называется транзитивным ...
  2. Свойства отношений

    Документ
    ... : Полнота: Бинарноеотношение R намножестве X называетсяотношением порядка, если имеют место Транзитивность: ; Антисимметричность: . Отношение порядка называется нестрогим, если ...
  3. Глава 3 Бинарные отношения 3 1 Основные положения

    Документ
    ... положения Бинарнымотношением R намножественазывается подмножество множества , < R, > ( 2). Иными словами бинарноеотношение R намножестве  представляет собой подмножество упорядоченных пар множества . Множествоназывается ...
  4. Глава I Алгебры Алгебраические системы 1 Операции на множествах

    Документ
    ... операций намножествах Определение 5. Бинарная операция * намножестве М называется коммутативной, если a,b М: a*b = b*a. Определение 6. Бинарная операция * намножестве М называется ассоциативной ...
  5. 1 Множества и действия над ними

    Закон
    ... . Бинарноеотношение а намножестве X называетсяотношением порядка, если оно транзитивно: и антисимметрично: Виды: Отношение порядка а называетсяотношением нестрогого порядка намножестве X, если ...

Другие похожие документы..