Метод математической индукции

Метод математической индукции Метод математической индукции – универсальный способ доказательства утверждений, зависящих от натурального аргумента n. Он основан на следующем принципе математической индукции: утверждение справедливо для любого натурального n, если 10 оно справедливо для n = 1; 20 из того, что оно верно для всех n  k (k  1) следует его справедливость для n = k + 1. Этот принцип, являющийся одной из аксиом натурального ряда можно перефразировать так: если в цепочке утверждений Р(n) первое утверждение Р(1) верно, а из справедливости Р(k) следует справедливость Р(k + 1), то вся цепочка состоит из верных утверждений. Пример 1. Найти сумму . Решение. Имеем:; ; ; . Есть подозрение, что . Докажем эту формулу. 10. При n = 1 – формула верна. 20. Предположим, что для произвольного k  1 для всех n  k . В частности, для n = k . Найдем . Имеем . По предположению это равно = = = , что и требовалось доказать. Слово “индукция” переводится как “наведение”. Во многих отраслях науки используют метод простой (не математической) индукции – вывод, полученный после рассмотрения ряда частных случаев (согласно принципу простой индукции – от частного к общему). В основном так поступают, обобщая результаты каких-то экспериментов. Так было сделано и в решении предыдущего примера, при разработке вывода о возможной формуле для Sn. Предварительно были найдены S1, S2, S3, … . Однако индуктивное утверждение может быть неверным, простая индукция позволяет лишь выдвинуть гипотезу, которую надо доказать, например, с помощью математической (полной) индукции. Можно привести много примеров, когда простая индукция приводит к ошибочным выводам. Например, анализируя числа 1, 3, 5, 7 можно прийти к неверному заключению, что все нечетные числа являются простыми. Слово ”индукция” в названии рассматриваемого метода, видимо связано с тем, что для его использования необходимо сначала догадаться, что именно следует доказать, т.е. выдвинуть гипотезу. Обычно это делается с помощью простой индукции. Пример 2. “Докажем”, что все натуральные числа равны между собой. Предположим, что k = k + 1. Прибавим по 1 к обеим частям этого равенства. Получим k + 1 = k + 2, что и требовалось доказать. Ошибка этого “доказательства” состоит в отсутствии проверки утверждения при n = 1. КОНТРОЛЬНЫЕ ВОПРСЫ И ЗАДАНИЯ 1*. Доказать формулу Sn = 12 + 22 + 32 + … + n2 = n(n +1)(2n +1) /6. 2*. Доказать неравенство 2n > 2n + 1 при n  3. 3*. Обозначим Hn = 1 + 1/2 + 1/3 +…+ 1/n– гармонические числа. Доказать, что Нn неограниченно сверху, т.е. что Нn  +. 4*. Доказать, что любую сумму денег более 7 копеек можно уплатить монетами достоинством 3 и 5 копеек. 5*. Доказать, что для любого n  0 число 11n + 2 + 122n + 1 делится на 133. Доказать формулы и утверждения (6 – 13). Примеры решения Задача 1. , т.е. при n = 1 формула верна. Sk + 1 = Sk + (k+1)3 = = = . Задача 2. 2k + 1 = 2×2k > 2(2k + 1) = 4k + 2 = (2k + 3) + (2k – 1) > 2k + 3. Задача 3. Докажем, что . 10. m = 1, Н2 = 1 +  1 +. 20. > + = = > 1 + = 1 + . Это означает, что при достаточно большом n значение Нn может стать больше любого числа. Задача 4. 10. 3 + 5 = 8 – верно. 20. Пусть уплатили k копеек. Возможны два случая. а). Вся сумма оплачена только 3-копеечными монетами. В этом случае надо 9 копеек (3+3+3) заменить на 5 + 5 – получим сумму k + 1. б). Использована хотя бы одна 5-копеечная монета. Тогда надо 5 копеек заменить на 3 + 3 – снова получим сумму k + 1. Задача 5. 10. 112 + 121 = 133 – верно при n = 0. 20. 11k +3 + 122(k + 1) +1 = 1111k + 2 + 144122k + 1 = = (144–133) 11k + 2 + 144122k + 1 = 144  (11k + 2 + 122k + 1 ) – – 13311k + 2. В полученной разности уменьшаемое делится на 133 по предположению, а вычитаемое содержит множитель 133. Следовательно, все выражение делится на 133. ЛЕКЦИЯ № 1 Основные понятия теории множеств  Для множества не существует строгого определения, поэтому введем описательные понятия множества и его элементов. Множеством называется совокупность некоторых предметов, объединенных общим признаком. Элементы множества - это те предметы, из которых состоит множество. Пусть имеется множество А, элементом которого является предмет а, это записывается как А={а}. Например, В={1, 2, 3}. Если какой-то элемент а принадлежит множеству А, то это обозначается аА, а если b не принадлежит А, то - bА. Например, пусть А - множество четных натуральных чисел, тогда 6А, а 3А. Пусть имеется два множества А и В, причем все элементы множества А принадлежат множеству В, т.е. если хА, то хB. В этом случае говорят, что множество А включено в множество В. Обозначается: АВ ( - символ нестрогого включения, т.е. возможно совпадение множеств). Множество А совпадает с множеством В (А = В), если все элементы множества В являются элементами множества В и все элементы множества В являются элементами множества А. Это можно записать в виде (АВ и ВА) <=> (А = В). Множество А строго включено в множество В, если все элементы множества А принадлежат множеству В, но не все элементы множества В принадлежат множеству А. Пример: А = { 1, 2, 3 }, В = { 0, 1, 2, 3 }, АВ. Возможны два способа задания множества. 1. Перечислением элементов, т.е. в фигурных скобках дается полное перечисление элементов данного множества. Например : N= {1,2,...,n,...} - множество натуральных чисел. 2. С помощью указания характерного свойства (указание свойства, которым обладают только элементы данного множества). Символически это записывается в виде A={x | P(x)} и читается - A есть множество всех элементов х, обладающих свойством P(x). При задании множества вторым способом возможны различные противоречия и парадоксы. Рассмотрим примеры таких парадоксов. 1) Парадокс парикмахера: в городе жил парикмахер, который брил всех, кто не брился сам. Кто же брил парикмахера? 2) Пусть имеем натуральное число 11218321 - одиннадцать миллионов двести восемнадцать тысяч триста двадцать один. Это число можно описать с помощью восьми слов. Пусть А - множество натуральных чисел, которые нельзя определить с помощью фразы, имеющей меньше 20 русских слов. Обозначим аmin - наименьшее число из множества А, причем аminA. Число аmin можно определить следующим образом: наименьшее натуральное число, которое нельзя определить с помощью фразы, имеющей менее двадцати слов. В этой фразе 14 слов. Значит, аmin можно определить с помощью фразы, содержащей менее 20 слов. Тогда получается, что аmin А. К настоящему времени накопилось много подобных примеров, когда определение множества оказывалось внутренне противоречиво. Выяснение условий, при которых это может иметь место потребовало специальных исследований, составивших предмет математической логики и выходящих за рамки собственно теории множеств. Поэтому в данном пособии мы не станем касаться спорных случаев и будем рассматривать лишь множества, которые определяются точно и без противоречий. В теории множеств имеется специальное множество, называемое пустым множеством (), которое не содержит ни одного элемента. Пустое множество по определению содержится в любом множестве А (А). Это понятие вводится из следующих соображений. Задавая множество вторым способом не всегда заранее можно быть уверенным, существуют ли элементы, ему принадлежащие. Например, можно говорить о множестве четырехугольников на плоскости, у которых все углы прямые, а диагонали не равны. Только знания основ геометрии позволяют убедиться, что таких четырехугольников не существует и, следовательно, это множество пусто. Большинство утверждений теории множеств связано с равенством двух множеств и включением одного множества в другое. Поэтому надо детально разобраться в методах доказательства этих фактов. 1. Доказательство включения АВ. Для этого нужно доказать, что любой элемент x, принадлежащий множеству А одновременно является элементом множества В, т.е. (x  А)  => (x  В). 2. Доказательство равенства А = В. Оно сводится к доказательству двух включений АВ и ВА. Пример 1. Докажем следующую теорему. Для любых множеств А, В и С выполняется закон транзитивности нестрогого включения, т.е. если АВ и ВС, то из этого следует, что АС. Доказательство. Пусть x - любой элемент множества А, (xА), тогда в силу условия АВ, по определению нестрогого включения, элемент х принадлежит множеству В (хB). После доказательства этого факта, аналогично, используя условие ВС можно доказать, что х принадлежит С (хС). В качестве исходного допущения мы приняли, что x – любой элемент из А. Из этого допущения при выполнении условий а) и б) получено следствие хС. По определению нестрогого включения это означает АС, что и требовалось доказать. Пример 2. Пусть А={1,6}, В ={х | х2-7х+6=0}. Последнее читается как, В является множеством элементов х, для которых выполняется условие х2 - 7х + 6 = 0. Включение АВ доказывается подстановкой элементов множества А в это условие. Для доказательства обратного включения ВА нужно найти все корни уравнения и убедиться, что они равны 1 и 6, т.е. принадлежат А. Выполнение обоих нестрогих включений означает равенство множеств А и В. Операции над множествами Определим следующие операции. 1. Объединение. Пусть А и В - произвольные множества. Их объединением называется множество С = АВ, которое состоит из всех элементов, принадлежащих хотя бы одному из множеств А или В. 2. Пересечение. Пересечением множеств А и В называется множество С, состоящее из элементов одновременно принадлежащих А и В. Обозначается так: C=AB. 3. Разность. Разность множеств А и В - это множество С (С=А\В), состоящее из элементов множества А, не принадлежащих множеству В. Если ВА, то разность С = А\В называется дополнением В до А. Иногда, говоря о некотором наборе множеств подразумевают, что все они включены в некоторое множество S, которое называют универсальным множеством. В этом случае дополнение какого-либо множества А до S обозначается С(А) или . 4. Симметричная разность. По определению симметричная разность двух множеств А и В - это множество С = АВ = (А\В)(В\А). Основные свойства операций. 1. Операции пересечения и объединения коммутативны (перестановочны): АВ = ВА; АВ = ВА. 2. Операции пересечения и объединения ассоциативны. (АВ) С = А (ВС) = АВС (АB) С = А (ВС) = АВС. Свойствами коммутативности и ассоциативности обладают многие операции. Чтобы не создалось впечатления, что коммутативность и ассоциативность являются общими свойствами всех операций, приведем пример неассоциативной операции - возведение в степень. Имеем: (23)2 = 82 = 64; = 28 = 512. Пример некоммутативной операции - операция умножения матриц (АВВА). 3. Операции объединения и пересечения взаимно дистрибутивны. Для вещественных чисел закон дистрибутивности читается так: а(в+с) = ав + ас. Для множеств закон дистрибутивности имеет вид: а) (АВ)С = (АС)  (ВС) б) (АB) С = (АС)  (ВС). Докажем равенство а). Предположим, что x (АВ) С, тогда xС и xА или xВ. Рассмотрим первый случай xС и xА. Тогда хАС, а значит, по определению объединения, х(АС)(ВС). Во втором случае, т.е. при xС и xВ получаем, что x (ВС)(АС). Таким образом, мы доказали включение [(АВ) С][(АС)(ВС)]. Докажем обратное включение. Пусть х(АС)(ВС), тогда хАС или хВС. В первом случае хА и хС. Во втором случае хВ и xС. В обоих случаях получаем, что хС и хА или хВ. Следовательно, х(АВ) С. Тем самым доказано включение (АС)(ВС)(АВ) С. Таким образом, (АВ) С=(АС)(ВС), что и требовалось доказать. Пусть А1, А2, . . . - некоторые множества и пусть все они включены в S (А1, А2, . . .  S). Тогда выполняются следующие соотношения. 4. - дополнение объединения множеств равно пересечению их дополнений. 5. - дополнение пересечения множеств равно объединению их дополнений. Докажем свойство 4. Пусть х, тогда хзначит, x не принадлежит ни одному из множеств Ak (k, хАk), следовательно, по определению дополнения хS\Аk для любого k. Отсюда вытекает, что х. Обратно, пусть х тогда этот элемент принадлежит каждому из множеств S \ Ak (k, хS\ Ak). Следовательно, хAk для любого k, а, значит, х и поэтому х, что и требовалось доказать. ЛЕКЦИЯ № 2 Отображения Пусть Х - некоторое числовое множество. Говорят, что на множестве Х определена функция f, если каждому числу xХ ставится в соответствие определенное число y=f(x). Множество Х – область определения функции, а множество Y={f(x) | xX} - область значений функции. Если в качестве множеств Х и Y рассматривать множества произвольной природы, а не только числовые, мы приходим к понятию отображения. ОПРЕДЕЛЕНИЕ. Пусть А и В - два произвольных множества. Говорят, что на А определено отображение f, принимающее значения из В (f : A B), если каждому элементу x из А ставится в соответствие  _единственный . элемент y= f(x) из B. Множество элементов xA, для которых определено отображение f, называется областью определения f и обозначается f. Если имеется какой-либо элемент хА, то соответствующий ему элемент yB будем называть образом x. Пусть C - некоторое подмножество множества A, образом множества C называется множество вида {f(x) | xC}. Образ области определения называется областью значений отображения f и обозначается f (т.е. f =f(f)=f(X)). Если задать yВ, то множество соответствующих ему x, т.е. таких, что y = f(x) будем называть прообразом y и обозначать f-1(y), f-1(y)={xX | y = f(x)}. В общем случае обратное отображение f-1 неоднозначно. Отображение i : A  A такое, что i(x)=x для любого xA называется тождественным отображением. Пусть f : A  B и g : B  C. Отображение h : A  C, такое, что каждому элементу xA ставится в соответствие единственный элемент h(x) = g(f(x)), называется композицией (или суперпозицией) отображений f и g и обозначается g o f. Отображение f : А  В называется сюръекцией А на В, если множество образов всех элементов из А совпадают с множеством В. Это обозначается как f(А) = В. Другое эквивалентное определение сюръекции - это отображение, при котором каждый элемент из В имеет прообраз в множестве А. Если для любых x1, x2A таких, что x1x2, получается, что f(x1)f(x2), т.е. разным элементам соответствуют различные образы, то это отображение f называется инъекцией. Отображение f, которое является одновременно сюръекцией и инъекцией, называется биекцией, или взаимно однозначным отображением.  Если между А и В установлено биективное отображение, то говорят, что множества А и В эквивалентны. Эквивалентность множеств обозначается A~B. Основные свойства отображений можно сформулировать в виде следующих теорем. ТЕОРЕМА 1. f -1(AB) = f -1(A)f -1(B) - прообраз объединения двух множеств равен объединению их прообразов. ДОКАЗАТЕЛЬСТВО. Пусть xf -1(A)f -1(B). Тогда или xf -1(A) или хf -1(B). В первом случае y=f(x)А, во втором yВ. В любом случае yАВ, поэтому xf-1(AB). Докажем обратное включение. Пусть xf -1(AB), тогда y=f(x)AB. Значит или yА, или yВ. Если yА, то f -1(y)  f -1(A). Так как xf -1(y), то отсюда следует, что xf -1(A). Если же yВ, то f -1(y)f -1(B), что влечет xf -1(В). В любом случае   xf -1(A)f -1(B). Поэтому, если xf -1(AB), то xf -1(A)f –1(B), что и требовалось доказать. ТЕОРЕМА 2. f -1(AB)=f -1(A)f -1(B) - прообраз пересечения двух множеств равен пересечению их прообразов. ДОКАЗАТЕЛЬСТВО. Пусть xf -1(AB), тогда y=f(x)AB. Значит, yА и yВ. Если yА, то f -1(y)f -1(A), а если yВ, то f -1(y)f -1(B). Эти включения должны выполняться одновременно, следовательно, f -1(y)f -1(A)f -1(B), а значит, хf -1(A)f -1(B). Таким образом, f -1(AB)f -1(A)f -1(B). Докажем обратное включение. Пусть xf -1(A)f -1(B), тогда xf -1(A) и xf -1(B). Если xf -1(A), то y=f(x)A. Если же xf -1(B), то y=f(x)B. Так как yA и yB, то yAB и поэтому f -1(y)  f -1(AB). Значит,  хf -1(AB) и отсюда следует, что f -1(A)f -1(B)  f -1(AB). Эти два включения означают, что f -1(AB)=f -1(A)f -1(B), что и требовалось доказать. ТЕОРЕМА 3. Образ объединения двух множеств равен объединению их образов. ДОКАЗАТЕЛЬСТВО. Пусть yf(AB), тогда для любого x из множества f -1(y) выполняется принадлежность хAB. Поэтому xA или xB. В первом случае y=f(x)f(A), во втором случае y=f(x)f(B). Так как yf(A) или yf(B), то yf(A)f(B) и, следовательно, f(AB)f(A)f(B). Докажем обратное включение. Пусть yf(A)f(B), тогда yf(A) и f -1(y)A или yf(B) и f -1(y)B. Соответственно получаем, что xA или xB, т.е. xAB и тогда y=f(x) f(AB). Доказано включение f(A)f(B)f(AB). Следовательно, f(AB)=f(A)f(B). ЗАМЕЧАНИЕ. Образ пересечения двух множеств не обязательно совпадает с пересечением их образов. Рассмотрим пример. Пусть A и B - множества точек на плоскости: A = { (x, y) | 0  x  1, y=2 }, B = { (x, y) | 0  x  1, y=1 }. С помощью проектирования точек на ось ОХ построим отображение А и В на множество С = { (x, y) | 0  x  1, y=0 }. Так как f(A) = C, f(B) = C, то f(A)f(B) = C. Но множества A и B не пересекаются и f(AB)=f()=, т.е. мы показали, что f(AB) f(A)f(B). Теоремы 1, 2, 3 остаются в силе при любом конечном и бесконечном числе множеств. Например, теорема 1 примет вид: где A1, A2, . . . - некоторая система множеств. Докажем (1) с помощью метода математической индукции. 1. При n=2 равенство f -1(A1A2)=f -1(A1)f -1(A2) справедливо согласно доказанной теореме 1. 2. Предположим, что равенство верно при любом n  k. 3. Докажем, что равенство верно при n = k+1. Обозначим B = . Тогда f -1()=f -1(BAk+1)= f -1(B)f -1(Ak+1), так как для двух множеств В и Ak+1 теорема верна. Но по предположению индукции для k множеств теорема также верна, поэтому f -1(B)=. Отсюда следует требуемое равенство. Множества, между которыми можно установить биективное отображение называются эквивалентными. Легко видеть, что эквивалентность множеств обладает свойством транзитивности, т.е. если A~B и B~C, то A~C. Признаки эквивалентности множеств дают следующие ТЕОРЕМЫ Кантора-Бернштейна. 1. Если ABC, причем A~C, то A~B. 2. Если A эквивалентно подмножеству множества B, а B эквивалентно подмножеству множества A, то A~B. Мощность множества Рассмотрим множество всех молекул в земной атмосфере. Это множество содержит очень большое число элементов (примерно 1.02 77 010 541 0), но оно конечное, т.е. существует такая константа, которая больше числа элементов этого множества. Помимо конечных существуют бесконечные множества. Одной из задач теории множеств является определение числа элементов множества и исследование вопроса о сравнении друг с другом двух множеств по количеству элементов. Для конечных множеств самой разной природы эта задача легко решается непосредственным подсчетом. Для бесконечных множеств вопрос о сравнении невозможно решить как для конечных, с помощью подсчета. Поэтому Кантор предложил для сравнения двух бесконечных множеств установить между ними взаимно однозначное (биективное) отображение. Рассмотрим примеры установления такого отображения. Пример 1. В качестве множества А рассмотрим интервал на числовой прямой, пусть А=(-1, 1), а в качестве множества В - множество действительных чисел R. Это множества одинаковой мощности, т.к отображение f(x) = tg(x/2), хА позволяет установить между ними искомое взаимно-однозначное соответствие. Пример 2. Пусть А = [-1,1], В = (-1,1). Строим отображение f : A  B по следующему правилу: выделим в А последовательность -1, 1, 1/2, 1/3, 1/4, . . . , 1/n и положим f(-1)=1/2, f(1)=1/3, f(1/2)=1/4, f(1/3)=1/5, т.е. f(1/n) = 1/(n+2), а все точки, не входящие в эту последовательность отобразим сами в себя, т.е. f(x) = =x. Следовательно, открытый и замкнутый интервалы эквивалентны. Мощность множества является обобщением понятия числа элементов множества. Если взаимно однозначное отображение множеств установлено, значит, по определению, в обоих множествах одинаковое число элементов или мощность одного множества равна мощности другого множества. Мощность - это то общее, что есть у двух эквивалентных множеств. Мощность множества A обозначается m(A) или |A|. Таким образом, m(A)=m(B), если A~B. Если множество A эквивалентно какому-либо подмножеству множества B, то мощность A не больше мощности B (т.е. m(A)m(B)). Если при этом множество B не эквивалентно никакому подмножеству множества A, то m(A)< m(B). ЛЕКЦИЯ № 3 Свойства счетных множеств Простейшим среди бесконечных множеств является множество натуральных чисел  N. ОПРЕДЕЛЕНИЕ. Назовем счетным всякое множество, эквивалентное множеству  N. Другими словами, счетным называется всякое множество, элементы которого можно перенумеровать или составить из них бесконечную последовательность. Примеры счетных множеств. 1. Множество целых чисел Z={0, 1, 2, . . .}.Построим из его элементов последовательность: a1=0; a2=-1; a3=1; a4=-2; a5=2; . . . Формулу для вычисления ее общего члена можно записать в виде 2. Множество Q всех рациональных чисел. Докажем счетность этого множества. Как известно, рациональные числа - это дроби вида p/q, где pZ, qN. Запишем их в виде таблицы из бесконечного числа строк и столбцов 0/11/1 2/13/1 . . . -1/1 -2/1 -3/1 -4/1 . . .  1/2 2/2 3/2 4/2 . . . -1/2 -2/2 -3/2 -4/2 . . . . . . . . . . . . . . . . Из элементов этой таблицы построим последовательность по следующему правилу a1=0/1; a2=1/1; a3=-1/1; a4=1/2; a5=-2/1; a6=2/1 и т.д., двигаясь в направлении, указанном стрелками. Очевидно, в эту последовательность войдут все рациональные числа. Более того, в ней многие числа будут повторяться. Следовательно, мощность множества элементов данной последовательности не меньше мощности множества рациональных чисел. С другой стороны, эта последовательность эквивалентна натуральному ряду, т.е. подмножеству множества Q, а значит она не может иметь мощность, большую чем  Q. Значит, множество рациональных чисел счетно. Бесконечное множество не являющееся счетным называется несчетным. 1. Всякое подмножество счетного множества конечно или счетно. ДОКАЗАТЕЛЬСТВО. Пусть А - счетное множество и BА. Поскольку А счетно, то занумеруем его элементы и построим из них последовательность a1, a2, a3, . . . Из этой последовательности выделим все элементы, принадлежащие множеству B, т.е. рассмотрим последовательность an1, an2, an3, . . . Возможны следующие случаи: 1) множество B конечно; 2) множество B бесконечно. Поскольку элементы множества B занумерованы, то во втором случае оно является счетным, что и требовалось доказать. 2. Объединение любого конечного или счетного множества счетных множеств снова является счетным. ДОКАЗАТЕЛЬСТВО. Пусть множества А1, A2, . . . , Аn, . . . – счетные. Если их число не более, чем счетно, то множества можно занумеровать и расположить принадлежащие им элементы в таблицу А1={a11, a12, a13, . . .} А2={a21, a22, a23, . . .} А3={a31, a32, a33, . . .} . . . . . . . . . . . . . . . . . Пусть B=. Построим последовательность подобно тому, как это было сделано в п. 4 при доказательстве счетности Q. b1=a11, b2=a12, b3=a21, b4=a31, b5=a22, . . . (1) Если множества Аi попарно пересекаются (Аi Аj ), то в последовательность (1) не включаются те элементы, которые уже занумерованы. Таким образом, построено взаимно однозначное соответствие между множествами B и N. Следовательно, множество B счетно. 3. Всякое бесконечное множество содержит счетное подмножество. ДОКАЗАТЕЛЬСТВО. Пусть М - произвольное бесконечное множество. Выберем в нем произвольный первый элемент и обозначим его a1 , затем - элемент a2 и т.д. Получаем последовательность a1, a2, . . . , которая не может оборваться на каком-то элементе, так как М бесконечно. Следовательно, данная последовательность образует счетное подмножество множества М. Доказанная теорема позволяет утверждать, что среди бесконечных множеств счетное множество является самым "маленьким". Если множество конечно или счетно то говорят, что оно не более, чем счетно. Рассмотренные примеры и свойства могут создать впечатление, что все бесконечные множества счетны. Однако, это далеко не так, и для доказательства этого достаточно построить контрпример, т.е. предъявить бесконечное множество, не являющееся счетным. ТЕОРЕМА. Множество всех бесконечных бинарных последовательностей, т.е. состоящих из 0 и 1, несчетно. ДОКАЗАТЕЛЬСТВО. Предположим противное, т.е. что эти последовательности можно занумеровать. Пусть P1, P2, . . . - последовательности, где P1={a11, a12, a13, . . .}, P2={a21, a22, a23, . . .} и т.д., где аij=0 или аij=1. Построим последовательность P, не содержащуюся в этом списке. Такая последовательность существует, например, P={1-a11, 1-a22, 1-a33, . . .}. Очевидно, что ее элементы равны  0 или 1, причем она не равна никакой другой из списка, потому что отличается от последовательности P1 по крайней мере первым элементом, от P2 - по крайней мере вторым и т.д. Таким образом, построенная последовательность отличается от любой из занумерованных последовательностей хотя бы одним элементом. Следовательно, множество всех бинарных последовательностей занумеровать невозможно, а это означает, что оно несчетно. Множества мощности континуума и выше Другим важным примером бесконечного несчетного множества является множество вещественных чисел R. Дадим одно из возможных определений вещественного числа с помощью сечений Дедекинда. Рассмотрим разбиение множества всех рациональных чисел на два непустых подмножества А и В. Будем называть это разбиение сечением и обозначать А|В, если выполняются условия: 10. Каждое рациональное число попадает в одно и только одно из множеств А или В. 20. Для всех xA и yB имеет место соотношение y > x. Назовем А нижним классом сечения, В - верхним классом. Существуют сечения трех типов. 1. Сечение, у которого в нижнем классе нет максимального числа, а в верхнем классе есть минимальное число, назовем сечением первого типа. 2. Сечение, у которого в нижнем классе есть максимальный элемент, а в верхнем классе нет минимального число, назовем сечением второго типа. 3. Сечение, у которого в нижнем классе нет максимального элемента, а в верхнем классе - минимального, назовем сечением третьего типа. Примеры сечений: 1) А ={ x | x<1 }; B ={ x | x1 } - сечение 1-го типа; 2) А ={ x | x1 }; B ={ x | x>1 } - сечение 2-го типа; 3) А ={ x | x32 }; B ={ x | x3 >2 } - сечение 3-го типа. Докажем что в третьем примере нижний класс не содержит максимальный элемент. Для этого покажем, что  аA  n>0  : (a + 1/n)3 < 2. Так как (a+1/n)33a2/(2-a3). Иными словами, какое бы рациональное а из A мы ни выбрали, в классе А всегда можно найти число больше его. Аналогично можно доказать, что в этом примере в верхнем классе нет минимального элемента. Сечения типа 1 и 2 определяют рациональное число r. Для сечения 1 типа это число - наименьшее в верхнем классе, для сечения 2 типа - наибольшее в нижнем классе. Сечение 3 типа не определяет никакого рационального числа, так как предположение противного противоречит определению сечения. Будем говорить, что сечение 3-го типа определяет иррациональное число  , если для любых рациональных чисел xA и yB выполняется неравенство x<0, т.е. носитель A = {x/A(x)>0}  xE. • Элементы xE, для которых A(x)=0,5 называются точками перехода множества A. Примеры нечетких множеств 1. Пусть E = {0,1,2,..,10}, M =[0,1]. Нечеткое множество "несколько" можно определить следующим образом: "несколько" = 0,5/3+0,8/4+1/5+1/6+0,8/7+0,5/8; его характеристики: высота = 1, носитель={3,4,5,6,7,8}, точки перехода - {3,8}. 2. Пусть E = {1,2,3,...,100} и соответствует понятию "возраст", тогда нечеткое множество "молодой", может быть определено с помощью "молодой"(x) = . Нечеткое множество "молодой" на универсальном множестве E' ={Иванов, Петров, Сидоров,...} задается с помощью функции принадлежности "молодой"(x) на E = {1,2,3,..100} (возраст), называемой по отношению к E' функцией совместимости, при этом: "молодой"(Сидоров):= "молодой"(x), где x - возраст Сидорова. 3. Пусть E = {Запорожец, Жигули, Мерседес,....} - множество марок автомобилей, а E' = [0,) - универсальное множество "стоимость", тогда на E' мы можем определить нечеткие множества типа: "для бедных", "для среднего класса", "престижные", с функциями принадлежности типа: Имея эти функции и зная стоимости автомобилей из E в данный момент времени, мы тем самым определим на E' нечеткие множества с этими же названиями. Так, например, нечеткое множество "для бедных", заданное на универсальном множестве E = {Запорожец, Жигули, Мерседес,....} выглядит следующим образом: Аналогично можно определить Нечеткое множество "скоростные", "средние", "тихоходные" и т.д. О методах построения функций принадлежности нечетких множеств В приведенных выше примерах использованы прямые методы, когда эксперт либо просто задает для каждого xE значение  A(x), либо определяет функцию совместимости. Как правило, прямые методы задания функции принадлежности используются для измеримых понятий, таких как скорость, время, расстояние, давление, температура и т.д., или когда выделяются полярные значения. Во многих задачах при характеристике объекта можно выделить набор признаков и для каждого из них определить полярные значения, соответствующие значениям функции принадлежности, 0 или 1. Например в задаче распознавания лиц можно выделить следующие шкалы:     1 x1 высота лба низкий широкий x2 профиль носа курносый горбатый x3 длина носа короткий длинный x4 разрез глаз узкие широкие x5 цвет глаз светлые темные x6 форма подбородка остроконечный квадратный x7 толщина губ тонкие толстые x8 цвет лица темный светлый x9 очертание лица овальное квадратное Для конкретного лица А эксперт, исходя из приведенной шкалы, задает A(x) [0,1], формируя векторную функцию принадлежности { A(x1), A(x2),... A(x9)}. При прямых методах используются также групповые прямые методы, когда, например, группе экспертов предъявляют конкретное лицо и каждый должен дать один из двух ответов: "этот человек лысый" или "этот человек не лысый", тогда количество утвердительных ответов, деленное на общее число экспертов, дает значение  "лысый" (данного лица). (В этом примере можно действовать через функцию совместимости, но тогда придется считать число волосинок на голове у каждого из предъявленных эксперту лиц). Косвенные методы определения значений функции принадлежности используются в случаях, когда нет элементарных измеримых свойств, через которые определяется интересующее нас нечеткое множество. Как правило, это методы попарных сравнений. Если бы значения функций принадлежности были нам известны, например, A(xi) = wi, i=1,2,...,n, то попарные сравнения можно представить матрицей отношений A = {aij}, где aij=wi/wj (операция деления). На практике эксперт сам формирует матрицу A, при этом предполагается, что диагональные элементы равны 1, а для элементов симметричных относительно диагонали aij = 1/aij, т.е. если один элемент оценивается в  раз сильнее чем другой, то этот последний должен быть в 1/ раз сильнее, чем первый. В общем случае задача сводится к поиску вектора w, удовлетворяющего уравнению вида Аw = maxw, где max - наибольшее собственное значение матрицы A. Поскольку матрица А положительна по построению, решение данной задачи существует и является положительным. Операции над нечеткими множествами Включение. Пусть A и B - нечеткие множества на универсальном множестве E. Говорят, что A содержится в B, если x E A(x) B(x). Обозначение: A  B. Иногда используют термин "доминирование", т.е. в случае когда A  B, говорят, что B доминирует A. Равенство. A и B равны, если xE A(x) = B (x). Обозначение: A = B. Дополнение. Пусть  = [0,1], A и B - нечеткие множества, заданные на E. A и B дополняют друг друга, если xE A(x) = 1 -  B(x). Обозначение: B = или A = . Очевидно, что = A. (Дополнение определено для M = [0,1], но очевидно, что его можно определить для любого упорядоченного M). Пересечение. AB - наибольшее нечеткое подмножество, содержащееся одновременно в A и B. AB(x) = min( A(x),  B(x)). Объединение. А  В - наименьшее нечеткое подмножество, включающее как А, так и В, с функцией принадлежности: A B(x) = max(A(x),  B(x)). Разность. А - B = А с функцией принадлежности: A-B(x) = A  (x) = min( A(x), 1 -  B(x)). Дизъюнктивная сумма. АB = (А - B)(B - А) = (А ) ( B) с функцией принадлежности: A-B(x) = max{[min{ A(x), 1 - B(x)}];[min{1 - A(x), B(x)}] } Примеры. Пусть: A = 0,4/ x1 + 0,2/ x2+0/ x3+1/ x4; B = 0,7/ x1+0,9/ x2+0,1/ x3+1/ x4; C = 0,1/ x1+1/ x2+0,2/ x3+0,9/ x4. Здесь: 1. AB, т.е. A содержится в B или B доминирует A, С несравнимо ни с A, ни с B, т.е. пары {A, С} и {A, С} - пары недоминируемых нечетких множеств. 2. A  B  C. 3. = 0,6/ x1 + 0,8/x2 + 1/x3 + 0/x4; = 0,3/x1 + 0,1/x2 + 0,9/x3 + 0/x4. 4. AB = 0,4/x1 + 0,2/x2 + 0/x3 + 1/x4. 5. АВ = 0,7/x1 + 0,9/x2 + 0,1/x3 + 1/x4. 6. А - В = А = 0,3/x1 + 0,1/x2 + 0/x3 + 0/x4; В - А =  В = 0,6/x1 + 0,8/x2 + 0,1/x3 + 0/x4. 7. А  В = 0,6/x1 + 0,8/x2 + 0,1/x3 + 0/x4. Наглядное представление операций над нечеткими множествами    Для нечетких множеств можно строить визуальное представление. Рассмотрим прямоугольную систему координат, на оси ординат которой откладываются значения A(x), на оси абсцисс в произвольном порядке расположены элементы E (мы уже использовали такое представление в примерах нечетких множеств). Если E по своей природе упорядочено, то этот порядок желательно сохранить в расположении элементов на оси абсцисс. Такое представление делает наглядными простые операции над нечеткими множествами.         На верхней части рисунка заштрихованная часть соответствует нечеткому множеству A и, если говорить точно, изображает область значений А и всех нечетких множеств, содержащихся в A. На нижней - даны , A , A . Свойства операций  и . Пусть А, В, С - нечеткие множества, тогда выполняются следующие свойства: • - коммутативность; • - ассоциативность; • - идемпотентность; • - дистрибутивность; • A = A, где  - пустое множество, т.е. (x) = 0 >xE; • A = ; • AE = A, где E - универсальное множество; • AE = E; • - теоремы де Моргана. В отличие от четких множеств, для нечетких множеств в общем случае: A  , A  E. (Что, в частности, проиллюстрировано выше в примере наглядного представления нечетких множеств). Замечание. Введенные выше операции над нечеткими множествами основаны на использовании операций max и min. В теории нечетких множеств разрабатываются вопросы построения обобщенных, параметризованных операторов пересечения, объединения и дополнения, позволяющих учесть разнообразные смысловые оттенки соответствующих им связок "и", "или", "не". Один из подходов к операторам пересечения и объединения заключается в их определении в классе треугольных норм и конорм. ЛЕКЦИЯ № 5 Бинарные отношения и операции над ними ОПРЕДЕЛЕНИЕ. Пусть А1, А2, . . . , Аn - некоторые множества. Их прямым или декартовым произведением называется множество упорядоченных наборов из n элементов, т.е. А1А2 . . . Аn={(а1, а2, . . . , аn) | aiAi }. Если все множества Ai совпадают A=А1=А2= . . . =Аn, то прямое произведение А1А2 . . . Аn=An называют прямой n-ой степенью множества А. Бинарным отношением между элементами множеств А и В называется любое подмножество RAB. Если множества A и B совпадают А=В, то R называют бинарным отношением на множестве А. Если (x, y)R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R. Приведем примеры бинарных отношений. Пусть A=B=R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение R1 = { (x, y) | x2 + y2 1 } определяет замкнутый круг единичного радиуса с центром в точке (0,0) на плоскости, отношение R2 = { (x, y) | x  y } полуплоскость, а отношение R3= { (x, y) |  |x-y|  1 } полосу. Диагональ множества AA, т.е. множество ={(x,x) | xA}, называется единичным бинарным отношением или отношением равенства в A. Областью определения бинарного отношения R называется множество R={ xA | yB, (x, y) R }. Областью значений бинарного отношения R называется множество R={ yB |  xA, (x, y)R }. Образом множества X относительно отношения R называется множество R(X) = { yB | xX, (x, y)R }; прообразом X относительно R называется R -1(X). В теории выбора и принятия решений большую роль играют бинарные отношения предпочтения, то есть такие отношения, согласно которым в паре (x, y)R элемент x в каком-то смысле лучше чем y. Например: - в смысле отношения R2 "лучше" означает "больше или равно"; - в смысле отношения R3 понятие "лучше" может означать "отстоит не больше чем на единицу". Операции над бинарными отношениями определяются подобно операциям над соответствующими множествами. Пусть А – произвольное множество на котором введены бинарные отношения R, R1, R2,... 1) Объединение двух бинарных отношений R1 и R2 - это отношение R1R2 = { (x, y) | (x, y)R1 или (x, y)R2 }. 2) Пересечение двух бинарных отношений R1 и R2 - это отношение R1R2 = { (x, y) | (x, y)R1 и (x, y)R2 }. 3) Обратное отношение R –1 = { (x, y) | (y, x)R}. 4) Дополнение к отношению ={ (x, y) | (x, y)(AA)\R}. 5) Двойственное отношение Rd = . 6) Композиция (суперпозиция) отношений R=R1oR2  содержит пару (x, y) тогда и только тогда, когда существует такое zA, что (x, y)R1 и (z, y)R2. 7) R1 содержится в R2 (R1  R2), если любая пара (x, y), которая принадлежит отношению R1, также принадлежит и отношению R2. Свойства операций над отношениями Приведем здесь список основных свойств операций над отношениями и докажем некоторые из них. 1)  Rk -1=( Rk -1. k k 2)  Rk -1=( Rk  -1. k k 3) (R1 o R2) -1 = R1 -1o R2 -1. 4) (R1 o R2 )oR3 = R1o(R2 o R3). 5) (R1  R2 )oR3 = (R1 oR3 )( R2o R3 ). 6) (R1  R2 )oR3  (R1 oR3 )( R2o R3 ). 7)  а) если R1 R2 то R1o R3 R2o R3; б) если R1  R2 то R1-1 R2-1; в) если R1  R2 то R3oR1  R3oR2. 8) a) (R1 R2)d = R1d R2d; б) (R1 R2)d = R1d R2d; в) (R d)d = R. ДОКАЗАТЕЛЬСТВО. Свойство 2. Пусть пара (x, y)( Rk  -1. Тогда (y, x) Rk. Это означает, что найдется отношение Rj, что (y, x) Rj. Отсюда, по определению обратного отношения, (x, y)Rj-1, а значит, (x, y)Rk-1и (Rk-1   Rk-1. Докажем обратное включение. Пусть (x,y) Rk-1 Это означает, что найдется такое множество Rj, что (x,y)Rj-1. Следовательно, (y, x)Rj  и (y, x) Rk , поэтому (x, y)( Rk -1. Значит,    Rk-1  (Rk-1. Одновременное выполнение обоих включений означает равенство множеств, что и требовалось доказать. Свойство 6. Пусть (x, y)(R1 R2)oR3. По определению композиции это означает, что найдется такое zA, что (x, z)(R1R2) и (z, y)R3. Первое включение возможно только тогда, когда одновременно выполнено (x, z)R1 и (x, z)R2. Это, в свою очередь означает, с учетом (z, y)R3, что одновременно (x, y)R1oR3 и (x, y)R2oR3, а, следовательно, (x, y)(R1oR3)(R2oR3), что и доказывает требуемое соотношение. ЗАМЕЧАНИЕ. Покажем, почему неверно обратное включение. Пусть (x, y)(R1oR3)(R2oR3), тогда (x, y) (R1oR3) и (x, y) (R2oR3). Первое включение означает существование такого элемента z1  из A, что (x, z1)R1 и (z1, y)R3, второе - существование такого z2A, что (x, z2)R2 и (z2, y)R3, причем необязательно z1=z2. Значит, не всегда существует такой элемент z, что (x, z)R1 и (x, z)R2, а, следовательно, не будет принадлежности пересечению R1 и R2. Свойство 7б. Возьмём любую пару (x, y)R1, что эквивалентно (y, х) R1-1. Пусть теперь R1R2, т.е. из (x, y)R1 следует (x, y)R2. Перейдя к обратным отношениям, получим, что из (y, х)R1-1 вытекает (y, х)R2-1, что и означает требуемое свойство. Свойство 8а. Докажем предварительно равенство = Пусть (x, y) . Следовательно, (y, x) R или, другими словами, (y, x)R. Отсюда, ( x, y) R-1, что означает  и (x, y)R-1 . Если же (x, y) R-1 , то (x, y)R-1 и (y, x)R. Тогда (y, x)R или, что то же самое, (x,y)(R )-1. Для доказательства свойства 8а воспользуемся доказанным равенством и известными свойствами операций над множествами и отношениями. (R1R2)d = ( R1R2)-1 = R1R2-=(R1R2) =R1-1  R2-1 = R1d  R2d. Способы задания бинарных отношений Традиционное задание отношений аналогично тому, как это принято в теории множеств, что не всегда удобно. Поэтому, наряду с таким заданием, применяются другие способы. 1. Матричное задание. Оно используется когда А - конечное множество А={xi}. Тогда отношение R можно задавать с помощью матрицы R={xij}, элементы которой определяются соотношением: 2. Задание с помощью графа. Для конечного множества А отношение можно задавать с помощью графа Г(R), который является геометрическим образом бинарного отношения. Граф - фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть xi, а наличие дуги, соединяющей вершины xi и xj, означает, что (xi,xj)R. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка. Основные свойства графа. 1) Г(R-1) получается из Г(R) изменением направления стрелок на противоположные. 2) Граф Г(АА) содержит дуги, соединяющие любую пару (xi, xj). Такой граф назывыется полным. 3. Задание верхними и нижними срезами. Этот способ может быть использован для любых множеств и отношений. Пусть на множестве А задано отношение R. Верхний срез GR (x) отношения R в точке x А - это множество элементов yА таких, что (y, x)R, т.е. GR(x) = { yA | (y, x)R }. Если рассматривать R как отношение предпочтения, то GR (x) – это множество элементов, лучших чем х. Нижний срез HR(x) отношения R в точке xА - это множество элементов yА, таких, что (x, y)R, т.е. HR(x) = { yA | (x, y)R }.   Свойства нижних и верхних срезов. Для любого хA и любого отношения Ri AA выполняются соотношения. 1. а) GRR(x)=GR(x)GR(x); б) HRR(x)=HR(x)HR(x) 2. a) GR(x) = A\GR(x); б)HR(x) = A\HR(x). 3. a) GR-1(x) = HR(x); б) HR-1(x) = HR(x). 4. GAA(x) = HAA(x) = A. ЛЕКЦИЯ № 6 Свойства бинарных отношений 1) Рефлексивность. Отношение R называется рефлексивным, если (х, х)R для любого хA. Примеры рефлексивных отношений: отношения "", "" на множестве R. 2) Антирефлексивность. Отношение R называется антирефлексивным, если (х, х)R для любого хA. Примеры антирефлексивных отношений: отношения "<", ">" на множестве R. Если R - антирефлексивное отношение, то xGR(x) и хHR(x) для любого хA . 3) Симметричность. Отношение R называется симметричным, если для любых x,yA из того, что (x, y)R следует (y, x)R и обратно. Примеры симметричных отношений: отношения "=" и "". Если отношение R симметрично, то для любого хA а) GR(x) = HR(x); б) R = R-1. 4) Антисимметричность. Отношение R называется антисимметричным, если для любых x и y из A из одновременного выполнения условий (x, y)R и (y, x)R следует, что x = y. Пример антисимметричного отношения. Пусть А - множество людей в данной очереди. Отношение R "не стоять за кем-то в очереди" будет антисимметричным. Пусть х=ВАСЯ, а y=ИВАНОВ. Тот факт, что (x, y)R означает, что "ВАСЯ не стоит в очереди за ИВАНОВЫМ", (y, x)R - "ИВАНОВ не стоит за ВАСЕЙ". Очевидно, что одновременное выполнение обоих включений может быть, только если ВАСЯ и есть ИВАНОВ, т.е. x = y. Отношение "" также антисимметрично: если xy и yx, то x=y. 5) Асимметричность. Отношение R асимметрично, если R R-1= , т.е. пересечение отношения R с обратным отношением пусто. Эквивалентное определение асимметричности: из двух отношений (x, y)R и (y, x)R одно не выполняется. Примеры асимметричных отношений: ">", "<", "быть начальником". Если R - асимметричное отношение, то из xRy следует yRx. Для любого отношения R вводятся понятия симметричной части отношения Rs = R R-1 и асимметричной части отношения Ra = R \ Rs. Если отношение R симметрично, то R= Rs, если отношение R асимметрично, то R= Ra. Примеры. Если R - "", то R-1 - "<", Rs - "=", Ra - ">". 6) Транзитивность. Отношение R транзитивно, если для любыx x, y, zA из того, что (x, y)R и (y, z)R следует (x, z)R. Свойства транзитивного отношения: а) RoRR; б) для любого хA из yGR(x) следует, что GR(y)GR(x). Нетранзитивным является отношение "". Пусть x=2, y=3, z=2, тогда справедливо xy и yz, но x=z, т.е. (x, z)R. Отношение R1 называется транзитивным относительно отношения R2, если: а) из (x, y) R1 и (y, x) R2 следует, что (x, z) R1; б) из (x, y) R2 и (y, x) R1 следует, что (x, z) R1. 7) Негатранзитивность. Отношение R называется негатранзитивным, еслиR транзитивно. Примеры. Отношения R1 - ">" и  R2 - " " негатранзитивны, так как отно- шенияR1 - "",R2 - "=" транзитивны. Возможно одновременное выполнение свойств транзитивности и негатранзитивности. Например, отношение R1 одновременно транзитивно и негатранзитивно, а R2 , как известно, транзитивным не является. 8) Полнота. Отношение R полно, если для любых x,yА либо (x, y)R, либо (y, x)R, либо оба отношения выполняются одновременно. Свойства полных отношений: а) GR(x)HR(x) = А для любого хA; б) полное отношение рефлексивно. 9) Слабая полнота. Отношение R называется слабо полным, если для любых хy из А или (x, y)R, или (y, x)R. Пример слабо полного отношения. Пусть А - множество предприятий, "неблагополучных" в смысле своего бюджета. Отношение R "быть должным" является слабо полным, так как каждое из этих предприятий или кому-либо должно, или ему кто-то должен, но быть должным самому себе нельэя и (x, x)R. 10) Ацикличность. Бинарное отношение R ациклично, если Rn R-1=  для любого nN . Иными словами, если из любой конечной цепочки отношений хRу, уRt,..., vRz следует, что zх, то отношение R ациклично. Специальные бинарные отношения. Упорядочение и безразличие Для бинарных отношений нет устоявшейся терминологии. В данном пособии использованы названия специальных бинарных отношений из [5]. Бинарные отношения нас интересуют, прежде всего, с точки зрения теории принятия решений. Для этого необходимо построить такие отношения, свойства которых позволили бы их использовать в этой области. При принятия решений, как минимум, надо уметь из 2-х элементов выбрать лучший, т.е. нужно построить такое отношение предпочтения, минимально необходимым свойством которого, является асимметричность. Введем следующие отношения. Pуп - отношение строгого упорядочения, обладающее свойством асимметричности. Iуп - отношение безразличия. Это отношение исключает Pdуп между двумя элементами, т.е. x Iуп y <=> ( xPуп у и yPуп x ). (1) Так как (x, y) и (y, x) не принадлежат Pуп, то нельзя сказать, что x лучше y, или x лучше y. Если воспользоваться понятием пересечения отношений, то Iуп можно также представить в виде Iуп =Pуп Pdуп . (2) Покажем, что Iуп рефлексивно и симметрично. Симметричность. Отношение xIупy означает, что (x, y)Pуп и (y, x)Pуп. Отношение же yIупx означает, что (y, x)Pуп и (x, y)Pуп. Т.е. xIупy и yIупx абсолютно эквивалентны. Значит, Iуп симметрично. Рефлексивность. Так как Pуп антирефлексивно, то (x, x) Pуп и по определению (x, x)Iуп . Значит, Iуп рефлексивно. Можно дать другое определение отношения Iуп, как симметричного, рефлексивного отношения. На базе введенных отношений строгого упорядочения и безразличия можно построить новое отношение Rуп = Pуп Iуп, (3) которое называется нестрогим упорядочением. Докажем, что Rуп полно. ДОКАЗАТЕЛЬСТВО. Возьмем любую пару (x, y). Для нее возможны три случая: а) (x, y)Pуп; б) (y, x)Pуп; в) (x, y)Pуп и (y, x)Pуп, т.е. (x, y)Iуп. Если имеют место случаи а) или в), то по свойству объединения (x, y)Rуп. Если выполняется б) или в), то (y, х)Rуп. Иными словами, в любом случае либо пара (x, y), либо (y, x) принадлежит Rуп. Значит, Rуп полно. Свойство полноты можно взять за определение отношения Rуп. Рассмотрим основные свойства отношений Pуп и Rуп. 1. а) Pуп  Pdуп = Pdуп; б) Pуп  Pdуп = Pуп; в) I =Pуп  Pdуп . ДОКАЗАТЕЛЬСТВО. Докажем свойства а) и б). Пусть (x,y)Pуп. Тогда, в силу асимметричности, (y, x)Pуп, а значит, (x, y)Pdуп по определению двойственного отношения. Таким образом, из (x, y)Pуп следует (x, y) Pdуп, а это означает, что Pуп Pdуп. Тогда, по свойствам объединения и пересечения множеств, Pуп Pdуп = Pdуп, a Pуп = Pdуп Pуп, что и требовалось доказать. Докажем свойство в). Пусть (x, y)Iуп. Тогда, по определению Iуп, будем иметь (x, y) Pуп и (y, x) Pуп. Второе соотношение эквивалентно тому, что (x, y)Pdуп. Следовательно, из (x, y)Iуп одновременно вытекает (x, y)Pdуп и (x,y) Pуп , т.е. (x, y) PупPdуп и Iуп PPdуп. Докажем обратное включение. Ход рассуждений представим в виде схемы: Что и требовалось доказать. 2. Rуп = Pdуп; Pуп = Rdуп , т.е. Pуп и Rуп образуют двойственную пару. ДОКАЗАТЕЛЬСТВО. По определению Rуп = PупIуп . Воспользуемся представлением (2) отношения безразличия Iуп. Тогда Rуп = Pуп(Pуп Pdуп ) = (Pуп Pуп)( Pуп Pdуп). Так как (Pуп Pуп)=АА, то Rуп = Pуп Pdуп, а по свойству 1а) Rуп = Pdуп. Второе равенство непосредственно вытекает из свойства 8в п.2 для произвольного отношения R. При R=Pуп получим Rdуп=( Pdуп)d = Pуп. ЛЕКЦИЯ № 7 Слабый порядок Введенное отношение строгого упорядочения обладает слишком малым набором свойств, чтобы его можно было применить для решения практических задач организации выбора. Поэтому, кроме асимметричности нужны другие свойства, например, транзитивность или негатранзитивность. ОПРЕДЕЛЕНИЕ. Асимметричное, негатранзитивное отношение Pсл назовем слабым порядком. Кроме того, по аналогии с Iуп введем отношение Iсл  xIслy <=> ((x, y) Pсл и (y, x) Pсл) или xIслy <=> ((y, x)Pсл  и (x, y)Pсл). Назовем его отношением эквивалентности. Введем также отношение Rсл = Pсл Iсл, называемое нестрогим слабым порядком . Из определения следует, что Pсл  Pуп . Так как Pуп только асимметрично, а Pсл асимметрично и негатранзитивно, то из (x, y)Pсл всегда следует (x, y)Pуп. В качестве примера Rсл можно привести отношение "". Рассмотрим свойства слабого порядка и порожденных им отношений. 1) Rсл = Pdсл , Rdсл = Pсл. 2) Iсл = Rsсл , Pсл = Raсл. 3) Для любых x,yA выполняется одно и только одно из соот- ношений: xPслy, yPслx, xIслy. 4) Отношение Pсл транзитивно. 5) Отношение Iсл рефлексивно, симметрично, транзитивно. 6) Отношение Rсл транзитивно и полно. Докажем свойство 4). Для этого докажем вспомогательное утверждение, что любое отношение Р негатранзитивно тогда и только тогда, когда xPy   zА, xPz или zPy. (4) Предположим противное, что отношение Р негатранзитивно, но свойство (4) не выполняется, т.е. xPy и   z : xPz и zP y. (5) Так как Р негатранзитивно, то из (5) следует одновременное выполнение xРy и xPy, а этого быть не может, поэтому из негатранзитивности следует свойство (4). Докажем обратное следствие. Предположим противное, т.е. что (4) выполнено, но Р не является негатранзитивным. Последнее означает, что  x,y,zA : xPz, zPy, но (x, y) P, т.е. (x, y)P. Таким образом, получаем, что xPy выполняется, а xPz и zPy не выполняется, и, значит, (4) неверно, что противоречит предположению. Полученное противоречие доказывает требуемое следствие. Перейдем теперь непосредственно к доказательству свойства 4). Предположим, что x, y, z таковы, что выполняются соотношения xPслy и yPслz. Запишем для них условие (4): xPслy   z : xPслz или zPслy; yPслz   x : yPслx или xPслz. Вспомним, что отношение Pсл асимметрично, т.е. xPслy и yPслx, а также yPслz и zPслy не могут выполнятся одновременно. Поэтому, из xPслy может следовать только xPслz, а из yPслz - также только xPслz. Объединив оба этих следствия, получим, что xPслy и yPслz  xPслz, т.е. Pсл транзитивно. Докажем свойство 5). Ранее, в п.6, было доказано, что Iуп рефлексивно и симметрично. Аналогично доказывается рефлексивность и симметричность Iсл. Поэтому остается доказать транзитивность Iсл. Пусть x, y, zA таковы, что xIслy и yIслz, покажем, что (x, z)Iсл. По определению Iсл, отношение xIслy эквивалентно выполнению условий (x, y)Pсл и (y, x)Pсл, а отношение yIслz - (y, z)Pсл и (z, y)Pсл. В силу негатранзитивности Pсл получим, что (x, z)Pсл и (z, x)Pсл. Следовательно, (x, z)Iсл по определению Iсл. ЗАМЕЧАНИЕ. Свойства рефлексивности, симметричности и транзитивности считают определяющими свойствами отношения эквивалентности. Разбиение и эквивалентность ОПРЕДЕЛЕНИЕ. Система ( конечная или бесконечная ) непустых подмножеств А1, А2,..., Аn... множества А называется разбиением, если: 1) объединение множеств Аi образуют все A (т.е. Аi=А); 2) множества Аi попарно не пересекаются (т.е. для любых ij справедливо АiAj =  ). ТЕОРЕМА о разбиении. Отношение IАА, будет отношением эквивалентности тогда и только тогда, когда существует разбиение А1, А2,..., Аn,... множества А, что из xIy следует существование такого Аi, что x, yАi. Другими словами, отношение I является отношением эквивалентности в том и только в том случае, когда множество А можно разбить на пересекающиеся классы, в каждом из которых все элементы эквивалентны между собой. ДОКАЗАТЕЛЬСТВО. Предположим, что I - отношение эквивалентности, т.е. оно является рефлексивным, симметричным, транзитивным. Наша задача - построить такое разбиение, чтобы между элементами каждого класса выполнялось отношение I. Введем для каждого xА множество Вx, состоящее из элементов эквивалентных х, т.е. Вx = {zA | xIz }. Покажем, что два множества Bx и By либо совпадают, либо не пересекаются. Пусть zBx By. Это означает, что одновременно zIx и zIy. Тогда, в силу симметричности и транзитивности, получаем xIy. Пусть теперь v - произвольный элемент из Bx, т.е. выполнено отношение vIx. Тогда, вследствие транзитивности отношения I и xIy, получим vIy, т.е. vBy. Точно также можно доказать, что если vBx. Это означает, что всякий элемент v из Bx одновременно принадлежит и By и наоборот. Следовательно, два множества Bx и By, имеющие хотя бы один общий элемент, совпадают между собой. Наконец, в силу того, что множества Bx построены для всех элементов х из A, и, в силу рефлексивности I, элемент х принадлежит своему множеству Bx, их объединение включает в себя все множество A. Это означает, что система {Bx} образует разбиение A, т.е. в одну сторону теорема доказана. Докажем обратное. Пусть имеем разбиение множества А на непересекающиеся классы. Определим отношение I следующим образом: элемент x находится с элементом y в отношении I тогда и только тогда, когда они оба принадлежат одному классу. Тогда это отношение обладает свойством рефлексивности, т.к. сам элемент х принадлежит классу, элементом которого является. Обладает отношение I и свойством симметричности, т.к. если x и y принадлежат какому-то классу, то это же можно сказать и про y и x. Наконец, если имеют место отношения xIy и yIz, то это значит, что x,yB и y,zB, где B - какой-то класс. Это означает, что x, zB, т.е. между x и z установлено отношение I. Следовательно, I обладает транзитивностью. Значит, I - отношение эквивалентности. Теорема доказана и в другую сторону. Качественный порядок Дополним отношение строгого упорядочения Pуп свойством транзитивности. Назовем полученное отношение качественным порядком Pкач. Рассмотрим два примера такого отношения. 1) Пусть х, у - вещественные числа. Введем качественный порядок следующим соотношением: хРкачу <=> x > у +1. Очевидно, что в данном случае отношение Ркач асимметрично и транзитивно, но оно не является негатранзитивным. Покажем это. Дополнение к введенному отношению определим как хРкач у   <=>    х  у +1. Положим у = 0; х = 0.9; z = -0.9. Тогда, очевидно, выполняются отношения (х, y) Ркач ; (y, z) Ркач ; (х, z)  Ркач. Т.е. условие негатранзитивности не выполняется. Согласно рассмотренному примеру, а также доказанному ранее свойству транзитивности слабого порядка, можно сделать вывод, что асимметричное негатранзитивное отношение Р является транзитивным, но обратное не всегда верно. 2) Введем на множестве точек n-мерного евклидова пространства следующее отношение Par, называемое отношением Парето: х, уРаr <=>   i : хi  yi и   j : хj > уj. Отношение Парето называется также безусловным критерием предпочтения (БКП). Оно означает, что точка x по всем координатам имеет не меньшие значения, чем точка y и хотя бы по одной координате имеется строгое превосходство. В двумерном случае данное отношение можно изобразить графически. Возможны следующие ситуации: а) x1 < y1 б) x1 > y1 в) x1 < y1 x2 > y2 x2 = y2 x2 < y2 нет отношения Раr; есть отношение Раr, есть отношение Раr,   x лучше y; y лучше x. Отношение Раr является качественным порядком. Также как и для Pуп и Pсл, на основе Pкач можно построить производные от него отношения:   Iкач - отношение качественного безразличия хIкачу  <=> ( xРкач у) и (уРкач х ); Rкач - нестрогий качественный порядок Rкач = Рd кач. Качественный порядок также называют в литературе частичным порядком. Понятия же нестрого качественного и нестрого частичного порядков различны. Помимо введенных выше специальных бинарных отношений дадим краткие определения некоторых других, часто встречающихся отношений. Отношение Rчаст называется нестрогим частичным порядком, если оно рефлексивно, транзитивно и антисимметрично. Нестрогий частичный порядок можно определить по формуле Rчаст = Pкач . Рефлексивное и транзитивное бинарное отношение называется предпорядком. Симметричный предпорядок является отношением эквивалентности, антисимметричный предпорядок - нестрогим частичным порядком. В заключение изложения теории специальных бинарных отношений приведем сводную таблицу их свойств. В предлагаемой таблице использованы следующие обозначения:   - данным свойством отношение обладает по определению;  - это свойство вытекает из определения. рефл антирефл Симм асимм Антисимм транз нега-транз полн ацикл Pуп   Iуп   Rуп   Pсл      Iсл    Rсл     Pкач +    Rкач    Rчаст    ЛЕКЦИЯ № 8 Функция выбора. Основные понятия Задача выбора возникает, когда из некоторого конечного или бесконечного множества надо отобрать подмножество в каком-то смысле хороших элементов. Подмножество отбираемых элементов называется выбором, а правило их отбора - функцией выбора. Более строго функцию выбора можно определить следующим образом. Пусть А - множество элементов из которых осуществляется выбор, ХА - множество допустимых решений (предъявление), а С(Х)Х - множество отобранных точек (выбор). Отображение  : ХC(Х) называется функцией выбора. Алгоритм реализующий эту функцию выбора называется механизмом выбора. Рассмотрим примеры наиболее распространенных механизмов выбора. 1) Скалярный оптимизирующий механизм - выбор вариантов, при которых некоторая скалярная функция f(х) достигает максимума. Сопт(Х) = { хХ | х=arg max f(x) } 2) Условно-оптимальный механизм - выбор по схеме математического программирования, т.е. выбор таких хХ, при которых достигается условный максимум скалярной функции f0(x) при выполнении системы ограничений. Смп(Х) = { хХ | х=arg[ max f0(x)|f i(х)0, i=1,..,m] } 3) Механизм доминирования по бинарному отношению R – выбор тех хХ, которые с любым элементом из Х находится в отношении R (элемент х лучше любого y в смысле отношения предпочтении R). СR(Х)={ хХ |  yХ : (x,y)R }   4)Механизм блокировки по бинарному отношению R - выбор тех элементов xX, для которых в Х нет элемента лучше в смысле отношения предпочтения R. СR(Х) = { хХ |  yХ : (x,y)R } 5) Механизм ограничений по бинарному отношению R отбирает те элементы х, которые с фиксированной точкой u образует пару в R. Сu(Х) = { хХ |  (x, u)R } 6) Паретовский механизм осуществляет выбор таких элементов х, для которых нет элемента y лучшего чем х сразу по всем критериальным функциям f i(х). Сpar(Х) = { хХ | не  yХ : f i(y)f i(x)  i=1,..,m } 7) Турнирный механизм - выбор такого х, при котором достигает максимума турнирная функция f R(x). Ее можно трактовать, как число очков, набранных элементом х во время турнира со всеми элементами из Х. СT(Х) = { хХ | х=arg max f R(x) }; f R(x) =  f R (x,y) y При решении задачи выбора возникают 2 подзадачи. 1) Задача анализа - организация выбора по заданному механиз- му выбора и предъявлению. 2) Задача синтеза - построение механизма выбора по известно- му выбору на предъявлении Х и результату выбора С(х). Классификация функций выбора Обозначим  - множество всех возможных функций выбора. Простейшая классификация различает следующие подмножества  : а)   >0 - подмножество функций непустого выбора, т.е. таких функций, выбор по которым содержит хотя бы один элемент. б)  1 - подмножество функций однозначного выбора, т.е. таких функций, выбор по которым содержит ровно один элемент. Ясно, что 1   >0   .   Приведем без доказательства следующие теоремы о функциях выбора. ТЕОРЕМА 1. Бинарное отношение R порождает функцию непустого выбора, основанную на механизме доминирования или блокировки тогда и только тогда, когда R ациклично. ТЕОРЕМА 2. Бинарное отношение R порождает функцию однозначного выбора, основанную на механизме доминирования или блокировки тогда и только тогда, когда R ациклично и слабополно. Более тонкая классификация функций выбора основывается на наличии или отсутствии у них следующих свойств. 1) H: (YX) => C(X)YC(Y) - свойство наследования. Наличие этого свойства означает, что элемент b, выбираемый на множестве Х, будет также выбран на любом более узком содержащем его подмножестве Y. Иными словами, при переходе к рассмотрению элемента b на более узком множестве, его свойство быть выбранным сохраняется (наследуется). 2) C: X = YZ => (C(Y)C(Z))C(X) - свойство согласия. Наличие этого свойства означает, что элемент b, выбираемый одновременно на любых составных частях некоторого множества Х, будет также выбран на всем Х. 3) О: (C(X)YX) => (C(Y) = C(X)) - свойство отбрасыва- ния или независимости от отбрасывания отвергнутых вариантов. Оно означает, что выбор на любом множестве Y, содержащем выбор C(X) совпадает с C(X). Т.е. выбор не зависит от того, сколько "плохих" элементов пришлось отбросить при выборе. 4) K: (YX) => (C(Y) = Y(X)) - свойство строгого нас-  ледования (константности). Перечислим ряд закономерностей, которые вытекают из названных свойств функций выбора. Пусть (H), (C), (O), (K)   - множества функций выбора, удовлетворяющих соответствующим свойствам. ТЕОРЕМА 3. (K)(H)(C)(O). Т.е. если функция выбора обладает свойством K, то она обладает одновременно свойствами H, C, O. ТЕОРЕМА 4. Для того чтобы функции выбора порождалась бинарным отношением R посредством механизма доминирования или блокировки, необходимо и достаточно, чтобы она принадлежала области (H)(С). ТЕОРЕМА 5. Для того чтобы функция выбора порождалась качественным порядком необходимо и достаточно, чтобы она принадлежала области (H)(С)(O). ТЕОРЕМА 6. Для того чтобы функция выбора порождалась слабым порядком необходимо и достаточно, чтобы она принадлежала области (К). Свойства Н, С, О кажутся очень естественными при выборе. Тем не менее, несложно привести пример, когда эти свойства не выполняются . Пусть Х - множество точек на плоскости ограниченных прямоугольником АBCD: A(0,0), B(0,4), C(2,4), D(2,0) Ставится следующая задача выбора: на множестве Х найти геометрическое место центров кругов, включенных в Х, максимального радиуса. Покажем что соответствующая функция выбора не обладает ни одним из свойств H, K, O, C. 1) Пусть Х = АBCD; Y = АEFD; E(0,2), F(2,2) (Рис. 1). Тогда множеством центров кругов максимального радиуса, вписанных в ABCD, яввляется отрезок PQ (C(X)=PQ), где P(1,3), Q(1,1). Тогда C(X)Y = QR. Очевидно, что C(Y)=Q. Получили, что на множестве X нашлось такое подмножество Y, что хотя YX, тем не менее множество YC(Х) не включено в C(Y), т.е нарушаются условия H и K. 2) Пусть Y = MNOT: M(0,1), N(0,3), O(2,3), T(2,1) (Рис. 2). Так как, по прежнему, C(X) = PQ, а C(Y)=R(3,3), то C(X)YX.Равенство C(X)=C(Y) при этом не выполняется, т.е нарушается условие O. Задача векторной оптимизации В классических задачах оптимизации необходимо найти минимум или максимум скалярной функции - функции цели или критерия эффективности. Но в практических задачах редко удается свести эффективность к одному показателю. Пример. Пусть необходимо сконструировать самолет. Основными, одинаково важными, критериями эффективности конструкции являются скорость и дальность полета. Увеличивая дальность полета самолета, мы уменьшаем его скорость и наоборот. Такая ситуация называется конфликтом критериев. В том случае, когда имеется несколько конфликтующих критериев, говорят, что имеет место задача векторной оптимизации. F(x) = { f 1(x), f 2(x),..., f n(x) }  орt, где f i- частные критерии эффективности. Как правило, не существует такой точки в которой все f i оптимальны. Поэтому в задаче векторной оптимизации ищут компромиссное решение. Для эффективного поиска такого решения необходимо, чтобы число возможных допустимых вариантов было как можно меньше. Для достижения такой цели задачу разбивают на 2 этапа. 1) Поиск нехудших (недоминируемых) решений в смысле безусловного критерия предпочтения (БКП). Множество таких точек называется множеством Парето. 2) Выбор компромиссного решения на множестве Парето. Рассмотрим пример [6]. Пусть имеем два критерия эффективности q1(x) и q2(x), зависящих от одного аргумента х, каждый из которых необходимо минимизировать ( Рис.3 ). Обозначим Х1 и Х2 - точки минимума критериев q1(x) и q2(x), соответственно. Разобьем область определения аргумента х на три участка: I, II, III. Осуществим на каждом участке выбор точек, лучших по Парето, т.е. по обоим критериям одновременно: а) Cpar(I) = Х1 - выбор на I участке есть точка X1; б) Cpar(III) = X2 - выбор на III участке есть точка X2; в) на участке II нет точки, которая была бы лучше остальных сразу по обоим критериям, т.е. он весь состоит из конфликтующих точек, следовательно, Cpar(II)=[X1, X2]. Рис. 3 Чтобы найти множество Парето в общем случае надо реализовать функцию выбора на основе паретовского механизма (механизма блокировки в смысле бинарного отношения Парето) (см. п.6). Для того чтобы построить эту функцию достаточно организовать сравнение предлагаемых вариантов по каждой критериальной функции. Для этой задачи можно достаточно легко построить алгоритм решения, т.е она формализуема. Для задачи второго этапа необходимо применять неформальные методы выбора, основанные на интуитивных предпочтениях эксперта или лица принимающего решения (ЛПР). Для организации паретовского механизма выбора необходимо произвести парные сравнения исходных вариантов и отбросить те, для которых найдется доминирующий элемент. Если исходное множество велико, то метод попарного сравнения трудоемок, т.к в общем случае необходимо произвести m(m-1)/2 сравнений, где m – число сравниваемых вариантов. Более эффективен следующий алгоритм, который производит последовательное накопление элементов искомого множества. Обозначим X = {xi} - исходное множество сравниваемых вариантов. Для него будем производить отсев плохих точек и получение множества П(Х), содержащее точки Парето. begin П(Х):={х1}; for i:=2 to m do П(Х):=Cpar ({xi}  П(Х) ); end. При реализации этого алгоритма возможны три случая: 1) Для хi существует такой у  П(Х), что у Par xi. В этом случае необходимо прекратить сравнение хi с паретовскими точками и перейти к хi+1. 2) Для хi существует такой у  П(Х), что xi Par у. В этом случае необходимо исключить y из П(Х) и продолжить сравнение хi с оставшимися точками пока не будет просмотрено все текущее множество П(Х). Если процесс сравнения не прекратился раньше, чем было просмотрено все П(X), то хi необходимо включить в П(Х). 3) Для хi не существует такого у  П(Х), чтобы у Par xi или xi Par у. В этом случае y не исключают и продолжают сравнение хi с оставшимися точками также, как и в случае 2). Обычно множество недоминируемых точек содержит значительно меньше элементов, чем исходное т.е k = |П(Х)|<<|Х| = m. В этом случае нужно провести O(mk) сравнений, т.е. значительно меньше, чем при всевозможных парных сравнениях. Данный алгоритм даст верное решение, если для любых множеств X и Y выполняется условие: CR(X  Y) = CR( X  CR(Y)) (1) ТЕОРЕМА. Соотношение (1) выполняется, если функция выбора обладает свойствами Н и О. ДОКАЗАТЕЛЬСТВО. Вспомним свойства - наследования: (Y  X) => C(X)  Y  C(Y); - отбрасывания: (C(X)  Y  X) => (C(Y) = C(X)). Покажем, что при их выполнении CR(XY)  XCR(Y). Пусть х  CR(XY). Если х  X, то х  XCR(XY). Пусть теперь х  Y, тогда х  CR(XY)Y. В силу свойства наследования получим, что Y  XY, поэтому CR(XY)Y C R(Y). Значит, x  CR(Y), а, следовательно, x  XCR(Y), что доказывает утверждение. Обозначим A = XY, B = XCR(Y). По доказанному ранее CR(XY)  XCR(Y)  XY. Тогда по свойству отбрасывания CR(A) = CR(B) или СR(XY) = СR(XСR(Y)), что и требовалось доказать. Условие (1) в частности выполняется, если R – качественный порядок (см. п.11, ТЕОРЕМА 5). T.к отношение Парето таковым является, то алгоритм позволяет построить искомое конфликтное множество. ЛЕКЦИЯ № 9 КОМБИНАТОРНЫЕ КОНФИГУРАЦИИ И ИХ ПРИЛОЖЕНИЯ Комбинаторика – это область математики, в которой изучаются различные комбинации элементов дискретных (в основном – конечных) множеств, подчиненных тем или иным условиям. Как наука комбинаторика возникла в 16 веке, и первоначально основной областью ее приложения являлись азартные игры. Однако, за последние несколько десятков лет комбинаторные методы трансформировались из разделов “досуговой” математики в инструмент решения огромного числа практически важных задач, таких как составление расписаний, планирование производства, размещение объектов на данной территории и многое другое. Не последнюю роль комбинаторика играет и при решении задач разработки технического и программного обеспечения современных информационных систем – проектирование интегральных схем, кодирование информации, организация структур данных – вот далеко не полный перечень проблем “компьютерной” математики, решаемых средствами комбинаторики. 1. Основные задачи, обозначения и правила Среди многочисленных проблем, решаемых средствами комбинаторики, основное внимание уделим следующим задачам. 1. Выбор из некоторого, обычно конечного, множества некоторого подмножества (комбинации) элементов, обладающих заданными свойствами. 2. Подсчет числа таких комбинаций. 3. Определение элемента комбинации, обладающего оптимальными свойствами. Введем следующие понятия и обозначения. n-множество – множество из n различных элементов: Х = {х1, х2, …, хn}, хi  хj, при i  j. (n)-множество – множество, содержащее n различных типов элементов: Х = {х1, х1, …, х1, х2, х2, …, хn}. r-выборка множества – совокупность из r элементов данного множества (если выборка из n-множества, то повторяющихся элементов нет, если из (n)-множества, то есть повторения). Размещения – упорядоченные r-выборки (элементы прямого произведения Х1  Х2 …  Х r). Сочетания – неупорядоченные r-выборки (r-элементные подможества данного множества). Пример 1.1. а) На диске секретного замка 12 букв. Замок открывается после набора пароля из 5 букв. В пароле буквы могут повторяться. Следовательно, каждый пароль – это 5-размещение из (12)-множества, т.е. размещение с повторениями. б) Из 25 человек, членов комитета, надо выбрать: председателя, вице-председателя, секретаря и казначея (4 человека). Совмещение должностей не допускается. В задаче повторение элементов невозможно, т.к. не допускается совмещение должностей. Кроме того, в данной 4-выборке важен порядок выбора, т.к. надо не просто выбрать заданное число человек, но необходимо связать каждого выбранного с определенной должностью. Следовательно, здесь речь идет о размещении без повторений. в) Из 125 человек надо выбрать 6 делегатов на конференцию. В данном случае порядок выбора не играет роли, следовательно, имеет место 6-сочетание из 125-множества. Многие простые задачи комбинаторики решаются с помощью двух основных аксиоматических правил. 1. Правило суммы. Если все комбинации можно разбить на несколько непересекающихся классов, то общее число комбинаций равно сумме чисел комбинаций во всех классах: . 2. Правило произведения. Пусть объект А можно выбрать n способами, а при каждом таком выборе объект В можно выбрать m способами. Тогда выбор упорядоченной пары (А, В) можно сделать nm способами. В общем случае: . На практике оба правила часто используются в комбинации. Пример 1.2. Сколькими способами можно из 28 костей домино выбрать 2 кости, которые можно приложить друг к другу? Решение. 1-ю кость можно выбрать 28-ю способами. Из них в 7 случаях кость будет дублем, а в 21 случаях – с различными числами. Если 1-я кость является дублем, 2-ю кость можно выбрать 6-ю способами, а если – нет, то 12-ю способами. В соответствии с правилами суммы и произведения общее число случаев равно N = 76 + 2112 = 294. 2. Простейшие конфигурации 2.1. Размещения с повторениями. Так называются упорядоченные r-выборки из (n)-множества. Дадим более подробное определение. Пусть дано неограниченное число предметов, относящихся к n различным видам. r-размещениями с повторениями называются различные расстановки из этих предметов по r штук в каждой, образованные по следующим правилам. 1. 2 расстановки считаются различными, если они отличаются либо видом входящих в них предметов, либо порядком следования этих видов. 2. В каждую расстановку может входить несколько предметов одного вида. Свойство. Число r-размещений с повторениями из предметов n типов обозначается и равно nr. Доказательство. На 1-м месте может быть предмет одного из n видов. Следовательно, существует n способов выбрать 1-й предмет. При каждом фиксированном таком способе имеется n способов выбрать 2-й предмет, и т.д. В соответствии с правилом произведения всю группу из r предметов можно выбрать nr способами, что и требовалось доказать. В примере 1.1.а) существует 125  250 тыс. различных паролей. (Если взломщик будет тратить по 1 секунде на проверку комбинации, то ему понадобиться 69 часов для проверки всех паролей). Пример 1.3. В азбуке Морзе самый длинный код буквы состоит из 5 символов. Можно ли использовать коды длиной не более 4-х символов? Решение. В соответствии с правилом суммы число различных кодов длиной не более 4 символов при использовании 2 видов символов (точка и тире) равно = 2 + 4 + 8 + 16 = 30. Значит, 4-х символьных кодов не хватит для кодирования даже всех букв кириллицы, не говоря о служебных символах. При использовании же 5-ти символьных кодов N = 30 + = 62, т.е. такой длины кода достаточно. 2.2. Размещения и перестановки без повторений. Размещениями без повторений называются упорядоченные r-выборки из n-множества. Такие расстановки по r элементов составляются из n неповторяющихся предметов. Свойство. Число r-размещений без повторений из n предметов обозначается и равно n(n – 1)…(n – r + 1) = . Доказательство. 1-й предмет можно выбрать n способами, 2-й – (n – 1) способами, т.к. число кандидатов на это место уже n – 1, и т.д. В соответствии с правилом произведения получаем выражение из r сомножителей: . В примере 1.1.б) число способов выбора 4-х членов в руководство комитета из 25 человек равно = 25242322 = 303600. В частном случае при r = n получаем = Рn = n! Данная конфигурация называется перестановкой из n неповторяющихся предметов – упорядоченная n-выборка из n-множества. 2.3. Перестановки с повторениями. Так называют упорядоченные n-выборки из (m)-множества (n > m). Если некоторые элементы такой выборки совпадают, то могут существовать неразличимые (совпадающие) перестановки. Найдем количество различных перестановок. Обозначим a, b,…, z – переставляемые объекты; nj – количество повторений j-го элемента, j = 1,…,m, ; Р(n1, n2,…, nm) – число таких перестановок. Рассмотрим 1-ю перестановку: . Объекты “а” можно переставлять n1! способами, но поскольку все они одинаковы, то такие перестановки не дают новых комбинаций. Следовательно, число действительно различных перестановок за счет совпадения первых n1 элементов будет в n1! раз меньше, чем в случае всех различающихся элементов. Аналогично, совпадение n2 элементов “b” уменьшает число различных перестановок в n2! раз, и т.д. Поскольку при несовпадении всех n элементов количество перестановок было бы равно n!, то Р(n1, n2,…, nm) = . Пример 1.4. Найти все перестановки букв в слове “мама”. Решение. В данном слове есть объекты 2-х типов – “м” и “а”. Всего множество содержит 4 элемента. Следовательно, число перестановок равно . Действительно, имеем следующие комбинации: ”аамм”, “мама”, “амам”, “ммаа”, “амма”, “маам”. Пример 1.5. Найти число перестановок букв в слове “Миссисипи”. Решение. Длина этого слова – 9 букв. Из них буква “м” встречается 1 раз, “и” – 4 раза, “с” – 3, “п” – 1. Следовательно, число перестановок равно Р(1, 4, 3, 1) = = 2520. 2.4. Сочетания без повторений. Так называются неупорядоченные r-выборки из n-множества (r < n). Свойство. Число r-сочетаний без повторений из n предметов обозначается и равно . Доказательство. Каждое неупорядоченное r-сочетание можно упорядочить r! способами и получить r-размещение. Следовательно, сочетаний в r! раз меньше, чем размещений, т.е. = Р(r, n – r). В примере 1.1.в) 6 делегатов из 125 человек можно выбрать = 4.69110 9 способами Пример 1.6. В лотерее из 36 номеров будут выбраны 5. Какова вероятность угадать ровно 3 номера из 5? Решение. 3 номера из 5 верных можно выбрать способами. На каждый угаданный номер могут приходиться любые 2 из 31 невыбранных номеров, т.е. сочетаний. Окончательное число благоприятных случаев равно . Общее же число случаев равно количеству выпадения 5 номеров из 36, т.е. . Отсюда вероятность угадывания равна  0.0123 – немногим более 1%. 2.5. Сочетания с повторениями. Это неупорядоченные r-выборки из (n)-множества. Они получаются, например, если необходимо r неразличимых предметов разместить по n ящикам, в частности возможно n > r. Свойство. Число r-сочетаний с повторениями из n предметов обозначается и равно . Доказательство. Обозначим rj  0 – количество элементов j-го типа в сочетании, (rj можно интерпретировать как количество предметов в j-м ящике). Набор значений rj однозначно определяет текущее сочетание. Представим этот набор в виде следующей бинарной последовательности. Числа rj отобразим в группы из rj единиц, каждую такую группу отделим от соседних одним нулем (если rj = 0, то несколько нулей могут стоять подряд). Число промежутков равно n – 1. Например, набор (2, 0, 3, 1), n = 4, r = 6 соответствует последовательности (1, 1, 0, 0, 1, 1, 1, 0, 1). Построенная конструкция – не что иное, как набор перестановок с повторениями объектов 2-х видов – 0 и 1. Число нулей в этих сочетаниях равно n – 1, а единиц – r. Следовательно, , что и требовалось доказать. Пример 1.7. Определить количество N возможных сочетаний из 8 пирожных 4-х сортов. Решение. В данном случае rj– число пирожных j-го сорта. Следовательно, r = 8, n = 4 и N = = = 165. Другой вариант доказательства основан на построении взаимно-однозначного отображения напрямую между элементами повторных и бесповторных сочетаний. Свяжем каждый набор r1, r2, …, rn с элементами n – 1-сочетаний без повторений из множества чисел {1, 2,…, n + r – 1}. Обозначим Кj, j = 1,…, n –1– число, стоящее на j-м месте в отбираемом сочетании (Кj > Кj–1), формально положим К0 = 0. Построим взаимно-однозначное отображение f : (r1, r2, …, rn)  (K1, K2, …, Kn–1) по следующему правилу: rj = Кj – Кj – 1 – 1, j = 1,…, n – 1; (1.1) rn = (n + r – 1) – Кn –1. Очевидно, обратное отображение строиться по формуле Кj = , j = 1,…, n –1. (1.2) Покажем, что числа, найденные по формулам (1.1) являются элементами r-сочетаний с повторениями. Действительно, т.к. при любом j и , то . Кроме того . Несложно также убедиться, что числа Кj, полученные по формуле (1.2) являются натуральными, и обладают всеми свойствами элементов сочетаний: ; Следовательно, отображение f действительно устанавливает взаимно однозначное соответствие между элементами r-сочетания из (n)-множества и элементами n – 1-сочетания из n + r – 1-множества. Отсюда = = . Последнее равенство вытекает из формулы числа сочетаний. 2.6. Свойства чисел сочетаний 1. =. Это свойство вытекает из формулы числа сочетаний. 2. = + . Доказательство. Разобьем все r-сочетания на два класса. К первому классу отнесем сочетания, содержащие объект an, ко второму классу – не содержащие an. Так как в первом классе меняются только r – 1 элементов из n – 1 возможных, то он содержит r – 1-сочетания из n – 1-множества, следовательно, в нем элементов. Второй класс содержит все r-сочетания из n – 1-множества, т.к. в них нет одного элемента – an. Следовательно, в нем элементов. Общее число сочетаний, согласно правилу суммы равно + , что и требовалось доказать. Данное свойство позволяет легко построить рекуррентный процесс вычисления всех чисел сочетаний. Положим по определению для любого n  0 (ноль элементов из любого множества, в том числе – пустого, можно выбрать 1 способом, кроме того, по определению 0! = 1 – см. формулу из 2.4) и (отрицательное количество элементов выбрать невозможно). Организуем двойной цикл для вычисления всех , r  m  n: for m := 1 to n do for r := 0 to m do := + Описанный процесс удобно представить в виде таблицы, называемой треугольником Паскаля: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 ……………………. В таблице каждая m-я строка состоит из чисел , r = 0, … m, каждый элемент равен сумме двух элементов, расположенных над ним (пустое место считается нулем). 3. Доказательство. Пусть имеем последовательность из n двоичных разрядов, содержащих 0 или 1. Очевидно, что каждую такую последовательность можно рассматривать, как n-размещение с повторениями из элементов 2-х типов, значит, количество этих размещений равно 2n. Теперь рассмотрим некоторое множество из n объектов – а1, … аn, из которого будем образовывать все возможные сочетания без повторений, включая: 0-сочетания (не выбирается ни один объект), 1-сочетания и т.д., n-сочетания. При этом любую из упомянутых выше последовательностей из 0 и 1 можно интерпретировать, как перечень элементов, отбираемых в сочетание – если на k-м месте последовательности стоит 1 – элемент аk отобран, если 0 – не отобран. Очевидно, что таким образом будут перечислены все бинарные n-последова-тельности. По правилу суммы общее число таких сочетаний, а, значит – и бинарных последовательностей равно Свойство доказано. Замечание. Каждая отбираемая в сочетание группа элементов представляет собой некоторое подмножество исходного множества из n объектов. Следовательно, число всех подмножеств (включая пустое) множества из n элементов равно 2n. 3. Комбинаторные конфигурации в алгебре и анализе Многие важные формулы алгебры и математического анализа (и других разделов математики) имеют наглядную комбинаторную интерпретацию или доказываются с использованием правил комбинаторики. 3.1. Бином Ньютона. – формула бинома Ньютона. В частности, (х + у)2 = х2 + 2ху + у2; (х + у)3 = х3 + 3х2у + 3ху2 + у3 и т.д. Доказательство. Раскроем скобки выражения (х + у) n = (x + y)(x + y)…(x + y). В результате получим сумму членов вида . Например (х + у) 3 = ххх + хху + хух + хуу + ухх + уху + уух + ууу. Приведем подобные члены, подсчитав число таких произведений при каждом k = 0,…, n. Каждое такое выражение – не что иное, как перестановка повторениями из 2-х элементов. Полагая n1 = k, n2 = n – k, получим, что число этих перестановок равно Р(k, n – k) = (см. пп. 2.3, 2.4), т.е. множитель при хkуn – k совпадает с , что и требовалось доказать. С помощью формулы бинома легко получить новые свойства чисел сочетаний. 5. . Доказать легко с использованием бинома Ньютона на основе тождества (1 – 1)n = 0. 6. . Доказательство. Имеем: n2n–1 = n(1 + 1)n –1 = . В свою очередь при любом р выполняется равенство: = = . Следовательно, . Переобозначим индекс суммирования, положив p + 1 = k. Имеем: , что и требовалось доказать. В последнем равенстве формально введено равное нулю слагаемое при k = 0. 3.2. Полиномиальная формула. Формулу бинома можно обобщить на случай нескольких слагаемых: (х1 + х2 + … + хk)n. Запишем эту формулу в виде произведения одинаковых сомножителей и перемножим. Получим все возможные n-размещения с повторениями из объектов х1, х2 , … , хk. Приведем подобные, сосчитав число повторений каждого слагаемого вида . Для этого надо определить число слагаемых, в которых символ х1 повторяется n1 раз, х2 – n2 раз, и т.д., хk повторяется nk раз. Каждое такое слагаемое – это перестановка с повторением nj раз элемента хj, j = 1,…k. Число таких перестановок равно Р(n1, n2 ,…, nk),  nj = n. Следовательно (х1 + х2 + … + хk)n = . Выражение n1 + … + nk = n в значке суммы означает, что перебираются все (целые неотрицательные) значения n1,…, nk, удовлетворяющие данному условию. Например: (x + y + z)4 = P(4, 0, 0)x4 + P(0, 4, 0)y4 + P(0, 0, 4)z4 + P(3, 1, 0)x3y + P(3, 0, 1)x3z + P(2, 2, 0)x2 y2 + P(2, 1, 1)x2 y z + P(2, 0, 2)x2 z2 + P(1, 3, 0)x y3 + P(1, 0, 3)x z3 + P(1, 1, 2)x y z2 + P(1, 2, 1)x y2 z + P(0, 3, 1)y3 z + P(0, 1, 3)y z3 + P(0, 2, 2)y2 z2. Напоминаем, что здесь Р(a, b, c) = , например Р(2, 1, 1) = = 12. 3.3. Ряд Ньютона. Формулу бинома можно обобщить на случай нецелой степени, в результате получим выражение: (у + х) = у +  у–1х + + … + + +… При целом значении  формула содержит конечное число слагаемых, т.к. для k >  коэффициенты при у–kхk обращаются в ноль. При нецелом  получается бесконечный степенной ряд. ЛЕКЦИЯ № 10 Комбинаторные алгоритмы При поиске оптимального варианта из некоторого допустимого набора часто приходится перебирать все возможные альтернативы. Во многих задачах перебираемые варианты являются членами сочетаний, размещений и других комбинаторных конфигураций. Поэтому большое значение имеют алгоритмы генерации элементов соответствующих конечных множеств. Главная сложность составления таких ”генераторов” состоит в необходимости сделать их структуру независимой от размерности порождаемых ими множеств, которая может очень сильно варьироваться в различных задачах. Например, алгоритм генерации r-размещений с повторениями очень легко реализовать с помощью r вложенных циклов: for j1 := 1 to n do for j2 := 1 to n do ………………….. for jR := 1 to n do writeln (j1, j2, … jR); Ясно, что всякий раз при изменении значения r такую программу пришлось бы переделывать, добавляя или удаляя циклы, и на самом деле алгоритм генерации должен быть другим. Другой особенностью предлагаемых алгоритмов является то, что в них вместо комбинаций самих объектов генерируются комбинации из их номеров. Очевидно, что такие расстановки легко преобразовать в манипуляции, например, с названиями объектов, введя в программу массив из строк символов соответствующей размерности. Многие из комбинаторных конфигураций удобно генерировать с помощью алгоритма поиска с возвратом. Общая схема рекурсивного поиска с возвратом. Пусть дано n упорядоченных множеств В1, В2,… Вn. Требуется найти набор векторов вида Х = (х1, х2,… хn), где xiВi, удовлетворяющих некоторым дополнительным условиям. Иными словами Х  В1В2 … Вn. В алгоритме поиска с возвратом каждый вектор Х строится покомпонентно слева направо. Предположим, что уже найдены первые k – 1 компонент х1, х2,… хk–1. Тогда их значения определяют некий набор условий, ограничивающих выбор k-й компоненты некоторым множеством Sk  Вk. Если Sk не пусто, мы вправе выбрать в качестве хk первый по порядку элемент из Sk, присоединить его к уже выбранным компонентам, и перейти к выбору хk+1 и так далее. Однако, если набор условий таков, что Sk пусто, то мы возвращаемся к выбору k–1-й компоненты. При этом мы отбрасываем хk–1 и выбираем в качестве новой k–1-й составляющей вектора Х тот элемент из Sk–1, который непосредственно следует за только что отброшенным хk–1. Предположим теперь, что в процессе поиска новых компонент мы дошли до конца, т.е. выбрали хn. Теперь надо как-то использовать полученный вектор Х, в соответствие с условием задачи. Например, если в задаче требуется найти лучший из векторов, то нам следует сравнить построенный вектор Х с решением, которое до данного момента считалось оптимальным и если Х окажется лучше, то надо обновить текущее оптимальное решение, вернуться на шаг назад и продолжить поиски новых решений. Этот процесс продолжается, пока не будут рассмотрены все возможные вектора решений. Данная схема легко реализуется посредством рекурсивной процедуры. procedure Solve ( k ); { k – номер подбираемой координаты (номер глубины рекурсии) } { Х – вектор текущего решения } begin if  Х – решение  then  Использовать Х  else begin  Определить Sk  ; for у  Sk do begin Xk:= y; Solve(k+1 ) end; end; end; Конкретный набор требований, которым должны удовлетворять сгенерированные векторы, определяются множествами Sk, а также правилом проверки того, что Х – решение. 1. Алгоритм генерации r-размещений с повторениями. В размещениях с повторениями на k-месте должно стоять число из набора 1,…, n независимо от чисел, стоящих на предыдущих позициях. То есть для любого k всегда будет Sk= {1, …, n }. Пример 2.1. Пусть r = 3; n =2. Надо получить следующие векторы Х: (1 1 1), (1 1 2), (1 2 1), (1 2 2), (2 1 1), … (2 2 2). Обозначим А[j] – номер предмета, находящегося на j-м месте, j = 1,…r. Предлагается следующий алгоритм. Procedure Razm_P(k); begin if k=r+1 then write(A[1],…A[r]); else for y:=1 to n do begin A[k]:=y; Razm_P(k+1); end; end; begin Razm_P(1); end. Назначение процедуры Razm_P(k)– получение k-й компоненты вектора Х =(A[1],…A[r]). Если k = r+1 – это означает, что вектор полностью получен, и надо его использовать (вывести на экран). В противном случае надо получить следующую компоненту. Так как на ее месте может стоять любое число от 1 до n, то Sk = {1, … n}, перебор элементов этого множества обеспечивается циклом for y:=1 to n do 2. Алгоритм генерации r-размещений без повторений. Отличие данного алгоритма от предыдущего в том, что каждое из возможных значений 1, … n элементов размещений можно использовать только один раз. Поэтому в процедуре Razm_BP используется массив dop[j], j = 1,…n, в котором dop[j] = 1, если значение j не было использовано и dop[j] = 0, в противном случае. При продвижении вглубь рекурсии значение j блокируется, чтобы его нельзя было использовать повторно, а при откате – восстанавливается. Procedure Razm_BP(k); begin if k=r+1 then write(A[1],…A[r]); else for y:=1 to n do if dop[y] > 0 then begin A[k]:=y; dop[y]:=dop[y]-1; Razm_BP(k+1); dop[y]:=dop[y]+1; end; end; begin for i:=1 to n do dop[i]:= 1; Razm_BP(1); end. Данный алгоритм можно также использовать для генерации перестановок без повторений при r = n. 3. Алгоритм генерации перестановок с повторениями. Этот алгоритм похож на предыдущий, только первоначально dop[j]=n[j]– число повторений j-го значения, j = 1,…m. По мере использования этого значения переменная dop[j] уменьшается, пока не станет равной 0. Это будет означать, что данное значение уже нельзя использовать. Предлагается следующий алгоритм генерации перестановок из m объектов при . Procedure Perest_P(k); begin if k=n0+1 then write(P[1],…P[n0]); else for y:=1 to m do if dop[y] > 0 then begin P[k]:=y; dop[y]:=dop[y]-1; Lex(k+1); dop[y]:=dop[y]+1; end; begin n0=0; for j:=1 to m do begin dop[j]:=n[j]; n0:=n0+n[j]; end; Lex(1); end. 4. Алгоритм генерации r-сочетаний без повторений. Алгоритм похож на генерацию размещений без повторений, отличие в том, что в каждом сочетании не допускаются перестановки элементов, т.е. каждый следующий элемент больше предыдущего. Пример 2.2. Подобные 3-сочетания из 5 выглядят так: (1 2 3), (1 2 4), (1 2 5), (1 3 4), … (1 4 5), (2 3 4), … – т.е. генерируется возрастающая последовательность 3-значных чисел. Для обеспечения этого условия в генерации сочетаний используется цикл for y:=t to n do, а не for y:=1 to n do, как в размещениях, где переменная t подбирается по правилу if k<=1 then t:=1 else t:=А[k-1]+1. Procedure Sochet_BP(k); begin if k=r+1 then write(А[1],…А[r]); else begin if k<=1 then t:=1 else t:=А[k-1]+1; for y:=t to n do if dop[y] > 0 then begin А[k]:=y; dop[y]:=dop[y]-1; Sochet_BP(k+1); dop[y]:=dop[y]+1; end; end; end; begin for i:=1 to n do dop[i]:= 1; Sochet_BP(1); end. АНАЛИТИЧЕСКИЙ АППАРАТ КОМБИНАТОРИКИ Формулы и алгоритмы, рассмотренные в теме 1, дают способы вычисления комбинаторных чисел для некоторых распространенных конфигураций. Однако, практические задачи далеко не всегда непосредственно сводятся к ним. В этом случае чрезвычайно важно знание методов сведения одних конфигураций к другим, либо общих методов, не столь зависящих от конкретных комбинаторных структур. Рассмотрим наиболее популярные из таких методов. 1. Принцип включения и исключения 1.1. Вывод формулы. Пусть имеем N объектов и некоторый набор свойств а1, …, аn, которыми могут обладать эти объекты. Обозначим N(i) – число объектов, обладающих свойством аi, и вообще N(i1, …, ik) – число объектов, обладающих одновременно всеми свойствами . Пусть N(0) – число объектов, не обладающих ни одним из свойств аi. Справедлива формула включения и исключения: N(0) = N – + + … + (– 1)k + … + (–1)n N(1, 2, … , n). (3.1) Символ 1  i1 < i2 <…< ik  n под знаком суммы означает, что суммирование ведется по всем комбинациям i1, i2,…, ik так, чтобы выполнялось указанное соотношений. Доказательство проведем с помощью индукции по n – число свойств. 10. n = 1. N(0) = N – N(1). Всего существует одно свойство. От общего числа объектов отнимем количество объектов, обладающих этим свойством – узнаем, сколько объектов этим свойством не обладают. 20. Пусть для n – 1 свойств справедлива формула N(0) = N – + + … + (– 1)k + … + (–1)n N(1, 2, … , n – 1). (3.2) Пусть теперь имеем множество, все элементы которого обладают свойством аn, и, возможно, обладают свойствами а1, …, аn–1. Очевидно, для этого множества формула (3.2) также верна и имеет вид: N(0, n) = N(n) – + … + +(–1)n–2+ (–1)n–1N(1, 2, … , n – 1, n). (3.3) В (3.3) везде в скобках дописано n, т.к. все элементы множества свойством аn обладают. Вычтем (3.3) из (3.2): N(0) – N(0, n) = N – + + … – (–1)n–1 N(1, 2, … , n – 1, n). Отсюда N(0) – N(0, n) = N – ++… + (–1)n N(1, 2,…,n). Справа мы получили требуемую формулу. А что слева? N(0) – число элементов, не обладающих свойствами а1, …, аn–1, но, возможно, обладающих свойством аn. N(0, n) – число элементов, не обладающих свойствами а1, …, аn–1, но обязательно обладающих свойством аn. Следовательно, N(0) – N(0, n) – число элементов, не обладающих ни одним из свойств а1, …, аn, т.е. требуемая величина. Формула доказана. Пример 3.1. Староста класса подал следующие сведения о классе. Всего в классе 45 учеников, из них 25 мальчиков. 30 человек учится без троек, из них – 16 мальчиков; 28 человек занимаются спортом, из них – 18 мальчиков и 17 хорошистов и отличников; 15 мальчиков учатся без троек и одновременно занимаются спортом. Классный руководитель внимательно посмотрел список и сказал, что в сведениях есть ошибка. Как он это узнал? Решение. Обозначим a1 – свойство принадлежности к мужскому полу; a2 – хорошая успеваемость; a3 – занятие спортом. Тогда N = 45, N(1) = 25, N(2) = 30, N(3) = 28, N(1, 2) = 16, N(1, 3) = 18, N(2, 3) = 17, N(1, 2, 3) = 15. Итого N(0) = 45 – 25 – 28 + 16 + 18 + 17 – 15 = – 2 – ошибка. 1.2. Модификации формулы включения и исключения 2.а. Формулу (2.1) можно обобщить для определения числа элементов, обладающих в точности k свойствами (0  k  n): N(k) = + …+ (– 1)s–k+ … + (–1)n–k N(1, 2, … , n). (3.4) Пример 3.2. В отделе НИИ каждый сотрудник владеет хотя бы одним иностранным языком. Известно, что английским языком владеют 6 человек, немецким – 6, французским – 7, английским и немецким – 4, немецким и французским – 3, английским и французским – 2, все три языка знает 1 человек. Определить, сколько всего человек в отделе, сколько человек владеют только английским, только немецким, только французским, и сколько человек знает только 1 иностранный язык. Решение. Согласно условиям задачи N(0) = 0, т.к. в отделе нет сотрудников, не владеющих иностранными языками. Следовательно, по формуле (3.1) получаем: N = – + N(1, 2, 3) (3.5) N = 6 + 6 + 7 – 4 – 3 – 2 + 1 = 11 человек всего в отделе. Для вычисления остальных показателей также воспользуемся формулой (3.5). Найдем, например N(только А) – число человек, не владеющих никаким другим языком, кроме английского. Для этого формулу (3.5) надо применить только к множеству людей, владеющих английским языком. В этом случае n = 2. Тогда N = N(A), N(1) и N(2) – число людей, владеющих помимо английского еще немецким и французским, соответственно, N(1, 2) – число людей, владеющих помимо английского еще одновременно немецким и французским. Отсюда N(только A) = N(A) – N(А и Н) – N(А и Ф) + N(А и Н и Ф) = 6 – 4 – 2 + 1 = 1. Аналогично N(только Н) = N(Н) – N(А и Н) – N(Н и Ф) + N(А и Н и Ф) = 6 – 4 – 3 + 1 = 0. N(только Ф) = N(Ф) – N(Ф и А) – N(Ф и Н) + N(А и Н и Ф) = 7 –2 – 3 + 1 = 3. Вычислим теперь N(1) – число людей, владеющих только 1 языком. Воспользуемся формулой (3.4) при k = 1. N(1) = N(А) + N(Н) + N(Ф) + (–1)2–1 [N(А и Н) + N(Н и Ф) + N(А и Ф)] + (–1)3–1 N(А и Н и Ф) = 6 + 6 + 7 – 2(4 + 3 + 2) + 31 = 4. Такой же результат получим, если сложим N(только A) + N(только Н) + N(только Ф). 2.б. Формулу (3.1) можно также интерпретировать, как подсчет мощностей пересечений различных множеств, т.е. дать теоретико-множественное представление принципа включения и исключения. Пусть имеем некоторое конечное множество А и его подмножества Аj, j = 1,…, n. Тогда теоретико-множественный аналог формулы (3.1) будет иметь вид: = |A| – + + … + (– 1)k+ …+ (–1)n . ЛЕКЦИЯ № 11 Рекуррентные соотношения В комбинаторных задачах искомым решением часто является числовая последовательность u1, u2, …, un, … Например, если мы ищем число подмножеств m-элементного множества, то . В данном разделе рассмотрим ситуацию, при которой свойства членов искомой последовательности определяются некоторым рекуррентным соотношением, которому удовлетворяют числа un: un + k + b1 un + k – 1 + b2 un + k – 2 +…+ bk un = 0, (3.6) где b1, b2, …, bk – некоторые коэффициенты. Выражение (3.6) называется еще разностным линейным уравнением k-го порядка с постоянными коэффициентами. Одной из наиболее известных последовательностей, задаваемых линейным рекуррентным соотношением, является последовательность Фибоначчи {Fn}, определяемая следующими условиями: F0 = 0; F1 = 1; Fn+2 = Fn+1 + Fn. Отсюда получаем F2 = 1; F3 = 2; F4 = 3; F5 = 5; F6 = 8 и т.д. Воспользовавшись уравнением (2.8) всегда можно вычислить значения un для любых n, если знать первые k членов последовательности. Однако, часто необходимо знать явную формулу для вычисления un. Теорема 3.4. Пусть 1, 2,…, s – корни соответствующих кратностей m1, m2,…, ms характеристического уравнения для выражения (3.6): k + b1 k–1 + b2 k–2 +…+ bk = 0 (3.7) Тогда общее решение уравнения (3.6) определяется по формуле: un = ( C11 + C12 n + C13n2 + … + )+ ( C21 + C22 n + C23n2 + … + )+ … (3.8) ( Cs,1 + Cs,2 n + Cs,3n2 + … + ), где C11,…, – константы (их число равно k), определяемые начальными условиями. Пример 3.3. Решим уравнение Фибоначчи Fn+2 – Fn+1 – Fn = 0. Его характеристическое уравнение имеет вид: 2 –  – 1 = 0. Корни равны – некратные. Обозначим Ф1 = 1  1.618; Ф2 = 2  – 0.618. Общее решение равно: . Из начальных условий F0 = 0; F1 = 1 получаем систему уравнений для вычисления С1 и С2 = 1: . Отсюда С1 = – С2 = . Использование рекуррентных соотношений дает эффективный метод решения многих комбинаторных задач. Пример 3.4. Найти число бинарных n-последовательностей, в которых никакие две единицы не стоят рядом. Решение. Обозначим: zn – число искомых последовательностей; хn – число последовательностей, заканчивающихся 0; уn – число последовательностей, заканчивающихся 1. Назовем для краткости последовательность, заканчивающуюся 0 – х-последовательностью, а заканчивающихся 1 – у-последовательностью. Очевидны следующие их свойства. 1) х-последовательность длиной n можно получить, приписав 0 в конец либо у-последовательности либо х-последовательности длиной n – 1. 2) у-последовательность длиной n можно получить, приписав 1 только в конец х-последовательности длиной n – 1. Отсюда имеем следующую систему уравнений: . Уравнение (a) отражает свойство 1), уравнение (b) – свойство 2), а уравнение (а) соответствует очевидному равенству. Из уравнения (b) при замене n на n – 1 имеем: уn–1 = хn–2. Подставим это равенство в (a), получим: хn = хn–1 + хn–2, т.е. числа хn образуют последовательность Фибоначчи. Вычтем (b) из (a), получим: хn – уn = уn–1  хn = уn + уn–1  уn+1 = уn + уn–1 – тоже последовательность Фибоначчи. В соответствие с формулой общего решения и уравнением (c) получим: . Для нахождения констант запишем начальные условия. z1 = 2, т.к. существует 2 последовательности длиной 1: 0 и 1. z2 = 3, т.к. существует 3 последовательности длиной 2: (0 0), (0 1), (1 0). Отсюда ; . Следовательно . Например, z9 = 89, z19 = 10946. 4. Производящие функции 4.1. Определение производящих функций. Последовательности {un}, фигурирующей в какой-либо задаче, например, комбинаторной, удобно поставить в соответствие формальный степенной ряд u(x) = , который называется производящей функцией данной последовательности. Слова “формальный ряд” означает, что эту формулу мы трактуем только как удобную запись последовательности. Для нас сейчас несущественно, при каких значениях х ряд сходится и сходится ли вообще, т.к. вычислять значение u(x) мы никогда не будем. Пример 3.5. Известно, что = 1 + х + х2 + … + хn + … Следовательно, функция является производящей для последовательности 1,…, 1. Пример 3.6. Согласно формуле бинома Ньютона (1 + х)n = . Следовательно, функция (1 + х)n является производящей для конечной последовательности . 4.2. Операции с производящими функциями. Рассмотрим основные технические приемы, применяемые в работе с производящими функциями. 4.2.а. Линейная комбинация. Если функция u(x) соответствует последовательности {un}, а v(x) – последовательности {vn}, то функция au(x) + bv(x) (a и b – константы) является производящей для последовательности { aun + bvn}. 4.2.б. Сдвиг. Если функция u(x) соответствует последовательности {un}, то функции хmu(x) соответствует последовательность … – сдвиг вправо. Аналогично, функция является производящей для последовательности um, um+1, … – сдвиг влево. 4.2.в. Умножение. Если функция u(x) соответствует последовательности {un}, а v(x) – последовательности {vn}, то функции u(x)v(x) соответствует последовательность {wn}, где – формула Коши. Например, w0 = u0v0; w1 = u0 v1 + u1 v0; w2 = u0 v2 + u1 v1 + u2 v0. Пример 3.7. Пусть u(x) соответствует последовательности {un}, а v(x) = – производящая функция для последовательности 1,…, 1 (см. пример 3.5). Тогда функция = u0 + (u0 + u1) x + (u0 + u1 + u2) x2 +… (3.9) является производящей для последовательности частичных сумм. 4.2.г. Дифференцирование и интегрирование. Если u(x) соответствует последовательности {un}, то по правилу дифференцирования рядов u(x) = 0 + u1 + 2 u2 x + 3 u3 x2 + …. То есть u(x) является производящей функцией для последовательности {k uk}. Аналогично . То естьявляется производящей функцией для последовательности . Пример 3.8. = . Следовательно, функция является производящей для последовательности {k}. Далее, (3.10) Следовательно, является производящей функцией для последовательности . Сопоставляя (3.10) с (3.9) получаем , где – гармонические числа. 4.3. Пример использования производящих функций Решим с помощью производящих функций следующую комбинаторную задачу. Пример 3.9. На окружности находится 2n точек. Сколькими способами можно их попарно соединить так, чтобы полученные отрезки не соединялись друг с другом? Решение. Обозначим un – число способов соединить 2n точек. Построим рекуррентное соотношение. Формально положим u0 = 1 (нет точек, нет пересечений, следовательно, способ единственный). u1 = 1 – очевидно, т.к. две точки соединяются единственным способом, и пересечений нет. u2 = 2. Способы соединения изображены на рис. 3.1. Пусть n > 1. Выберем одну из 2(n + 1) точек, обозначим ее А. Соединим А с вершиной В, выбрав ее так, чтобы с обеих сторон от соединяющей их линии находилось четное число точек. Пусть слева будет 2k точек, справа – 2(n – k). 2k точек можно соединить между собой uk способами, 2(n – k) точек – un–k способами. При этом линии не пересекутся, т.к. 2k и 2(n – k) точек расположены по разные сторона от АВ. Следовательно, при фиксированном k получим ukun–k способов соединения. Но k меняется от 0 до n. Следовательно, un +1 = u0un + u1un–1 + … + unu0. (3.11) Получили искомое нелинейное рекуррентное соотношение, формула общего решения которого нам, к сожалению, неизвестна. Чтобы получить явную формулу для un, построим для этой последовательности производящую функцию. u(x) = u0 + u1х + u2 x2 + u3 x3 + …. (3.12) Имеем, согласно формуле Коши: [ u(x) ]2 = (u0)2 + (u0u1 + u1u0 ) х + (u0u2 + u1u1 + u2u0)х2 + … Видно, что коэффициенты для разложения [ u(x) ]2 можно получить с помощью формулы (3.11). Из (3.12) имеем: = u1 + u2 x + u3 x2 + …. Подставим в эту формулу выражение uk согласно (3.11). С учетом того, что u1 = (u0)2 получим: . Следовательно, имеем квадратное уравнение относительно u(х). Решив его, получим . По формуле бинома имеем: ++…= 1 –. Умножим каждое k-е слагаемое на 1 = . Тогда коэффициент k-го члена ряда равен: = = = . Отсюда . Для того, чтобы коэффициенты ряда были положительными, надо перед корнем в формуле u(x) брать знак “–”. Заменим индекс суммирования k на k +1. В результате получим: u(x) = == . Окончательно – это так называемые, числа Каталана. 5. Связь производящих функций с линейными рекуррентными соотношениями Пусть имеем дробно-рациональную функцию f(x) = = , которая разлагается в ряд f0 + f1x + f2 x + …. Отсюда A(x) = B(x)f(x). Подставим вместо f(х) ее ряд – получим систему уравнений: b0 f0 = a0; b0 f1 + b1 f0 = a1; b0 f2 + b1 f1 + b2 f0 = a2; ……………………….. b0 fm –1 + b1 fm –2 +… + bm –1 f0 = am – 1; b0 fm + b1 fm –1 +… + bm f0 = 0; ……………………………….. b0 fm + n + b1 fm –1 + n +… + bm fn = 0; …………………………… Во всех уравнениях, начиная с m+1-го, правая часть равна 0, т.к. am + 1 = … = am + n =…= 0. Следовательно, имеем линейное рекуррентное соотношение b0 fm + n + b1 fm –1 + n +… + bm fn = 0, (3.13) которому удовлетворяют члены ряда для функции f(x). Таким образом, мы получили теорему о связи производящих функций с линейными рекуррентными соотношениями: Теорема 3.5. Для того, чтобы производящая функция числовой последовательности была правильной рациональной дробью необходимо и достаточно, чтобы члены этой последовательности удовлетворяли линейному рекуррентному соотношению, характеристическое уравнение которого совпадает со знаменателем этой дроби, записанным в обратном порядке. Пример 3.10. Найдем производящую функцию для чисел Фибоначчи. Решение. Имеем рекуррентное соотношение: Fn+2 – F n+1– Fn = 0. Следовательно, f(x) = . A и В легко найти с помощью деления многочленов: Следовательно, 0 = F0 = B; 1 = F1 = A + B, т.е. В = 0; А = 1 или . ЛЕКЦИЯ № 12 теория грАфов Вводные понятия Как и большинство разделов дискретной математики, теория графов возникла при решении различных головоломок. Известна точная дата ее появления – 1736 г. Это год, в котором великий математик Леонард Эйлер опубликовал статью с решением задачи о Кенигсбергских мостах. В 18 в. Кенигсберг был расположен на обоих берегах и двух островах реки Пречель. Острова были связаны между собой и с берегами семью мостами: Правый берег Левый берег Существовала популярная задача: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту ровно один раз? Размышляя над этой задачей, Эйлер для удобства рассуждений изобразил ее в виде простой геометрической фигуры – из точек, соединенных линиями. Каждый берег и остров он изобразил точками, а мосты – линиями, их соединяющими. Получилась фигура, которая сейчас называется графом: Задачу о мостах Эйлер сформулировал так: можно ли, начав движение из любой вершины, и двигаясь вдоль линий, пройти по каждой линии точно по одному разу и вернуться в исходную вершину? В современной постановке задача звучит так: существует ли в данном мультиграфе простой цикл, содержащий все ребра? В своей работе Эйлер 1) доказал, что эта задача не имеет решения; 2) сформулировал и доказал необходимое и достаточное условие существования в произвольном графе такого (Эйлерова) цикла. Потом о теории графов забыли, чтобы вспомнить в 19 веке, когда возникли задачи исследования электрических цепей, моделей кристаллов и структур молекул. Новый всплеск интереса к теории графов приходится на средину 20 века. Выяснилось, что к задачам о графах сводится множество производственных и научных задач – прокладка трасс, проектирование систем управления и интегральных схем, построение логических схем в экономике, химии, биологии. В терминах теории графов формулируются основные алгоритмы, связанные с перебором вариантов. Без преувеличения можно сказать, что теория графов – язык дискретной математики. 1.1. Основные понятия теории графов Изображение графа в виде точек и линий – это лишь наиболее наглядный способ их представления. Формально граф определяется так: граф – это пара объектов G = (V, E), где V – некоторое конечное множество, Е – отношение на V: E VV. V – множество вершин, E – множество ребер. Ребро принято обозначать либо как элемент Е: e1, …, em, ej E, либо указанием его начальной и конечной вершины (vi, vj). Второе обозначение не всегда однозначно, например, в задаче о мостах обозначению (v1, v3) соответствуют два различных ребра. Def. Графом без кратных ребер называется граф, в котором для любых i, j существует единственное ребро ek = (vi, vj). Граф с кратными ребрами называется еще мультграфом. Def. Пусть u, v – вершины, е = (u, v) – соединяющее их ребро. Тогда вершина u и ребро e инцидентны друг другу (также как и v и е). Два ребра, инцидентные одной вершине называются смежными. Две вершины, инцидентные одному ребру также называются смежными. Вершины, инцидентные одному ребру, могут быть равноправными, т.е. записи (u, v) и (v, u) эквивалентны, а могут быть неравноправными, т.е. важен порядок записи. Направленные ребра называются дугами, а содержащий их граф – ориентированным (орграфом) Направленные ребра на рисунке снабжаются стрелками – от начала к концу. Граф, в котором все ребра не направлены, называется неориентированным. Ребро вида (v, v) называется петлей. Def. Граф называется полным, если любые его две вершины смежны, E = V V. 0-граф – граф без ребер. Изолированная вершина – не смежная ни с одной другой вершиной. Def. Дополнение графа , где = (VV) \ E. Пример 1.1. Свойства графов легко связать со свойствами соответствующих бинарных отношений, т.к. R и E означают одно и то же. Например: R – симметрично  G – неориентированный; R – асимметрично  G – ориентированный, без петель; R – антисимметрично  G – ориентированный, с неориентированными петлями; R – рефлексивно  G имеет петли; отношению R–1 соответствует граф с обратной ориентацией дуг; соответствует и т.д. Изоморфизм. При изображении графа в виде точек с линиями такие понятия, как длина или кривизна линий не важны. Главное – изобразить, какие именно пара вершин соединяет данное ребро. Например, на рис. Графы а) и б) одинаковы, а а) и в) совпадают с точностью до нумерации вершин и ребер. Такие графы называются изоморфными. Более строго: Def. Пусть G = (V, E), H = (U, F) – графы. Пусть f : V  U – взаимно-однозначное отображение. Если для любых v, w  V их образы f(v) и f(w) смежны тогда и только тогда, когда смежны v и w, то f называется изоморфизмом G на H, а сами графы – изоморфными (обозначается G  H). Если f – тождественное отображение, то G = H. Пример 1.2. G  H  I, а J и K не изоморфны. 1.2. Машинное представление графа Приведем сравнительную характеристику существующих способов представления графа в памяти ЭВМ, их достоинства и недостатки. Рассмотрим конечный граф G = (V, E), где |V | = n, |E| = m. Матрица инциденций. Ориентированный граф задается прямоугольной матрицей B(nm), элементы которой определяются по правилу: где a – любое натуральное число, отличное от 1. У неориентированного графа оба элемента матрицы, соответствующие вершинам, инцидентным ребру ej, равны 1. Это представление графа является самым неудобным, так как объем занимаемой памяти равен nm единиц, причем в каждом столбце только две ненулевые ячейки. Кроме нерационального использования памяти недостатком этого способа представления является неудобный доступ к информации. Например, для ответа на вопросы: а) существует ли ребро (дуга) (vi, vj); б) к каким вершинам ведут ребра (дуги) из вершины vi требуется, в худшем случае, перебор nm элементов, т.е. порядка nm шагов алгоритма. От этого недостатка свободен следующий способ представления графа. Матрица смежности. Элементы квадратной матрицы A(nn) определяются следующим образом: Такая форма эквивалентна матричному представлению бинарного отношения (см. тема “Отношения”). Проверка существования ребра (дуги) (vi, vj) осуществляется за один шаг, в отличие от матрицы инциденций, однако, проверка свойств графа на основе такого представления требует, в худшем случае, порядка n2 шагов алгоритма. При этом способе объем неиспользованной памяти по-прежнему велик. При работе со взвешенными графами для хранения весов ребер (дуг) требуются дополнительные одномерные массивы размера m (для случая матрицы инциденций) или матрицы размера nn (для случая матрицы смежности). Это обстоятельство делает неприемлемым использование матрицы смежности для взвешенных графов, так как количество неиспользованных единиц памяти увеличивается в k раз, где k – число весов ребер (дуг). Таблица ребер. Она представляет собой матрицу размером m2, каждая строка которой содержит вершины инцидентные i-му ребру (i-ой дуге). Для работы со взвешенными графами нужно добавить к матрице столбцы, соответствующие весам ребер (дуг). Такая форма эквивалентна табличному представлению бинарного отношения Однако, этому способу представления графа присущ тот же недостаток, что и матрице инциденций, – неудобство доступа к информации, хотя число шагов при поиске ребра здесь значительно меньше (порядка m). Наиболее удобной и экономичной формой представления графа являются Списки инцидентности. Для каждой вершины viV создается список записей, характеризующих ребра (дуги), инцидентные этой вершине. Таким образом, это представление использует объем памяти порядка n + m, поиск вершины смежной с данной требует порядка n + m шагов, проверка свойств графа осуществляется за число шагов порядка n. Такая форма эквивалентна представлению бинарного отношения в виде верхних срезов. ЛЕКЦИЯ № 13 Степени, маршруты, связность 2.1. Степени вершин графов Def. Степенью вершины v графа называется число инцидентных ей ребер. Обозначается deg v. Вершина степени 0 называется изолированной, степени 1 – концевой или висячей. Для орграфа вводятся также понятия - полустепень исхода – число дух выходящих из v; обозначается deg– v; - полустепень захода – число дух входящих в v; обозначается deg+ v; Свойство. . Теорема 2.1. (Теорема Эйлера, лемма о рукопожатиях). ; Доказательство очевидно, если учесть, что каждое ребро в данной сумме учитывается 2 раза. Теорема 2.2. (о нечетных степенях). В конечном графе число вершин с нечетными степенями четно. Доказательство. Обозначим . По теореме 1.2. S четно. Далее, положим SЧ – сумма степеней вершин с четной степенью, SН – сумма степеней вершин с четной степенью. Очевидно, S = SЧ + SН. В SЧ каждое слагаемое четно, значит, само SЧ тоже четно. Отсюда, в силу четности S, получаем, что SН четно. Но каждое слагаемое в нем – нечетно. Следовательно, таких слагаемых должно быть четное число. Ч Т Д. 2.2. Маршруты и цепи Def. Пусть G = (V, E) – неориентированный граф. Маршрутом называется такая последовательность его ребер e1, … ek, что каждые два соседних ребра ej, ej+1 имеют общую вершину. Пусть e1 = (v0, v1), ek = (vk–1, vk). Тогда v0 – начальная, vk – конечная вершины маршрута. Если v0 = vk, то такой маршрут называется циклическим маршрутом. Маршрут называется цепью, а циклический маршрут – циклом, если все их ребра различны. Если все вершины цепи различны, то это простая цепь. Если все вершины цикла различны, то это простой цикл. Число ребер маршрута называется длиной маршрута. В этом графе: (1, 2) и (1, 2, 4, 7) – простые цепи; (1, 2, 4, 7, 8, 4) – цепь, но не простая; (1, 2, 4, 7, 8, 4, 2) – маршрут, но не цепь; (1, 2, 4, 1) – простой цикл; (1, 2, 4, 7, 8, 4, 1) – цикл. Задание 1. Доказать, что маршрут наименьшей длины, соединяющий две вершины графа является простой цепью. Задание 2. Обозначим d(u, v) – длина маршрута наименьшей длины, соединяющего вершины u и v. Доказать, что для любых вершин x, y, z выполняется неравенство треугольника: d(x, y)  d(x, z) + d(z, y). Для орграфа существуют аналогичные понятия: неориентированный маршрут, цепь, цикл и т.д., в которых при прохождении ребер их ориентация не принимается во внимание. Также существуют ориентированный маршрут, цепь, цикл, в которых ребра проходятся в направлении их ориентации (по стрелке). Ориентированная цепь называется также путем, ориентированный цикл – контуром. Свойства маршрутов. 1. Всякий маршрут, соединяющий вершины u и v, содержит простую цепь, соединяющую u и v. Доказательство очевидно, т.к. удалив из маршрута повторяющиеся куски, можно преобразовать его в простую цепь. 2. Всякий цикл содержит простой цикл. Доказательство аналогично. 3. Объединение двух несовпадающих простых цепей, соединяющих u и v, содержит простой цикл. Доказательство. Пусть последовательности вершин P = (u1, …, uk) и Q = (v1, …, vs) – несовпадающие простые цепи, u1 = v1 = u. Пусть ui и vi – первые, считая от u, несовпадающие вершины, а uj и vr – первые из совпадающих вершин (uj = vr) после ui и vi . Тогда ui-1, ui , …, uj , vr–1, … , vi, ui–1 – простой цикл (см. рис.) . 2.3. Связность Def. Говорят, что вершина u достижима из v, если существует маршрут, соединяющий u и v. Def. Граф называется связным, если любые его две вершины можно соединить маршрутом. Замечание. Учитывая свойство 1 маршрутов, в этих определениях слово “маршрут” можно заменить на “простая цепь”. Теорема 2.3. (1-я теорема о связности) Для связности графа необходимо и достаточно, чтобы в нем какая-нибудь фиксированная вершина u была достижима из любой другой вершины. Доказательство. Пусть вершина u достижима из любой другой вершины. Выберем две любые вершины v и w. Соединим v и u, а также w и u маршрутами. Объединив их, получим маршрут v, u, w, соединяющий вершины v и w. В силу произвольности v и w, теорема доказана. Компоненты связности Задание. Доказать, что отношение достижимости между двумя вершинами обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является эквивалентностью. Так как отношение достижимости между двумя вершинами является эквивалентностью, то, по теореме о разбиении, вершины графа можно разбить на непересекающиеся классы V1, …, Vk, и такие, что вершины, принадлежащие одному классу достижимы друг для друга, но не достижимы для вершин из любого другого класса. Образуем подграфы Gi = (Vi, Ei), соединив вершины множества Vi ребрами из множества Ei  E. Очевидно – граф распался на связные подграфы, не имеющие общих вершин и ребер. Такие подграфы называются компонентами связности графа G. Геометрически они выглядят, как отдельные изолированные куски. Теорема 2.4. (2-я терема о связности) Если в произвольном неориентированном графе ровно две вершины имеют нечетную степень, то они достижимы друг для друга. Доказательство. Пусть в графе G только две вершины u и v имеют нечетную степень. По теореме 2.2. о нечетных степенях, в конечном графе число вершин с нечетными степенями четно. Пусть Gu – компонента связности, которой принадлежит вершина u. Так как теорема 2.2 применима и к Gu , то в ней кроме u должна быть еще хотя бы одна вершина с нечетной степенью. Но во всем графе всего одна такая вершина – это v. Следовательно, v  Gu. Значит, u и v достижимы друг для друга, т.к. принадлежат одной компоненте связности. ЧТД. Теорема 2.5. (3-я терема о связности) Для n-вершинного графа с m ребрами и k компонентами связности справедливо неравенство m  n – k. Доказательство. Докажем индукцией по m. При m = 0 будет n = k, значит, неравенство выполняется. Пусть m > 0 и для графов с меньшим числом ребер неравенство верно. Удалим из графа любое ребро. Тогда число его ребер станет m1 = m – 1, а число компонент связности либо станет k + 1, либо останется равным k. Рассмотрим два случая. 1) Стало k + 1 компонент. Тогда по предположению индукции m1 = m – 1  n – (k + 1). Значит m  n – k. 2) Осталось k компонент. Тогда m1 = m – 1  n – k. Тем более m  n – k. Теорема доказана. ЛЕКЦИЯ № 14 Алгоритмы обхода вершин в графах общего вида При реализации многих алгоритмов на графах возникает необходимость организовать систематический перебор вершин графа, при котором каждая вершина просматривается точно один раз. Такой перебор можно организовать двумя способами: поиском в глубину или поиском в ширину. При этом программы, реализующие оба поиска, имеют одинаковую структуру и отличаются лишь процедурой, выполняющей перебор вершин. Основная идея алгоритма поиска в глубину состоит в последовательном движении из заданной вершины вдоль одного из ребер вглубь графа до тех пор, пока не дойдем до вершины, из которой нельзя попасть ни в какую непросмотренную вершину. После этого возвращаемся в предыдущую вершину и повторяем поиск. Если после возврата в начальную вершину останутся непросмотренные вершины, то повторим поиск, начиная из любой оставшейся вершины. Рис. 3.1 Пусть в каждом списке инцидентности все смежные вершины упорядочены по возрастанию их номеров. Тогда, например, для графа, изображенного на рис. 3.1 последовательность обхода вершин из начальной вершины 1 имеет вид: 1, 2, 4, 5, 3, 5, 6, 5, 4, 7, 4, 2, 1. Повтор вершин в списке обхода объясняется тем, что во время обратного шага приходится возвращаться в уже просмотренную вершину. Но обработка каждой вершины (т.е. какая-то длительная операция) производится ровно один раз при первом переходе к данной вершине. Поэтому, последовательность обработки вершин для графа рис. 3.1 имеет вид: 1, 2, 4, 5, 3, 6, 7. Если граф является связным, то будут просмотрены все вершины графа. В алгоритме каждой вершинеставится в соответствие логическая переменная Nowy[v], которая равна True, если данная вершина еще не просмотрена, и False, если вершина просмотрена. Вначале поиска считаем все вершины непросмотренными. Операцию обработки вершины будем символизировать печатью ее номера. Описанный в алгоритме порядок работы с вершинами, при котором вершина, просмотренная последней, обрабатывается первой, реализуется с помощью механизма стека. Он автоматически реализуется в Паскале рекурсивной процедурой, поэтому рекурсивный вариант алгоритма обычно проще, чем нерекурсивный. При построении алгоритмов мы будем пользоваться неформальным языком описания алгоритмов. Такой язык по синтаксису похож на язык программирования Паскаль, но он разрешает использование математических обозначений, не предусмотренных в Паскале. Это позволяет сосредоточиться на сути алгоритма и уйти от технических вопросов его реализации. Для реализации алгоритма на одном из языков программирования необходимо формализовать его в соответствии с правилами языка. Будем использовать обозначения 1) СПИСОК [ v ] – список инцидентности вершины v; 2) for uА – для всех элементов массива А. Опишем рекурсивную процедуру. procedure DEPTH_R(v) ; begin NOWY[v]:= False; write(v) ; for u  СПИСОК[v] do if NOWY[u] then DEPTH_R(u) ; end ; Основная программа поиска имеет вид. var NOWY : array [1..n] of boolean; begin for vV do NOWY[v]:= True ; for vV do if NOWY[v] then DEPTH_R(v) end. В первом цикле программы производится инициализация массива Nowy. Далее для первой непросмотренной вершины вызывается процедура поиска. Если граф – связный, то после возврата в основную программу поиск будет закончен. В противном случае при первом вызове процедуры DEPTH_R будут просмотрены все вершины одной компоненты связности графа, затем поиск повторится, начиная с первой непросмотренной вершины. Таким образом, обращение к процедуре DEPTH_R(v) из основной программы происходит всякий раз при переходе к очередной компоненте связности графа. Например, рассмотрим несвязный граф. Рис. 3.2 Начнем поиск с начальной вершины 1. При вызове процедуры DEPTH_R(1) получаем следующую последовательность вершин: 1, 2, 6, 3, после чего происходит выход из процедуры в основную программу, т.к. список смежности исходной вершины исчерпан. При следующем вызове процедуры просмотр начнется с первой непросмотренной вершины 4, принадлежащей следующей компоненте связности графа. Таким образом, для произвольного графа алгоритм работает корректно, то есть будут просмотрены все вершины графа, причем каждая не более одного раза. Оценим вычислительную сложность рекурсивного варианта алгоритма. В качестве основной операции, по числу выполнений которой определяется трудоемкость алгоритма, выберем вызов процедуры DEPTH_R. В основной программе она вызывается не более n раз. Внутри самой процедуры ее вызов в каждой вершине осуществляется столько раз, сколько эта вершина имеет смежных, или сколько ребер ей инцидентны. Так как каждое ребро инцидентно двум вершинам, то число вызовов не более 2m. Следовательно, вычислительная сложность алгоритма можно оценить как . Нерекурсивный поиск. Приведем нерекурсивный вариант процедуры поиска в глубину, использующий механизм стека, который организуется программистом (“вручную”). Обычно такой вариант требует меньше памяти и работает быстрее, чем рекурсивный, хотя и сложнее по реализации. Всюду в дальнейшем мы будем использовать следующие обозначения: 1) СТЕК  v, ОЧЕРЕДЬ  v – поместить вершину v в СТЕК или ОЧЕРЕДЬ; 2) v  СТЕК; v  ОЧЕРЕДЬ – извлечь вершину v из СТЕКА или ОЧЕРЕДИ. 3) top(Массив) – первый элемент массива (стека, списка или иного). 4) down(Массив) – последний элемент массива. 5) x:= top(СТЕК) – переписать в переменную х первый элемент стека, не извлекая его. 6) Next(Массив) – следующий по порядку элемент массива. procedure DEPTH( v ); begin СТЕК:= ; СТЕК  v; NOWY[v]:= False; write(v); {вершина просмотрена} while СТЕК<> do begin t:=top(СТЕК); P:= top(СПИСОК[t]); while(P<>down(СПИСОК[t]))and(not Nowy[P]) do P:= Next(СПИСОК[t]); if P<>down(СПИСОК[t])then {найдена новая вершина} begin t:=P; СТЕКt; NOWY[t]:= False; Write (t) end else {вершина t использована} t  СТЕК, end end; Головная программа имеет такую же структуру, что и для рекусивного варианта. Алгоритм поиска в ширину(очередь – queue) Основная идея такого поиска – последовательный просмотр списков инцидентности вершин, смежных с данной. При поиске в ширину, попав в новую вершину, просматривают все смежные с ней непросмотренные вершины и заносит их в список, после чего эта вершина считается обработанной. Далее переходят в новую вершину, стоящую первой в списке необработанных вершин. Иными словами, просмотр осуществляется по принципу очереди: чем раньше вершина просмотрена, тем раньше она будет обработана. Например, для графа, изображенного на рис. 3.1, последовательность просмотра вершин с помощью поиска в ширину имеет вид: 1, 2, 4, 7, 5, 6, 3. Сложность реализации алгоритма в том, что рекурсивные процедуры действуют по принципу стека, а не очереди. Поэтому в этом случае возможен только нерекурсивный вариант алгоритма. procedure BREADTH( v ) ; begin ОЧЕРЕДЬ:=; {ОЧЕРЕДЬ – локальная структура } ОЧЕРЕДЬ  v; NOWY[v]:= False; while ОЧЕРЕДЬ <>  do begin p  ОЧЕРЕДЬ; write(p); for u  СПИСОК[p] do if NOWY[u] then begin ОЧЕРЕДЬ  u; NOWY[u]:= False end end end; Как мы уже говорили, основная программа отличается от соответствующей программы поиска в глубину только именем вызываемой во втором цикле процедуры. Аналогично можно показать, что алгоритм корректен, а его вычислительная сложность также равна . ЛЕКЦИЯ № 15 Деревья Эквивалентные определения дерева Деревья – это графы специального вида. Они весьма широко используются во многих отраслях знаний и, в частности, в информационных технологиях – методах поиска информации, хранения данных, сортировке и мн. др. Существует несколько определений дерева. 1) Связный граф с n вершинами и n – 1 ребрами. 2) Связный граф без циклов. 3) Граф, в котором каждая пара вершин соединена точно одной цепью. Докажем эквивалентность этих определений. 1)  2). Докажем, что в связном графе с n вершинами и n – 1 ребрами нет циклов. Предположим противное, т.е. цикл есть и e = (u, v) – ребро этого цикла. Удалим это ребро. Тогда граф останется связным, т.к. из u в v можно добраться по другой половинке цикла. В графе G\e n вершин, n – 2 ребер и он связан, т.е. у него 1 компонента связности, k = 1. По 3-й теореме о связности должно быть m = n – 2  n – 1 – противоречие. Следовательно, циклов нет. 2)  3). Хотя бы одна цепь, соединяющая u и v должна быть, т.к. граф связный. Предположим, что цепей не одна, а хотя бы две. Тогда, по свойству 3 маршрута, из них можно составить цикл – противоречие, т.е. 2-й цепи нет. 3)  1). Из 3) следует, что граф связный. Так как каждая пара вершин соединена точно одной цепью, то удаление любого ребра увеличит на 1 число компонент связности. Пусть в графе m ребер. По 3-й теореме о связности должно быть m  n – 1. Удалив 1 ребро, получим m – 1 n – 2, т.к. станет k = 2. Удалив 2 ребра, получим k = 3 и m – 2 n – 3, и т.д. Удалим n – 1 ребер, получим k = n и m – (n – 1) n – n. Но, т.к. k = n, то ребер больше нет. Следовательно, они были удалены за n – 1 шагов, поэтому m = n – 1, ЧТД. Задание 1. Пусть Т – дерево, Т1, Т2 – его поддеревья. Доказать, что – тоже дерево. Задание 2. В дереве n > 1. Доказать, что имеется по крайней мере 2 висячих вершины. 4.2. Остов Def. Пусть G = (V, E) – неориентированный граф с n вершинами. Остовным деревом (остовом) графа G называется дерево T = (V, E1), E1  E. Остов можно построить с помощью алгоритма поиска любого вида (в глубину и в ширину). Для этого во время поиска в G параллельно строится новый граф Т: если найдена новая еще непомеченная вершина u в списке инцидентности вершины v, то ребро (v, u) добавляется в строящийся граф. Если исходный граф несвязный, то задача не имеет решения. Для связного исходного графа получим, что построенный граф является связным, так как новые ребра достраиваются к уже просмотренным вершинам, которые между собой достижимы. Этот граф не содержит циклов, так как в него не добавляется ребро, оба конца которого просмотрены, т.е. связаны маршрутом. Следовательно, построенный граф является деревом. Задача построения остова имеет большое прикладное значение. Она возникает при прокладке трасс и сетей коммуникаций, которые должны связать n заданных точек. Обычно требуют, чтобы остов обладал некоторым оптимальным свойством. Например, если каждое ребро имеет некоторый вес, то остов должен иметь минимальный вес. Алгоритм Краскала. Этот алгоритм применяется для построения остова минимального веса. Пусть имеем граф G = (V, E), в котором каждому ребру присвоен вес (e) – некоторое вещественное число. Основная идея алгоритма: начиная с полностью несвязного графа Т = (V, ), присоединяем к нему ребра графа G в порядке возрастания их веса; если после присоединения очередного ребра в Т может образоваться цикл, то это ребро не присоединяем, а переходим к следующему. Можно доказать, что таким образом строится остов минимального веса. Машинная реализация алгоритма Краскала. Сложность машинной реализации заключается в следующем. 1). Перед выполнением необходимо, чтобы ребра графа были отсортированы в порядке возрастания веса. Эта операция имеет сложность О(m2), а если граф близок к полному, то О(n4) – достаточно высокая. 2). Существенным моментом алгоритма является проверка на наличие цикла при добавлении ребра. В любом графе при добавлении ребра цикл появляется, если только присоединяемые ребра принадлежат одной компоненте связности. Следовательно, для контроля образования цикла необходимо каждой вершине приписать номер ее компоненты связности и следить, чтобы номера компонент двух соединяемых вершин всегда различались. После соединения вершин их компоненты связности сольются в одну, значит, надо соответствующим образом поменять их номера. Алгоритм. begin T:= ; for i:=1 to n do КОМП[i]:= i; for j:=1 to m do begin a:=НАЧАЛО[e[j]]; b:=КОНЕЦ[e[j]]; if КОМП[a] <> КОМП[b] then begin Т:= T; for i:=1 to n do if КОМП[i] = КОМП[b] then КОМП[i] := КОМП[a]; end; end; end.Оценим вычислительную сложность без сортировки. Просмотр списка ребер – O(m) операций. Внутренний цикл по i от 1 до n – повторяется n – 1 раз, по числу добавляемых ребер. Итого О(m) + О(n2) = О(n2). ЛЕКЦИЯ № 16 Специальные вершинные подмножества графа Определения вершинных подмножеств На основе понятий смежности, связности и достижимости на графах определяют специальные подмножества вершин. База – минимальное множество В вершин, из которых достижима любая вершина графа. База обладает следующими свойствами. 1) Каждая вершина графа достижима хотя бы из одной вершины множества В 2) В множестве В нет вершин, которая достижима из другой вершины множества В. Доминирующее множество (внешне устойчивое множество) графа – такое множество S вершин, что любая вершина из V\S смежна с какой-нибудь вершиной из S. Иными словами  uV\S  vS: (v, u) E. Доминирующее множество называется минимальным, если его подмножество уже не является доминирующим. Независимое множество (внутренне устойчивое множество) графа – множество N несмежных вершин. То есть  u, v  N (u, v)E. N называется максимальным независимым множеством, если любое множество H, включающее в себя N, уже не является независимым. Вершинное покрытие. Говорят, что вершина покрывает инцидентное ей ребро. Множество U таких вершин, которые покрывают все ребра графа, называется вершинным покрытием графа. Вершинное покрытие минимальной мощности называется минимальным вершинным покрытием. Клика (максимально полный подграф) – множество вершин К, такое, что построенный на нем подграф является полным и для любого множества H, включающего в себя К, построенный на нем подграф уже не является полным. а) База – т.к. граф связный, то любая вершина может быть базой. б) Доминирующие множества – {8, 7, 2, 5}, {7, 5, 1}, {1, 4}, {4, 6}. Два последних – минимальные доминирующие множества. в) Максимальные независимые множества – {8, 7, 2, 5}, {7, 5, 1}, {1, 4}. А {2, 7, 5} независимое, но не максимальное, т.к. включено в {8, 7, 2, 5}. г) Вершинные покрытия – {6, 3, 1, 4}, {8, 3, 2, 4, 1}, {1, 2, 3, 4, 5, 6, 7, 8}. Минимальное вершинное покрытие – {6, 3, 1, 4} мощности 4. д) Клики – {1, 2, 6}, {1, 6, 8}, {3, 4, 5}. А {1, 2, 6, 8} – не клика, т.к. нет ребра (2, 8). 5.2. Теоремы о вершинных подмножествах Теорема 5.1. (о независимости и доминировании). Независимое множество вершин максимально тогда и только тогда, когда является доминирующим. Доказательство. Необходимость. Пусть N – максимальное независимое множество. Предположим противное, что оно не доминирующее. Это значит, что есть вершина v, несмежная ни с одной вершиной из N. Тогда v можно добавить к N с сохранением у N независимости. Это противоречит тому, что N – максимальное. Достаточность. Пусть N – независимое доминирующее множество. Предположим противное, что оно не максимальное. Это значит, что есть вершина v, несмежная ни с одной вершиной из N. Это противоречит тому, что N – доминирующее. Теорема 5.2. (об эквивалентности вершинных множеств). Для любого неориентированного графа G = (V, E) и подмножества WV следующие утверждения эквивалентны. 1) W – вершинное покрытие графа G. 2) V \ W – независимое множество графа G. 3) V \ W – клика в графе . Доказательство. 1)  2). Пусть W – вершинное покрытие. Возьмем любое ребро (u, v) E. Тогда, по определению вершинного покрытия, либо u W, либо v W. То есть u и v не могут одновременно принадлежать V \ W. Значит, если одновременно u V \ W и v  V \ W, то (u, v) E. Это означает, что V \ W – независимое множество. 2)  3). Пусть U  V – какое-нибудь независимое множество. Значит для любой пары вершин u, v U будет (u, v) E или . Следовательно, U – клика в графе . Обозначим W = V \ U, тогда U = V \ W – получим нужное следствие. 3)  1). Пусть U – клика в графе . Значит для любой пары вершин u, v U будет (u, v) E. Это значит, что если (u, v) E, то или u U либо v U. Другими словами из (u, v) E следует, что либо u V \ U, либо v V \ U. Следовательно, V \ U – вершинное покрытие G. Обозначим W = V \ U (т.е. U = V \ W), получим, что если V \ W – клика в графе , то W – вершинное покрытие.