В.А. Носов - Комбинаторика и теория графов (1023552), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Произведение R1⋅R2 отношения эквивалентности R1 и R2 является отношением эквивалентности в том и только в том случае, когда выполняется условиеR1⋅R2 = R2⋅R1.2. Отношения толерантности.Бинарное отношение R на множестве А называется отношением толерантности,если оно рефлексивно и симметрично. Данное определение отвечает интуитивномупредставлению о сходстве или похожести предметов. Множество А вместе с заданнымна нем отношением толерантности называют также пространством толерантности (обозначение: (А,R)).Пример. Пусть H - произвольное множество, B1(H) - множество непустых подмножеств множества H. Определим отношение R на элементах множества B1(H) условиемxRy ⇔ xI y ≠ ∅ , x, y ∈ B1(H)Симметричность и рефлексивность данного отношения R очевидны, и поэтому оно будет отношением толерантности.Пример. Пусть H1, H2 - произвольные множества.

Обозначим через M(H1,H2) множество всех отображений F : H1 → H2. Определим на множестве M(H1,H2) отношение R условиемF1RF2 ⇔ ∃ h ∈ H  F1(h) = F2(h)Симметричность и рефлексивность данного отношения R также очевидны, и поэтомуоно будет отношением толерантности.

Над отношениями толерантности можно производить обычные операции. Нетрудно установить, что если T1, T2 - отношения толерантности, то отношениями толерантности также будут следующие отношения:26∨T1 U T2 , T1 I T2 , T1−1 , T1Произведение отношений толерантности, вообще говоря, не будет отношением толерантности. Может быть доказанаТеорема 5. Для того, чтобы произведение T1⋅T2 отношений толерантности T1, T2было отношением толерантности, необходимо и достаточно, чтобы выполнялось условие:T1⋅T2 = T2⋅T13. Отношения частичного порядка.Бинарное отношение R на множестве А называется антисимметричным, еслисправедливо свойство: aRb, bRa ⇒ a = b.

Отношение R называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно. Множество Авместе с заданным на нем отношением частичного порядка R называется частично упорядоченным множеством. Для обозначения отношения частичного порядка будет такжеиспользоваться знак ≤ .Пример 1. Пусть B(A) - булеан множества А. Тогда отношение теоретикомножественного включения ≤ задает на B(А) отношение частичного порядка.Пример 2.

Пусть Em = {0, 1, … , m} и пусть ≤ - обычное отношение сравнимости для целых чисел. Рассмотрим множество E nm = E m ×L× E m (n раз) и определим отношение частичного порядка на E nm , обозначаемое также ≤ , с помощью условия:(x1, … , xn) ≤ (y1, … , yn) ⇔ xi ≤ yi, ∀ i ∈1, nв смысле сравнимости элементов Em, xi, yi ∈ Em, i ∈1, n .Легко проверяется, что введенное отношение есть отношение частичного порядка. Приm = 1 мы получаем единичный n-мерный куб, (обозначение: En ), представляющий собоймножество двоичных набором длины n из элементов 0, 1.Весом набора α = (α1, … , α n) (обозначение - α ) называется число единичных координат.

Заметим, что булеан B(А) n-элементного множества A = {a1, … , an} однозначнопредставляется единичным n-мерным кубом En :гдеX ⊆ B(A) ⇔ αX = (α1, … , α n)αi =1, если ai ∈ X0, в противном случае.Данное соответствие определяет изоморфизм27двух частично упорядоченных множеств 〈 B(A), ⊆ 〉 и 〈 En , ≤ 〉. Элементы a, b частичноупорядоченного множества (А, ≤ ) называются сравнимыми, если b ≤ a или a ≤ b, впротивном случае - несравнимыми.

Частичный порядок называется линейным порядком(также - цепь), если любые два элемента сравнимы. Произвольное множество элементовчастично упорядоченного множества называется антицепью, если любые два его элемента не сравнимы. Примером линейного порядка является лексикографический порядок слов.

Пусть дан алфавит А с зафиксированным на нем порядком букв. Рассмотриммножество А* слов (т.е. последовательностей букв из алфавита А конечной длины). Определим линейный порядок на А* (обозначение: ∝) следующим образом:1. На словах, состоящих из одной буквы, отношение ∝ совпадает с порядкомбукв в алфавите А.2. Для произвольных двух слов s1 = a11a12 … a1m и s2 = a21a22 … a2n в алфавите Аполагаем s1 ∝ s2 ⇔ выполнено одно из условий:1. s1 = paiq1, s2 = pajq2 и ai ∝ aj . Здесь p, q1, q2 - некоторые слова (возможно пустые), ai, aj ∈ A.2. s2 = s1p , где p - непустое слово.Легко проверяется, что данное отношение есть отношение линейного порядка.

Наиболееизвестным примером лексикографического упорядочения является упорядочение слов всловарях.Замечание. Если рассматривать числа в позиционных системах счисления (например, в двоичной или десятичной) как слова в алфавите цифр, то их лексикографическое упорядочение совпадает с обычным, если рассматриваемые числа имеют одинаковое число разрядов. В общем виде эти два упорядочения могут не совпадать. Например,10 < 1088 и 10 ∝ 1088, но 20 < 1088 и 1088 ∝ 20.Для того, чтобы оба вида упорядочения совпадали, нужно выравнять число разрядов увсех сравниваемых чисел, приписав слева нули.

В данном примере получим 0020 ∝1088. Такое выравнивание автоматически происходит при записи целых чисел в ЭВМ.Над отношениями частичного порядка можно производить обычные операции.Нетрудно установить, что если R1, R2 - отношения частичного порядка, то отношенияR1−1 , R1 I R2 есть отношения частичного порядка. Объединение отношений частичногопорядка, вообще говоря, не является отношением частичного порядка. Может быть доказана28Теорема 6. Объединение R1 U R2 отношения частичного порядка является отношением частичного порядка тогда и только тогда, когда справедливо включениеR1 ⋅ R2 U R2 ⋅ R1 ⊆ R1 U R24. Приведем теперь количественные соотношения, связанные с введенными бинарными отношениями. Пусть А - множество из n элементов.21.

Число бинарных отношений на множестве А равно 2 n .2. Число рефлексивных отношений на множестве А равно 2 n3. Число симметричных отношений на множестве А равно 24. Число отношений толерантности на множестве А равно 22−n.n ( n +1)n ( n −1)1212..Эти факты легко следуют из матричного представления отношения R.СправедливаТеорема 7. Пусть pn - число отношения n-эквивалентности наn-элементном множестве. Тогда справедлива формулаpn+1 = n∑ i =0  i  p i , p0 = 1n♦ Зафиксируем некоторый элемент a ∈ A, гдеA = n + 1. Тогда для произвольного отношения эквивалентности элемент a будет находиться в классе эквивалентностивместе с i другими элементами, где i = 0, 1, … , n. Подмножество из i элементов может nбыть выбрано   способами.

Оставшиеся n - i элементов разбиваются на классы экви iвалентности pn-i способами - по числу отношений эквивалентности. Применяя правилосуммы и произведения, получимpn+1 = n∑i =0  i  p n− in= n∑ i =0  i  p i ,nчто и требовалось. ♦Приведем таблицу нескольких первых значений функций pn.n0123456789pn11251552203877414021147Числа pn называются числами Белла. Обозначим pnk - число отношений эквивалентности ранга k на n-элементном множестве.29Теорема 8.

Для чисел pnk справедливо соотношениеpnk = pn-1,k-1 + k pn-1,kp00 = 1, p10 = 0Пусть А = {a1, … , an} . Все множество отношений эквивалентности ранга k на Аразобьем на два класса. Класс 1 составляют те отношения, в которых элемент an образует класс [an] = {an}, состоящий из одного элемента. Класс 2 составляют все остальныеотношения эквивалентности ранга k. Ясно, что число элементов в классе 1 равно pn-1,k-1 по числу отношений эквивалентности ранга k - 1на (n - 1)-множестве А\ {an }. Далее,число элементов в классе 2 равно k pn-1,k , поскольку любое разбиение А\ {an} на k непустых частей дает k разбиений А на k непустых частей путем добавления k способамиэлемента an в одну из частей. Обратно, каждое разбиение А\{an} на k непустых частейможет быть получено из k разбиений А на k частей из класса 2 удалением элемента an .Применяя правило суммы, получаем утверждение.

♦Комбинаторные числа pnk называются числами Стирлинга 2-го рода. Применяяполученное соотношение, можно построить следующую таблицу для чисел pnkk0123456780100000000101000000020110000003013100000401761000050115251010006013190651510070163301350140211080112796617011050266281Упражнения.1. Доказать, что на множестве из n элементов имеется 2n-1 - 1 отношений эквивалентности ранга 2.3 n −1 + 1+ 2 n −1 отношений2. Доказать, что на множестве из n элементов имеется2эквивалентности ранга 3.303. Показать, что всякое подмножество En (множество двоичных наборовдлины n), содержащее не менее n + 2 набора, содержит пару несравнимых наборов.4. Доказать, что для любого набора x ∈ En, содержащего k единиц (0 ≤ k ≤ n),имеется 2k + 2n-k - 1 сравнимых с ним наборов.5.

Для множества E5 указать покрытие, состоящее из минимального числа цепей.31§ 5. Элементы теории подстановок.1. Подстановки были введены в § 1. Они играют большую роль в дискретнойматематике, поэтому мы займемся изучением их элементарных свойств. Пусть даномножество Nn = {1, 2, … , n} . Тогда любая подстановка F множества Nn представляетсяв виде таблицы2n L 1F:  F(1), F(2), L F( n)При этом число названо степенью подстановки F. Определим подстановку E множестваNn условием:E(i) = i,i ∈ Nn.Такая подстановка называется тождественной или единичной. Определим теперь умножение подстановок как результат последовательного выполнения соответствующих биективных отображений.

Ясно, что результирующее отображение при этом будет биективным. Если взять подстановку G, определяемую таблицей:2Ln  1G:  G(1), G(2), L G( n)то по определению полагаем12Ln F•G =  F(G(1)), F(G(2)), L F(G( n))Например, пусть 1 2 3 4F= ,G= 3 1, 4 21 2 3 4 , то1 3 4 2 1 2 3 4 3 4 2 1F•G = Ясно, что для тождественной подстановки E выполнено E•F = F•E = F для любой подcтановки F.Легко видеть, что, вообще говоря, F•G ≠ G•FУмножение подстановок ассоциативно, т.е. для любых подстановок F, G, H выполненоF•(G•H) = (F•G)•HЭто следует из доказанного выше утверждения об ассоциативности умножения бинарных отношений.32Для произвольной подстановки F определим обратную подстановкуF-1 , для которой справедливо F-1•F = F• F-1 = EОбратной к подстановке F, где2n L 1F=  F(1), F(2), L F( n)является подстановка F(1) F(2) L F( n)F-1 = 2Ln  1которая определяется корректно, т.к.

в строке F(1), F(2), … , F(n) все элементы различны и представлены точно 1 раз.Таким образом, множество подстановок конечного множества Nn удовлетворяетаксиомам группы, определение которой известно из курса Алгебры. Множество всехподстановок множества Nn называется симметрической группой множества Nn и обозначается S(Nn). Ясно, что число подстановок в группе S(Nn), называемое порядком группыS(Nn), равно n!2. Для подстановок часто используется запись в виде произведения независимыхциклов. Пусть P - некоторая подстановка множества Nn. Фиксируем некоторый элементa1 ∈ Nn и рассмотрим элемент P(a1) .Если P(a1) = a, то говорим, что элемент a1 образует цикл длины 1, и обозначим его (a1) .Если P(a1) ≠ a1, то образуем последовательностьa1, a2, a3, … , где a2 = P(a1), a3 = P(a2) и т.д.Поскольку множество Nn конечно, то в данной последовательности найдутся повторения.

Характеристики

Список файлов книги