Дискретная математика

Введение Дискретная математика – самостоятельное направление современной математики. Она изучает математические модели объектов, процессов, зависимостей, существующих в реальном мире, с которыми имеют дело в технике, информатике и других областях знаний. Сегодня дискретная математика является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов – обязательное квалификационное требование к специальностям различного профиля, связанным с обработкой информации. § 1. Введение в теорию множеств Не существует строгого определения множества. Определение 1. Под множеством понимают всякое собрание каких-либо объектов. Определение создателя теории множеств Г. Кантора: «Множество – есть многое, мыслимое нами как единое. Объединение в одно целое объектов, хорошо различимых нашей интуицией или нашей мыслью». Определение 2. Объекты, из которых состоят множества, называются элементами. Общим обозначением множества служит пара фигурных скобок { }, внутри которых перечисляются элементы множества. Для обозначения конкретных множеств используются различные прописные буквы A, S, X, … или прописные буквы с индексами A1, A2, … Для обозначения элементов множества в общем виде используются различные строчные буквы a, s, x, … или строчные буквы с индексами a1, a2, … . Примеры. 1) А = {множество студентов в группе}, 2) N = {множество натуральных чисел}. Если а – элемент множества А, то пишут a  A – а принадлежит А. Множества сами могут быть элементами множеств. Например, множество натуральных чисел – элемент множества целых чисел. Большинство множеств не являются элементами самих себя. Например, множество всех котов не является элементом самого себя, потому что оно само не кот. Множества бывают конечными и бесконечными. Определение 3. Множество называется конечным, если число его элементов конечно, т.е. если существует натуральное число N, являющееся числом элементов множества. Множество называется бесконечным, если оно содержит бесконечное число элементов. Если все элементы множества А – числа, то А – числовое множество. п 1.Числовые множества Первоначальные данные о числе относятся к эпохе каменного века – палеомелита. Это «один», «мало» и «много». Записывались они в виде зарубок, узелков и т.д. Развитие трудовых процессов и появление собственности заставили человека изобрести числа и их названия. 1) Первыми появились натуральные числа N, получаемые при счете предметов. Множество натуральных чисел N  1, 2, 3,..., n,... – числа для счета предметов. 2) Затем, наряду с необходимостью счета, у людей появилась потребность измерять длины, площади, объемы, время и другие величины, где приходилось учитывать и части употребляемой меры. Так возникли дроби. Формальное обоснование понятий дробного и отрицательного числа было осуществлено в 19 веке. Множество целых чисел Z – это натуральные числа, натуральные со знаком минус и нуль. Множество целых чисел Z   n,...,3,2,1, 0, 1, 2, 3,..., n,...  ( N )  0 ( N ) 3) Целые числа и дробные образовали совокупность рациональных чисел Q, но и она оказалась недостаточной для изучения непрерывно изменяющихся переменных величин. Множество рациональных чисел – Q 1 4) Бытие снова показало несовершенство математики: невозможность решить уравнение вида х2 = 3, в связи с чем появились иррациональные числа I. Множество иррациональных чисел I – бесконечные непериодические десятичные дроби 5) Объединение множества рациональных чисел Q и иррациональных чисел I – множество действительных (или вещественных) чисел R. В итоге числовая прямая заполнилась: каждому действительному числу соответствовала на ней точка. Множество действительных чисел – R  Q  I 6) На множестве R нет возможности решить уравнение вида х2 = – а2. Следовательно, снова возникла необходимость расширения понятия числа. Так в 1545 году появились комплексные числа. Их создатель Дж. Кардано называл их «чисто отрицательными». Название «мнимые» ввел в 1637 году француз Р. Декарт. Лишь к концу 18 – началу 19 века комплексные числа заняли достойное место в математическом анализе. Множество комплексных чисел – С. п 2. Задание множеств. Пустые, равные множества, подмножества. Задание множества осуществляется либо 1) перечислением элементов, например, А = {1, 2, 3}, 2) либо с помощью характеристического свойства, т.е. свойства, которым обладает каждый элемент множества и не обладают никакие другие, например, В = {х: 1< х < 3}, 3) либо с помощью графического изображения (геометрические фигуры на плоскости) – кругов Эйлера: А Иногда характеристическим свойством не обладает ни один объект множества, что повлекло за собой введение понятия пустого множества. Определение 4. Множество, не имеющее ни одного элемента, называется пустым  . Определение 5. Множества А и В называются равными, если состоят из одних и тех же элементов: А = В. В противном случае A  B . Символ «=» равенства множеств обладает свойствами: а) Х = Х – рефлексивность, б) если Х = Y, то У = Х – симметричность, в) если Х = У и У = Z, то Х = Z – транзитивность. Из определения 4 вытекает, что порядок элементов в множестве не существенен. Например, А = {1, 2, 3, 4} и В = {4, 1, 3, 2} – одно и то же множество. Из определения множества следует, что в нем не должно быть неразличимых элементов, поэтому в множестве не может быть одинаковых элементов. Запись {1, 1, 2, 3} следует рассматривать как некорректную и заменять на {1, 2, 3}. Определение 6. Символ  – отношение включения множеств, т.е. если A  B (А включено в В), то каждый элемент множества А является элементом множества В. При этом множество А называется подмножеством, множество В – надмножеством. Если A  B и A  B , то А называется собственным подмножеством В. В этом случае пишут A  B . Пустое множество  – подмножество любого множества. п 3. Действия над множествами 1) Подмножество: A  B А В Если может быть А = В, то пишут A  B . 2) Объединение множеств: A  B Определение 7. Объединением множество A  B  x x  A или x  B. В А множеств А и В называется 2 Свойства объединения: а) A  B  B  A , б) A   = А, в) A  A  A , г) если A  B , то A  B  B 3) Пересечение множеств: A  B В А Определение 8. Пересечением множеств А и В называется множество A  B  x x  A и x  B. Свойства пересечения: а) A  B  B  A , б) A   =  , в) A  A  A , г) если A  B , то A  B  A Определение 9. Два множества называются непересекающимися, если A B =  . 4) Разность множеств: A\ B B\ A В А В А Определение 10. Разностью множеств А и В называется множество М, которое содержит все элементы А, не входящие в В: M  x x  A и x  B. Свойства разности: а) A \ A   , б) A \   A . 5) Симметрическая разность: А А В В А Определение 11. Симметрической разностью множеств А и В называется множество В  ( A \ B)  ( B \ A) 6) Если все построение происходит на некотором фиксированном множестве U, то U называют универсальным множеством. Его графически удобно изображать в виде множества точек прямоугольника. А Дополнение множества А: A U Определение 12. Если A  U , то множество элементов x U , но x  A называется дополнением множества А относительно множества U и обозначается A  U \ A , т.е дополнением множества А называется разность U \ A . Свойства множеств (Доказать самостоятельно с помощью кругов Эйлера). 1. A  A , 2. Если A  B и B  C , то A  C – транзитивность, 3. A  B  A  A  B , 4. A  B  B  A  B , 5. A \ B  A . Законы алгебры множеств. Булева алгебра Пусть А, В, С – произвольные подмножества множества F. Тогда непосредственно из определений объединения, пересечения и дополнения вытекают следующие законы: 1. A  B  F , A  B  F – замкнутость операций объединения и пересечения, 2. A  B  B  A , A  B  B  A – коммутативность операций объединения и пересечения, 3. A  ( B  C )  ( A  B)  C – ассоциативность операции объединения, 4. A  ( B  C )  ( A  B)  C – ассоциативность операции пересечения, 5. A  ( B  C )  ( A  B)  ( A  C ) – дистрибутивность операции пересечения относительно операции объединения, 3 6. A  ( B  C )  ( A  B)  ( A  C ) – дистрибутивность операции пересечения, 7. A  A  A  A  A , 8. ( A  B  B)  ( A  B  A) , 9. A    A, A  F  A, A    , A  F  F , 10. A  A  F , A  A   , операции объединения относительно 11. ( A  B)  A  B , ( A  B)  A  B – законы де Моргана. Определение 13. Если для элементов множества   {A, B, C,...} определены операции объединения  и пересечения  , для которых выполняются данные законы, то тройка ( , , ) называется булевой алгеброй. Таким образом, если  – семейство всех частей множества F, то ( , , ) – булева алгебра. Отличие алгебры чисел от алгебры множеств: Если а и b – два числа, то между ними может быть три соотношения: a > b, a < b, a = b. Для двух множеств А и В может не выполняться ни одно из соотношений: A  B , B  A , А = В. п 4. Основные определения теории множеств Определение 14. Пусть А и В – множества. Правило f, которое каждому элементу а множества А соотносит один и только элемент b множества В, причем каждый элемент b  B оказывается соотнесенным одному и только одному элементу a  A , называется взаимно-однозначным соответствием между множествами А и В. Правило f – функция. Определение 15 Число элементов конечного множества А называется мощностью множества и обозначается символом A или Card A. (от английского cardinality - мощность). Определение 16. Если между множествами А и В можно установить взаимнооднозначное соответствие, то множества называются эквивалентными. A ~ В или что они имеют одинаковую мощность. Замечание. Два конечных множества оказываются эквивалентными тогда и только тогда, когда они состоят из одинакового числа элементов. Так что понятие одинаковой мощности есть прямое обобщение понятия одинаковой численности конечных множеств. Примеры эквивалентных множеств: а) А и В – множества точек на параллельных сторонах прямоугольника, б) А и В – множества точек двух концентрических окружностей. Определение 17. Множество, эквивалентное множеству всех натуральных чисел, называется счетным. 1   1 Примеры счетных множеств: 1) N, 2) А = {1, 4, 9, 16,…, n2, …}, 3) В = 1, ,..., ,... . n   2 Теорема 1. Для того, чтобы множество А было счетным, необходимо и достаточно, чтобы его можно было «перенумеровать», т.е. представить в форме последовательности: A  a1, a2 ,..., an ,.... Примеры. 1. Все числовые последовательности эквивалентны множеству натуральных чисел. 2. На первый взгляд кажется, что множество целых чисел невозможно перенумеровать. Ведь если мы начнем нумерацию с числа 0, а потом будем нумеровать вправо, то все отрицательные числа окажутся незанумерованными. Если же мы будем нумеровать влево, то незанумерованными окажутся все положительные числа. Однако нумерацию можно осуществить, если двигаться не в одном направлении, а все время менять его. Иными словами, будем нумеровать так: числу 0 дадим номер 1, числу 1 – номер 2, числу –1 – номер 3, числу 2 – номер 4, числу –2 – номер 5 и т.д. Мы получим таким образом взаимно однозначное соответствие между множествами Z и N. Следовательно, Z и N эквивалентны и Z является счетным множеством. 3. Еще сложнее занумеровать все точки плоскости, обе координаты которых – целые числа. Эти точки, как говорят, образуют решетку. Чтобы занумеровать все точки решетки, можно, например, 4 вести нумерацию по «раскручивающейся спирали». Следовательно, множество точек плоскости с целочисленными координатами являются примером счетного множества. Теорема 2. Каждое бесконечное подмножество А счетного множества В счетно. Теорема 3. Объединение конечного или счетного множества счетных множеств счетно. Однако не все бесконечные множества являются счетными. Существуют и такие множества, элементы которых нельзя перенумеровать. Простейшим примером такого множества является множество всех точек конечного интервала, например, интервала (0, 1). Ясно, что в этом множестве содержится счетное подмножество. В качестве такого подмножества можно указать, например, 1  1 1 числовую последовательность  , ,..., ,... . Но оказывается, что точек в интервале (0, 1) n  2 3 «намного больше», чем точек этой последовательности. Точнее говоря, множество точек интервала (0, 1) несчетно, т.е. нельзя установить взаимно однозначное соответствие между множеством точек интервала (0, 1) и множеством натуральных чисел N. Определение 18. Множество всех подмножеств данного множества А называют булеаном множества и обозначают символом B(A) ( в некоторых источниках Р(А) или 2А. Другие названия булеана – степень множества, показательное множество, множество частей. Ясно, что   B(A) , A B(A) . Например, Пусть A  {x, y, z} , тогда полный список подмножеств и, следовательно, булеан множества равен B( A)  {}, {x}, { y}, {z}, {x, y}, {x, z}, { y, z}, {x, y, z}, где   {}. Теорема 4. Для любого конечного множества A, если мощность его Card A = n, то мощность булеана равна Card B(A)=2n. Пример. Пусть A = {1,2,3}. Найти количество элементов булеана и перечислить все его элементы. Решение. B(A)={ ,{ 1 },{ 2 },{ 3},{ 1,2 },{ 1,3 },{ 2,3},{ 1,2,3 } }. Замечание 1. Если два множества равномощны, то равномощны и их булеаны. Замечание 2. Диагональ Кантора показывает, что булеан множества (бесконечного или нет) всегда имеет строго большую мощность, чем само множество (проще говоря, булеан должен быть 'больше', чем исходное множество). Булеан множества натуральных чисел, например, можно поставить во взаимно-однозначное соответствие с множеством вещественных чисел. Замечание 3. Булеан множества вместе с операциями объединения, пересечения и дополнения можно рассматривать как типичный пример булевой алгебры. Пример. Дано множество Н ={1,2,3,4,…, 10} и его подмножества А, В и С, причем A  {x 2  x  8}, В = {x х – простое число}, С = {x х – кратно 5}. Пусть множество M  ( A \ B)  C и В(М) – булеан этого множества. Тогда истинным будет утверждение: 1) {{3, 6, 10}} B(M ) , 2) {{3}, {5, 6, 10}}  B(M ) , 3) { 5, 6, 10}  B(M ) , 4) {{5}, {5, 6, 10}} B(M ) . Решение. A  {2, 3, 4, 5, 6, 7, 8} , B  {1, 2, 3, 5, 7} , C  { 5, 10} .Найдем множество A \ B  {4, 6, 8} , тогда множество M  ( A \ B)  C  {4, 5, 6, 8, 10} . Истинным будет 4) утверждение. Определение 19. Множество называется линейным, если все его элементы лежат на некотором промежутке прямой. Множество называется плоским, если все его элементы лежат в одной плоскости. Определение 20. Пусть а – элемент линейного множества. Интервал длины 2ε с центром в точке а называется окрестностью точки а: (a   ; a   ) . Пусть b – элемент плоского множества, т.е. его координаты b(x0 y0). ε- окрестностью точки b называется внутренность любого круга радиуса ε с центром в точке b: ( x  x0 )2  ( y  y0 )2   2 . Определение 21. Точка называется внутренней точкой множества, если она принадлежит ему вместе со своей окрестностью. Определение 22. Множество называется открытым, если все его точки внутренние. 5 Пример: 1) (a, b), 2) R, 3)  . Определение 23. Множество называется связным, если любые две его точки можно соединить непрерывной кривой или ломаной, целиком лежащей в данном множестве. Определение 24. Множество, состоящее из внутренних точек и обладающее свойством связности называется открытой областью или просто областью. Примеры наипростейших областей: внутренность круга, треугольника, эллипса. Определение 25. Точка, не принадлежащая области, называется граничной или предельной, если любая ее окрестность содержит точки, принадлежащие области. Множество всех граничных точек – граница множества. Определение 26. Множество, образованное областью и ее границей называется замкнутой областью. Иначе, множество называется замкнутым, если оно содержит все свои предельные точки. Определение 27. Линейное множество называется ограниченным, если существует отрезок, внутри которого оно содержится. Плоское множество называется ограниченным, если существует круг, внутри которого оно содержится. п 5. Понятие меры Определение 28. Мерой линейного ограниченного открытого множества М = (a, b) называется его длина. mes M = mes(a,b) = m(a,b) = b – a. х b а Определение 29. Мерой непустого ограниченного замкнутого линейного множества F = [a,b], где F  S  [ A, B] , называется число, равное mes F = B – A – mes F ( F  S \ F ) а A F b B х Определение 30. Иными словами, мера множества – обобщающее понятие длины, площади или объема множества в зависимости от того, какое множество рассматривается: линейное, плоское или объемное. Примеры. Найти меру а) линейного множества А – точек интервала (ОС) оси (Ох), где О(0), С(3), b) плоского множества Х – точек квадрата АВСД, где А(2,2), В(4,2), С(4,4), Д(2,4). Решение. О а) С А С 3 х mes А = 3 b) 4 Д С 2 А В mes Х = SАВСД = 2 · 2 = 4 х О 2 4 Определение 31. Множества, имеющие меру, называются измеримыми. С п 6. Верхняя и нижняя границы множества. Супремум и инфимум. Имея дело с множеством вещественных чисел, можно сравнивать элементы этого множества по их значению и, в частности, находить наибольший и наименьший элементы множества. Для конечных 6 множеств, заданных перечислением, эта задача не представляет труда. Так, для множества Т = {4, 3, 5, 6} имеем maxT = 6, minT = 3. Однако если множество задано описательным способом, например, указано лишь правило вычисления числовых значений его элементов, то задача определения наибольшего и наименьшего элементов становится весьма трудной. Несколько более легкой задачей является нахождение лишь области, внутри которой лежат все элементы множества. При решении этой задачи очень полезными являются понятия верхней и нижней границ множества. Рассмотрим линейное множество. Определение 32. Множество А называется ограниченным сверху (снизу), если существует число b такое, что для любого элемента a  A выполняется условие: a  b (a  b) . Число b называется верхней (нижней) гранью множества. Определение 33. Множество ограниченное и сверху и снизу называется ограниченным. Примеры 1) ограниченного множества – (a, b), [a, b], 2) ограниченного сверху множества – (–∞, а], 3) ограниченного снизу множества – (а, ∞). Любое ограниченное сверху (снизу) множество А имеет бесконечно много верхних (нижних) граней, образующих множество чисел, ограничивающих множество А сверху (снизу). Пусть b – верхняя грань, тогда b/ такое что b/ > b, также верхняя грань. Чисел, которые могут рассматриваться в качестве верхней границы множества, может быть бесконечно много, а может и не быть вообще. Так, в множестве A = {y < x < z} любое d  z является верхней границей. Множество всех целых чисел не имеет верхней границы. Определение 34. Наименьшее из чисел, ограничивающих множество А сверху, называется точной верхней гранью множества А или супремумом и обозначается sup A . Наибольшее из чисел, ограничивающих множество А снизу, называется точной нижней гранью множества А или инфимумом и обозначается inf A . Примеры: 1) Х = (a, b), тогда inf X = а, sup X  b 2) А = (а, +∞), тогда inf X = а, sup A не существует. Теорема 5. Любое непустое ограниченное сверху (снизу) числовое множество имеет точную верхнюю (нижнюю) грань. Теорема 6. (теорема о верхней и нижней границах подмножества). Если B  A , то inf В  inf А, sup В ≤ sup А. п 7. Упорядоченные множества Определение 35. Множество M называется упорядоченным, если между его элементами установлено некоторое отношение a < b (a предшествует b), обладающее следующими свойствами: 1) между любыми двумя элементами a и b существует одно и только одно из трех соотношений: a = b, a < b, b < a; 2) для любых трех элементов a, b и c из a < b, b < c следует a < c. Пример: ) множество натуральных чисел, 2) пустое множество считается упорядоченным. Замечание. Знак = мы всегда понимаем в смысле тождества, совпадения элементов. Запись a = b просто означает, что буквами a и b обозначен один и тот же элемент множества M. Поэтому из свойства 1) следует, что между двумя различными элементами выполняется одно и только одно из двух соотношений a < b или b < a. Если a предшествует b, то говорят, что b следует за a и пишут: b > a. Если в упорядоченном множестве M поменять ролями отношения < и >, т. е. вместо a < b писать a > b, и наоборот, то получится новое упорядоченное множество M', порядок которого называется обратным относительно порядка M. Например, для порядка во множестве натуральных чисел обратным будет порядок: ..., 3, 2, 1. Два упорядоченные множества, составленные из одних и тех же элементов, но расположенные в разном порядке, считаются различными. Поэтому при задании упорядоченного множества через его элементы необходимо указать их порядок. Будем считать, что запись слева направо соответствует порядку элементов, и сохраним прежнее обозначение фигурными скобками. Одно и то же множество можно упорядочить различным образом (если оно содержит не менее двух элементов). Так, множество натуральных чисел можно упорядочить обычным образом или в 7 обратном порядке, можно нечетные числа поставить впереди четных или наоборот, располагая те и другие в возрастающем или убывающем порядке. Получим упорядоченные множества: 1){1, 2, 3, ...}, 2){..., 3, 2, 1}, 3){1, 3, 5, ..., 2, 4, 6, ...}, 4){1, 3, 5, ..., 6, 4, 2}, 5){..., 5, 3, 1, 2, 4, 6, ...}, 6) {..., 5, 3, 1, ..., 6, 4, 2}. Замечание. Частично упорядоченное множество — понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определѐнной последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими (какие элементы больше каких). В общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за». В качестве абстрактного примера можно привести совокупность подмножеств множества из трѐх элементов {x,y,z} (булеан данного множества), упорядоченную по отношению включения. п 8. Элементы комбинаторики Определение 36. Комбинаторика – математический аппарат для вычисления числа различных комбинаций элементов множества. Теорема 7. Из m элементов а1, а2,…, аm и n элементов b1, b2,…, bn можно образовать ровно (m  n) различных пар (ai, bj), содержащих по одному элементу из каждой группы. Доказательство. Составим из этих пар прямоугольную таблицу, содержащую m строк и n столбцов, так, чтобы пара (ai, bj) стояла на пересечении i-той строки и j-ого столбца. Каждая из пар встретиться в таблице один и только один раз, что и требовалось доказать. Пример. Электрическая лампа с несколькими способами включения содержит три обычные лампочки и светящую арматуру, которая может работать в трех положениях или может быть выключена. Каждая из этих возможностей комбинируется с 0, 1, 2, 3 включенными лампочками. Следовательно, всего имеется 4  4  16 возможных комбинаций, из которых одна (0, 0) означает, что лампа не светит. Остается 15 способов включения лампы. Теорема 8. Пусть даны k групп элементов: m элементов первой группы а1, а2,…, аm; n элементов второй группы b1, b2,…, bn ;…..; s элементов k- ой группы с1, с2,…, сs. Тогда можно образовать ровно (m  n  ...  s) различных комбинаций (ai1 , bi2 ,...  cik ) , содержащих по одному элементу из каждой группы. Пусть дано конечное множество A  a1, a2 ,..., an  , состоящее из n элементов. Его называют генеральной совокупностью. Определение 37. Произвольное упорядоченное множество ai1 , ai2 ,..., ai m , состоящие из m (m < n) элементов, входящих в генеральную совокупность, называется набором или выборкой объема m из А. Определение 38. Объем выборки – это количество элементов в выборке. В некоторых наборах порядок элементов не важен, в некоторых – элементы могут повторяться (выбор с возвращением), а могут быть все различными (выбор без возвращения). Определение 39. Комбинаторная конфигурация – это расположение конечного множества элементов, удовлетворяющих ряду специальных свойств. К основным комбинаторным конфигурациям относятся сочетания, размещения и перестановки.   Определение 40. Неупорядоченные наборы элементов называются сочетаниями, упорядоченные – размещениями, упорядоченные без повторений – перестановкой. Определение 41. Комбинаторные формулы – формулы пересчета числа комбинаторных конфигураций. Рассмотрим подробно каждый выбор элементов из конечного множества A  a1, a2 ,..., an  , состоящего из n элементов. Сочетания Сочетания из n элементов множества по m элементов – неупорядоченные наборы различных m элементов из n. Это подмножества множества А. 8 Пример. А = {1, 2, 3}, тогда сочетания из 3 элементов по 2 – это наборы (1, 2), (1, 3), (2, 3). Всего 3 набора, при этом надо помнить, что (1, 2) = (2, 1) и т.п., так как при образовании сочетаний порядок элементов не учитывается. Определение 42. Число сочетаний, которые можно образовывать, выбирая различными способами m элементов из n, обозначают Cnm и называют биномиальными коэффициентами (они совпадают с биномиальными коэффициентами формулы бинома Ньютона для степени n). Теорема 9. Число различных выборок объема m из совокупности A  a1, a2 ,..., an  объема n, если выбор производится без возвращения и без учета порядка выбираемых элементов, то есть число n! сочетаний, равно Cnm  . m!(n  m)! Свойства сочетаний: 1) Cnm  Cnn  m , 2) Cn0  1 , 3) Cnn  1 , 4) Cn1  Cnn 1  n , 5) Cnm  Cnm11  Cnm1 , 6) Cnm  0 , если m > n. 3! В приведенном выше примере C32   3 . (3 набора) 2!1! Размещения Размещения из n элементов множества по m элементов – упорядоченные цепочки (ai1, ai 2 ,..., aim ) различных m элементов из n. Это подмножества множества А. Пример. А = {1, 2, 3}, тогда размещения из 3 элементов по 2 – это наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2). Всего 6 наборов. Определение 43. Число размещений, образованных выбором различных упорядоченных цепочек длины m из n элементов множества А, обозначают Anm . Теорема 10. Число различных выборок объема m из совокупности A  a1, a2 ,..., an  объема n, если выбор производится без возвращения, но с учетом порядка выбираемых элементов, то есть n! число размещений, равно Anm  n  (n  1)  ...  (n  m  1)  . (n  m)! Свойства размещений: n!  n , 3) Ann 1  n! , 4) Ann  n! 1) Anm  Cnm  m! , 2) An1  (n  1)! Замечание. На одно место претендует один элемент. 3! 6   6 . (6 наборов). В приведенном выше примере A32  (3  2)! 1 Перестановки Определение 44. Размещения из n элементов множества А по n называют перестановками и обозначают Ann  Pn . Различные перестановки содержат одни и те же элементы, расположенные в разном порядке. Следствие из теоремы 8. Число различных перестановок, образованных выбором различных упорядоченных цепочек длины n из n элементов множества А равно Pn  Ann  n! . Замечание. На одно место претендует один элемент. Размещения с повторениями Теорема 11. Число различных выборок объема m из совокупности A  a1, a2 ,..., an  объема n, если выбор производится с возвращением и с учетом порядка выбираемых элементов, равно nm. Замечание. На одно место претендует несколько элементов. 9 Примеры. 1. В коробке находятся карточки с цифрами от 1 до 9. Вытаскивают подряд 3 карточки и записывают цифры в ряд согласно поступлению. Чему равно количество всевозможных трехзначных чисел? 9! 9! Решение. Это размещения из 9 по 3. Их количество равно: A93    7  8  9  504 . (9  3)! 6! 2. Из группы в 25 человек выбирают 3-х человек для участия в конференции. Чему равно количество всевозможных троек? Решение. Это сочетания из 25 по 3. Их количество равно: 25! 23  24  25 3 C25    23  100  2300 . 3!(25  3)! 6 3. Имеется 6 билетов спортлото. Сколькими способами можно выбрать два билета? 6! 5  6 Решение. Это сочетания из 6 по 2. Их количество равно: C62    15 . 2!4! 2 4. Имеется 6 билетов спортлото и 10 билетов автолотереи. Сколькими способами можно выбрать один билет спортлото и один билет автолотереи? 1 Решение. C61  C10  6  10  60 или по теореме 3 сразу 6  10  60 . 5. Сколькими способами можно рассадить 1) 15 человек на 15 стульев, 2) 10 человек на 15 стульев? Решение. На одно место претендует один человек. 1) Это перестановки из 15 по 15. Их 15 количество равно: Pn  A15  15! 2) Это размещения из 15 по 10. Их количество равно: 15! 15! 10 A15    6  7  8  9  10  11  12  13  14  15  10897286400 . (15  10)! 5! 6. Сколькими способами можно разложить 15 шариков по 10 корзинам? Решение. Это размещения с повторениями, так как в одну корзину можно положить несколько мячей. Количество способов равно: 1015. п. 9. Кортеж. Прямое произведение множеств Определение 45. Множество a, b называется неупорядоченной парой или просто парой, если выполняется свойство: a, b  b, a. Определение 46. Множество (a1 , a2 ) называется упорядоченной парой, если указано, какой из этих элементов первый, какой второй, при этом (a1 , a2 )  (b1 , b2 )  a1  b1 , a2  b2 , в частности (a1 , a2 ) = (a2 , a1 )  a1  a2 . (a1 , a2 ,..., an ) – упорядоченная система из n элементов. (n-ка элементов). Элементы а1, а2, …, аn называются координатами упорядоченной системы. Определение 47. Кортеж – последовательность элементов, т.е. совокупность элементов, в которой каждый элемент занимает определенное место. Сами элементы при этом называются компонентами кортежа (первая компонента, вторая компонента и т.д.) или координатами. Примеры кортежей: множество людей, стоящих в очереди; множество слов в фразе; числа, выражающие долготу и широту точки на местности и т.п. Во всех этих множествах место каждого элемента является вполне определенным и не может быть произвольно изменено. В технических задачах эта определенность часто является просто предметом договоренности. Так, только договоренностью можно объяснить, почему долготу ставят на первое место, а широту на второе. Состояние кибернетической системы часто описывают множеством параметров, принимающих числовые значения. При этом состояние системы – просто некоторое множество чисел. Чтобы не оговаривать каждый раз, какое число что означает, устанавливают заранее, какой параметр считать первым, какой вторым и т.д., т.е. совокупность параметров представляют в виде упорядоченного множества. Так, если обозначить через h высоту самолета при полете, а через v – его скорость, то кортеж x = (h, v) будет описывать состояние самолета. 10 Определение 48. Число элементов в кортеже называется его длиной. Кортеж длины нуль называется пустым, обозначается ( ) или  . Кортежи длины 2 называются парами или упорядоченными парами, кортежи длины 3 – тройками, 4 – четверками и т.д. В общем случае кортежи длины n называются n-ками. Иначе определение 47. Кортеж или упорядоченная n-ка элементов – упорядоченный набор длины n (где n – любое натуральное число либо нуль): (a1 , a2 ,..., an ) , каждый элемент которого принадлежит некоторому множеству. Элементы кортежа могут повторяться в нѐм любое число раз (этим, в частности, он отличается от упорядоченного множества, куда каждый элемент может входить только в одном экземпляре): два одинаковых слова в фразе; одинаковые числовые значения долготы и широты точки на местности и т.п. Упорядоченная пара – частный случай кортежа. Примеры кортежей: 1) пустое множество – кортеж (с нулевым количеством элементов), 2) для каждого кортежа A  (a1, a2 ,..., an ) множество (a, a1 , a2 ,..., an )  a, a, A также является кортежем, 3) точка в n-мерном пространстве действительных чисел определяется как кортеж длины n, составленный из элементов множества действительных чисел. Кортеж (а1, а2, а3) может рассматриваться как точка в трехмерном пространстве или как трехмерный вектор, проведенный из начала координат в эту точку. Определение 49. Прямым или декартовым произведением двух множеств А и В называется множество A B всех упорядоченных пар (a, b) , в которых первый элемент a  A , а второй b  B : A  B  (a, b) a  A, b  B. Например, если A  k , l, B  1, 2, 3, то A  B  (k ,1), (k ,2), (k ,3), (l ,1),(l ,2), (l ,3). Замечание 1. Обозначение упорядоченной пары может быть таким: произведения – A  B   a, b  a  A, b  B прямого , Замечание 2. Элементами прямого произведения являются двухэлементные кортежи вида ( x1 , x2 ) . Замечание 3. A  B  B  A , т.е. результат прямого произведения зависит от порядка сомножителей. у Геометрическое представление. 1) Например, если тогда A  1, 2, B  1, 2, 3, A  B  (1,1), (1,2), (1,3), (2,1),(2,2), (2,3), и геометрически прямое произведение представляется в виде точек (рис.). у 3 2 1 О х 1 2 2) Пусть X и Y – отрезки вещественной оси. Прямое произведение X × Y изобразится заштрихованным прямоугольником, показанным на рис. Y х О X Примеры. 1. Прямое произведение окружности и прямой — это цилиндр: S 1  R1 . 2. Прямое произведение двух прямых – плоскость: R1  R1 . 3. Прямое произведение двух окружностей – тор: S 1  S 1 . Определение 50. Прямым или декартовым произведением n множеств А1, А2, …, Аn называется n A  A  ...  множество A1  A2  ...  An  (a1, a2 ,...an ) a1  A1,..., an  An . Множество    A  A , где n – n 11 целое неотрицательное число, называется n – кратным декартовым произведением множества А на себя или n-ой декартовой (Декартовой) или прямой степенью множества А. При положительных n декартова степень An состоит из всех упорядоченных наборов (кортежей) элементов из А длины n. При n = 0, декартова степень А0 по определению содержит единственный элемент – пустой кортеж. Примеры. 1. При записи шахматной партии для обозначения вертикалей.  2. Упорядоченный набор – это вектор x  ( x1 , x2 ,..., xn ) 3. 000 001 002 010 011 012 020 021 022 100 101 102 110 111 112 120 121 122 200 201 202 210 211 212 220 221 222 {0, 1, 2}3, 33 = 27 элементов п 10. Бинарные отношения Определение 51. n –местным отношением или отношением с n аргументами на множестве А называется всякое подмножество множества Аn, т.е. всякое множество n-ок элементов А. Пример. 3-местное отношение «между» для точек прямой – это множество всех троек (a, b, c) таких, что точка а лежит между точками b и c. Замечание. Одноместное отношение на множестве А – есть подмножество А и называется свойством на А. Двуместное отношение называют бинарным отношением. Определение 52. R называют бинарным отношением на множестве A, если R  A  A . Запись: чтобы обозначить принадлежность упорядоченной пары (a, b) к бинарному отношению R вместо записи (a, b)  R используют обозначения R(a, b) или aRb. При этом говорят, что а находится в отношении R к b. Определение 53. Если R  A  B , то говорят что R определено на паре множеств A и B. Если А = В, то говорят, что R задано на множестве А. Определение 54. Областью определения отношения R называется множество всех первых элементов пар из R, т.е. множество всех а таких, что (a, b)  R хотя бы при одном b. Dom R  {a  b ((a, b)  R)} . Обозначение: Dom R Определение 55. Множеством значений отношения R называется множество всех вторых элементов пар из R, т.е. множество всех b таких, что (a, b)  R хотя бы при одном a. Обозначение: Im R Im R  {b  a ((a, b)  R)} . Определение 56. Обратным отношением к R или инверсией называется множество R 1 всех R 1  {(a, b) (b, a)  R} . упорядоченных пар (a, b) таких, что (b, a)  R . Определение 57. Взаимообратными отношениями называются отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого. Примеры. 1. Бинарное отношение отцовства на множестве всех людей есть множество всех упорядоченных пар (a, b) таких, что a и b – люди и a – отец b. 2. Пусть A  {a, b, c, d , e, f , g , h} и B  {1, 2, 3, 4, 5, 6, 7, 8}, тогда подмножество {(a,2), (c,3), (d ,5)} в декартовом произведении A B является бинарным отношением между множествами А и В. 12 3. На множестве целых чисел Z отношение делимости, состоящее из упорядоченных пар (m, n) , в которых m делится на n, является бинарным отношением. В этом случае обозначение mRn заменяется на m : n. у 4. На множестве действительных чисел R упорядочение «  » – «меньше x y или равно» или «не больше» является бинарным отношением на R, x=y 2 состоящим из всех точек плоскости R , лежащих не ниже прямой x – y = 0 х (см.рис.). 5. Для функции f : X  Y ее график Г(f) = {( x, y) y  f ( x), x  X } О является бинарным отношением между X и Y. 6. На множестве всех неотрицательных целых чисел Z+ = N  {0} упорядочение « < » – «меньше» является бинарным отношением R, область определения которого – Z+, множество значений – Z+ \ {0}, обратным отношением R 1 к нему является отношение « > » – «больше». Свойства бинарного отношения на множестве. Определение 58. Бинарное отношение R на множестве А обладает свойством рефлексивности или называется рефлексивным, если (a, a)  R для всех a  A , то есть для любого а этого множества элемент а находится в отношении R к самому себе. Примеры рефлексивных отношений: равенство, одновременность, сходство. Определение 59. Бинарное отношение R на множестве А обладает свойством антирефлексивности или называется антирефлексивным, если (a, a)  R для всех a  A . Примеры нерефлексивных отношений: «заботиться о», «развлекать», «нервировать». Определение 60. Бинарное отношение R на множестве А обладает свойством симметричности или называется симметричным, если (a, b)  R влечет за собой (b, a)  R для всех a, b  A . Примером симметричных отношений могут быть: равенство «=», отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства). Определение 61. Бинарное отношение R на множестве А обладает свойством антисимметричности или называется антисимметричным, если (a, b)  R и (a, b)  R 1 влекут за собой a  b для всех a, b  A , то есть R и R-1 выполняются одновременно лишь для равных между собой членов. Определение 62. Бинарное отношение R на множестве А обладает свойством асимметричности или называется асимметричным, если (a, b)  R, a  b , влечет за собой (b, a)  R для всех a, b  A . Пример: отношение «больше» (>) и «меньше» (<). Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности. Определение 63. Бинарное отношение R на множестве А обладает свойством транзитивности или называется транзитивным, если (a, b)  R и (b, c)  R влечет за собой (a, c)  R для всех a, b, c  A . В противном случае отношение называется нетранзитивным. Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее». Пример нетранзитивного отношения: «x отец y» Определение 64. Бинарное отношение R на множестве А обладает свойством связанности или называется связанным, если (a, b)  R или (b, a)  R для всех a, b  A , то есть, что для любых двух различных элементов a и b из множества A, одно из них находится в отношении R к другому. Пример: отношение «меньше» (<). Примеры. 1. Отношение делимости целых чисел из примера 3 является 1) рефлексивным: любое целое число m делится на себя, то есть m : m; 2) транзитивным: если m делится на n, а n делится на k, то m делится на k. 13 2. Отношение «  » – «меньше или равно» или «не больше» на множестве целых чисел обладает свойствами: 1) рефлексивности ( 7  7) ; 2) транзитивности (если 7  8, 8  9, тогда 7  9); 3) асимметричности (из того что 7  8 не следует, что 8  7); 4) связанности. 3. Отношение « < » – «меньше» на множестве действительных чисел обладает свойствами: 1) антирефлексивности ( 7 не меньше 7) ; 2) транзитивности (если 7 < 8, 8 < 9, тогда 7 < 9); 3) асимметричности (из того что 7 < 8 не следует, что 8 < 7). 4. Отношение «иметь по крайней мере одного общего родителя» на множестве людей является: 1) рефлексивным, 2) симметричным (если х и у имеют одного общего родителя, то и у с х имеют одного общего родителя), 3) не транзитивным (если х и у имеют одного общего родителя, и у с z имеют одного общего родителя, то не обязательно, что х и z имеют одного общего родителя) Определение 65. Бинарное 1) рефлексивное, 2) симметричное, 3) транзитивное отношение называется отношением эквивалентности. Примеры. 1. Отношение параллельности между прямыми в плоскости. 2. Отношение подобия на множестве треугольников в плоскости. 3. Обмениваемость товаров на рынке. 4. Пример отношения, которое удовлетворяет аксиоме 3), т.е. транзитивно, но не удовлетворяет аксиомам 1) и 2) (асимметрично и антирефлексивно) – «больше». Виды отношений Определение 66. Отношения, обладающие только некоторыми из трѐх свойств отношения эквивалентности называются отношениями порядка. 1. Рефлексивное транзитивное отношение называется отношением квазипорядка. 2. Рефлексивное антисимметричное транзитивное отношение называется отношением частичного порядка. 3. Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка. 4. Полное антисимметричное транзитивное отношение называется отношением линейного порядка. 5. Антирефлексивное асимметричное отношение называется отношением доминирования. Например, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше) – «строгий порядок». Определение 67. Пусть бинарное отношение описано множеством B  A  A  A2 , тогда матрицей 1, (i, j )  B, бинарного отношения называется матрица Q  ( xij ) такая что, xij   0, (i, j )  B. Пример. Пусть на множестве А = {а1, а2, а3, а4} задано бинарное отношение, которое описано множеством B  A  A  A2 , причем В = {( а1, а1), (а1, а2), (а1, а4), (а2, а2), (а2, а3), (а3, а3), (а3, а4)}. Записать матрицу бинарного отношения. Решение. 1 1 0 1    0 1 1 0 Q . 0 0 1 1    0 0 0 0   п 11. Функция. Композиция функций Определение 68. Бинарное отношение R, определенное на некотором множестве, называется функцией f, если каждому значению x отношения xfy соответствует лишь одно значение. 14 То есть если из ( x, y)  f и ( x, z )  f следует, что y  z . Поскольку каждому значению x в выражениях xfy и xfz соответствует одно и то же значение, то y и z совпадут, окажутся одними и теми же. Функциональное отношение однозначно, поскольку каждому значению x отношения xfy соответствует лишь одно-единственное значение y такое, что ( x, y)  f , но не наоборот. y  f (x) . Определение 69. Бинарное отношение f, определенное на некотором множестве, отличающееся тем, что в нѐм каждому значению х соответствует единственное значение у, и каждому значению у соответствует единственное значение х называется биекцией (одно-однозначное отношение). Определение 70. Функция f , для которой из равенства f(x) = f(y) следует, что x = y , называется взаимнооднозначной функцией. Если f – взаимнооднозначная функция, то обратное отношение f 1 тоже является функцией. Например, y  2 x – взаимнооднозначная функция, y  2x 2 – не является взаимнооднозначной. Определение 71. f отображает множество X на множество Y, если f – функция с областью определения Х и множеством значений Y. Определение 72. Всюду определенной функцией от n аргументов f(x1, x2,…, xn) на множестве Х называется всякая функция, у которой область определения совпадает с Xn. Частичной функцией от n аргументов на множестве Х называется всякая функция, областью определения которой служит какоенибудь подмножество Xn. Например, обычное деление – частичная функция от двух аргументов на множестве целых чисел (т.к. на нуль делить нельзя). Определение 73. Бинарной или двуместной операцией на множестве Х называется отображение f такое что X  X  X , которое каждой упорядоченной паре элементов (x, y), называемых операндами, принадлежащей прямому произведению X  X , ставит в соответствие некоторый элемент того же множества, называемый результатом. Бинарная операция – операция, принимающая два аргумента и возвращающая один результат. Определение 74. n- местной операцией или операцией с n аргументами на множестве Х называется функция, отображающая Xn в Х. Примеры. 1) Обычное сложение – бинарная (двуместная) операция на множестве натуральных чисел (складываются два числа – операнда, результат – сумма – одно число). 2) Обычное вычитание – бинарная операция на множестве вещественных целых чисел, но оно не является бинарное операцией на множестве натуральных чисел (2 – 5 <0). 3) Скалярное произведение векторов на плоскости – не бинарная операция, так как результат – не вектор. Определение 75. Если f и g – функции, то композиция f  g этих функций есть такая функция, что справедливо равенство: ( f  g )( x)  f ( g ( x)) , причем ( f  g )( x) определена тогда и только тогда, когда определены функции g (x) и f ( g ( x)) . Примеры. 1. Даны функции: g ( x)  x 2 , f ( x)  x  1. Найти ( f  g )( x) и ( g  f )( x) . Решение: ( f  g )( x)  x 2  1 , ( g  f )( x)  ( x  1)2 . 2. Пусть g ( x)   x для всех действительных х. f ( x)  x для всех x  0 . Найти область определения композиции ( f  g )( x) . Решение: ( f  g )( x)   x , следовательно, область определения: x  0 . 3. Указать операции, которые определены на множестве целых чисел Z: 1) a  b  a b , 2) a  b – 2 общее кратное элементов а и b, 3) a  b  a  b , 4) a  b  2(a  b) . 35  Z ; 2) операция определена на Z, Решение: 1) операция не определена на Z, например, 2 например, общее кратное элементов 2 и 3 равно 6, а 6  Z , и это справедливо для всех целых чисел; 15 3) операция определена на Z, например, 2  5  3  Z , и это справедливо для всех целых чисел; 4) операция определена на Z. § 2. Математическая логика Определение 1. Логика – анализ методов рассуждений. Рассмотрим два вывода: 1) Все люди смертны. Сократ – человек, следовательно, Сократ смертен. 2) Все кролики любят морковь. Ушастик – кролик, следовательно, Ушастик любит морковь. Оба вывода имеют одну и ту же форму: все А суть В, С есть А, следовательно, С есть В. Логик желает знать, вытекает ли истинность заключения из истинности посылок. Основная задача логика – систематическая формализация и каталогизация правильных способов рассуждений. Главная цель математической логики – дать точное и адекватное определение понятия «математическое доказательство». Определение 2. Алфавитом  называется любое непустое множество. Элементы этого множества называются символами алфавита.   a, b, c,... Определение 3. Словом в алфавите называется произвольная, конечная (возможно, пустая) последовательность символов из  . Определение 4. Произведением слов a и b называется слово ab. Предложение – произвольная конечная последовательность слов.   1  2  3 , Определение 5. Рассмотрим алфавит: где 1  A, B, C,..., 2  , ,,, , 3  (),. Символы из 1 называются переменными высказываниями или пропозициональными буквами. Символы из 2 называются логическими связками или пропозициональными связками. Символы из 3 (скобки, запятые) называются вспомогательными символами. п. 1. Высказывания (пропозициональные буквы) Истина и ложь – слова, которые называются значениями истинности. Определение 6. Высказывание – утвердительное предложение, про которое можно сказать истинно оно или ложно. Например, «идет дождь» – высказывание, «пойдем обедать» – не высказывание. Высказывание может быть выражено с помощью слов, а также с помощью математических, химических и других знаков. Не являются высказываниями 1) восклицательные, повелительные и вопросительные предложения («Какого цвета свитер?», «Пейте чай», «Стой!» и т.д.); 2) также определения (они устанавливают названия и понятия некоторого объекта, не могут быть истинными или ложными, они лишь фиксируют принятое использование терминов); 3) также предложения типа: «он сероглаз или x 2  4 x  3  0 » (не указано, о каком человеке идет речь, при каких х рассматривается неравенство; такие предложения с неизвестной переменной называются неопределенными высказываниями). Например, «некоторые люди – сероглазы» – высказывание, «для всех x  R справедливо неравенство x 2  4 x  3  0 » – высказывание, причем 1) – истинное, а 2) – ложное. Высказывания, которые можно разложить на части – сложные, нельзя – простые. Из высказываний путем соединения их различными способами можно составлять новые, более сложные высказывания. Иногда бывает удобнее представлять некоторые словесные выражения – высказывания, посредством логических символов, которые называются кванторами. Кванторы. Определение 7. Кванторы – логические символы или специальные обозначения для некоторых часто встречающихся выражений. Например: 1) Квантор общности –  – любой, каков бы ни был. x p(x) – для всех x истинно (или выполнимо) свойство p(x). 2) Квантор существования –  – существует. 16 x p(x) – найдутся (или существуют) x, обладающие свойством p(x). Пример 1. Дано высказывание: «Утверждение, что множество А есть часть множества В, означает, что все элементы из А являются элементами из В». Записать посредством кванторов. Решение. A  B  (a  A  a  B) . Пример 2. Дано высказывание: «Утверждение, что множество А не есть часть множества В, равносильно следующему: существует такой элемент из А, что он не принадлежит В». Записать посредством кванторов. Решение. A  B  (a  A  a  B) . Замечание. В основе математической логики лежит логика высказываний, в которой высказывания изучаются с помощью особого буквенного исчисления, называемого алгеброй логики. Определение 8. Алгебра логики – раздел математической логики, который изучает общие свойства выражений, составленных из высказываний с помощью логических операций. п. 2. Логические связки (логические операции или пропозициональные связки). Будем рассматривать только истинностно-функциональные комбинации высказываний, т.е. в которых истинность или ложность новых высказываний определяется истинностью или ложностью составляющих высказываний. Определение 9. Логические связки – функциональные или логические операции над высказываниями. Виды связок. 1)  – отрицание. А,  А – «не А». Другое обозначение: A – «не А». Замечание. Отрицание для кванторов. Рассмотрим утверждение: Для всех x существует y, такой, что для любых z и h выполняется свойство p(x, y, z, h). Запишем его посредством кванторов: x y z h p( x, y, z, h) . Правило для отрицания: меняем квантор на противоположный, а последнее утверждение заменяем отрицанием. В рассмотренном примере получаем: x y z h p( x, y, z, h) . Обычно для построения отрицания данного высказывания надо присоединить к сказанному частицу «не» или, если она уже есть, опустить ее. Например, для высказывания а – «Сейчас небо синее» отрицание будет ā – «Сейчас небо не синее». Отрицанием высказывания b – «Гремучая змея не имеет позвоночника» является высказывание b – «Гремучая змея имеет позвоночник». В математике отрицание высказывания, записанного с помощью тех или иных знаков, часто выражают, перечеркивая соответствующий знак или опуская перечеркивающую линию. Например, высказыванию а : (2 + 3 = 5) отвечает отрицание ā: (2 + 3 ¹ 5); высказыванию с: (а || b) отвечает отрицание c : (a || b). Иногда применяются другие обозначения: отрицанием высказывания a < b является a ≥ b или неравенство a < b истинно только в том случае, когда a ≥ b ложно. 2)  (другое обозначение & ) – «и» – конъюнкция. A  B или или A  B А & В – «А и В». Определение 10. Конъюнкт или конъюнкция двух переменных – выражение вида ( A  B) или их отрицание: (A  B) , ( A  B) . Пример. Высказывание «Диагонали любого ромба перпендикулярны и делят углы при вершинах ромба пополам» – является конъюнкцией. Это сложное высказывание, состоящее из двух простых, связанных союзом «и». Оба истинны, следовательно, истинным является и сложное высказывание, которое есть конъюнкция двух высказываний. 17 3)  – «или» – дизъюнкция. A  B – «А или В», хотя бы один из них. Определение 11. Дизъюнкт или дизъюнкция двух переменных – выражение вида ( A  B) или их отрицание: (A  B) , ( A  B) . Пример. Высказывание «Завтра на уроке математики будет контрольная или проверочная работа» – дизъюнкция, состоящая из двух высказываний: 1) «Завтра на уроке математики будет контрольная» и 2) «Завтра на уроке математики будет проверочная работа», связанных союзом «или». Определение 12. Дизъюнктивная нормальная форма – это дизъюнкция нескольких конъюнктов. Например: f ( A, B)  ( A  B)  (A  B) – А и В находятся в дизъюнктивной нормальной форме. Определение 12/. Конъюнктивная нормальная форма – это конъюнкция нескольких дизъюнктов. Например: f ( A, B)  ( A  B)  (A  B) – А и В находятся в конъюнктивной нормальной форме. 4)  (другие обозначения  и  ) – «если одно, то и другое» – импликация. A  B – «если А, то и В». Пример. Высказывание «Если  АВС равносторонний, то A  B  C » является импликацией высказываний А: (  АВС – равносторонний) и В: ( A  B  C ). В импликации A  B высказывание А называют условием (или посылкой), а В – заключением (или следствием). В математике импликация встречается очень часто. 5)  (другие обозначения  , ~ ) – «тогда и только тогда, когда» – эквивалентность или эквиваленция. A  B – « А тогда и только тогда, когда В» Пример. Высказывание «Для того чтобы некоторый параллелограмм был ромбом, необходимо и достаточно, чтобы его диагонали были взаимно перпендикулярны» является эквивалентностью высказываний А: (Некоторый параллелограмм – ромб) и В: (Диагонали некоторого параллелограмма взаимно перпендикулярны). Формулировка этой теоремы заключает в себе две импликации: ( A  B) и ( B  A) . Эквивалентность играет важную роль в математических доказательствах. Многие теоремы формулируются в форме необходимых и достаточных условий, т.е. в форме эквивалентности. 6)  – симметрическая разность AB – либо А обладает каким-нибудь свойством f, либо В обладает каким-нибудь свойством f, но не оба вместе. Пример. Записать свойства бинарных отношений при помощи логических связок. Решение. 1. Рефлексивность: a  A (aRa ) . (если (a, a)  R для всех a  A ) 2. Антирефлексивность: a  A (aRa) . 3. Симметричность: a, b  A (aRb  bRa) . 4. Антисимметричность: a, b  A (aRb  bRa  a  b) . 5. Асимметричность: a, b  A (aRb  (bRa)) . 6. Транзитивность: a, b, c  A (aRb  bRc  aRc) Определение 13. Формула алгебры логики – простые высказывания или сложные, полученные из простых посредством применения конечного числа логических операций. Свойства логических операций (основные законы алгебры) 1. Коммутативность. A  B  B  A, 18 A  B  B  A, A  B  B  A. 2. Ассоциативность. A  ( B  C )  ( A  B)  C , A  ( B  C)  ( A  B)  C , A  ( B  C )  ( A  B)  C . Замечание. Свойства 1,2 не выполняются для импликации «  », т.е. A  ( B  C)  ( A  B)  C . 3. Дистрибутивность. A  ( B  C )  ( A  B)  ( A  C ) , A  ( B  C )  ( A  B)  ( A  C ) , A  ( B  C )  ( A  B)  ( A  C ) , ( A  B)  C  ( A  B)  ( B  C) . 4. Отрицание. ( A  B)  A  B , ( A  B)  A  B , A  A , ( A  B)  A  B . 5. Импликация. A  B  ( A  B) , A  B  A  B , A  B  (B)  (A) . A B  B  A, X  x1, x2 ,..., xn   множество или предметная область, Определение 14. Пусть x1 , x2 ,..., xn  предметные переменные. n-местным предикатом, определенным на области X, называют отображение множества Х во множество высказываний. n-местный предикат – это связное повествовательное предложение, содержащее n переменных и обладающее следующим свойством: при фиксации всех переменных о нем (предложении) можно сказать ложно оно или истинно. Предикат – синоним слова «отношение», т.е. это функция, утверждающая истину или ложь. Обозначение: Р(x1,x2,…xn) или f(x1,x2,…xn). Пример 1. а) f ( x) : x – человек – одноместный предикат, b) f ( x) : x  90 – одноместный предикат. f (100)  истинно, f (10)  ложно. c) P( x)  x 2  1, x  R – одноместный предикат, при всех х ложный. d) предикат равенства f ( x, y) : x  y . При f (1, 4)  ложно, f (2, 2)  истинно. Это двуместный предикат. е) P( x, y) : натуральное число х делится без остатка на натуральное число y – двуместный предикат на множестве натуральных чисел. P(4, 2)  истинно, P(3, 5)  ложно. Пример 2. Даны предикаты: f ( x) : x – человек; c( x) : x – машина; D( x, y) : x ездит на y. Записать утверждения: а) никакой человек не является машиной, b) существует человек, с) только люди водят машины. Решение. а) никакой человек не является машиной: (x : f ( x)  c( x)) . b) существует человек: x : f ( x) . с) только люди водят машины: x, y  D( x, y)  f ( x) . Истинность высказываний. Определение 15 . Высказывание (A) истинно, если А ложно. 19 Определение 16. Высказывание ( A  B) – конъюнкция – истинно, если А и В оба истинны, и ложно в противном случае. Например: 1) высказывание ( (2+2=5)   -рациональное число) – ложное, т.к. первое высказывание ложное: 2  2  5 ; 2) высказывание «Число 12 четное и простое» является ложным. Оно есть конъюнкция двух высказываний А: (число 12 четное) и В: (число 12 простое). Первое высказывание истинно, а второе ложно, поэтому ложным является также и их конъюнкция; 3) истинной конъюнкцией высказываний является двойное неравенство 3 < 6 < 7. Такое неравенство считают истинным лишь в том случае, когда истинны оба входящие в него неравенства, в нашем случае это 3 < 6 и 6 < 7. Определение 17. Высказывание ( A  B) – дизъюнкция – истинно, если хотя бы одно из высказываний А и В истинно. Например: 1) высказывание ( (2+2=5)   -рациональное число) – истинное, т.к. второе высказывание истинное:  -рациональное число; 2) истинной дизъюнкцией высказываний является нестрогое неравенство, например, 3 ≤ 7. Такое неравенство считается истинным, если истинно хотя бы одно из входящих в него высказываний 3 < 7 и 3 = 7; 3) истинной дизъюнкцией является высказывание «Данный четырехугольник является прямоугольником или ромбом». Здесь могут оказаться истинными оба высказывания (если четырехугольник является квадратом). Определение 18. Высказывание ( A  B) – импликация – ложно, если А – истинно, а В – ложно, и истинно во всех других случаях. Например: Предварительно обозначим: истинно – и, ложно– л. а) (1+1 = 2)  (Париж – столица Франции). Высказывание истинно: и  и. b) (1+1  2)  (Париж – столица Франции). Высказывание истинно: л  и. с) (1+1  2)  (Рим – столица Франции). Высказывание истинно: л  л. d) (1+1 = 2)  (Рим – столица Франции). Высказывание ложно: и  л. Определение 19. Высказывание ( A  B) истинно, когда А и В оба истинны или оба ложны. Например, высказывание «Числовой ряд  u n 1 n расходится тогда и только тогда, когда его общий член un при n   отличен от нуля» является истиной эквивалентностью высказываний А: (Числовой ряд  u n 1 n расходится) и В: (Общий член un числового ряда при n   отличен от нуля). Формулировка этой теоремы заключает в себе две импликации: ( A  B) и ( B  A) . Вывод: Всякое высказывание, построенное при помощи логических связок, имеет некоторое истинностное значение, зависящее от истинностных значений составляющих высказываний. п. 3. Таблицы истинности. Определение 20. Пропозициональная форма или формула алгебры высказываний – это выражение, построенное из пропозициональных переменных (высказываний) с помощью логических связок, точнее 1) все высказывания – есть формула, 2) если А и В – формулы, то (  А), ( A  B ), ( A  B ), ( A  B ), ( A  B ), ( AB ) – тоже формулы, 3) только те выражения являются формулами, для которых это следует из 1) и 2). Всякая формула алгебры определяет некоторую истинностную функцию, которая, в свою очередь, определена на множестве {и, л}. Графически формула (т.к. это функция) может быть представлена истинностной таблицей или таблицей истинности для этой формулы. Определение 21. Таблица истинности – распределение пропозициональных букв (высказываний), входящих в формулу. истинностных значений Построение таблицы истинности: под всеми вхождениями каждого из высказываний подписываем соответствующие истинностные значения. Каждая строка таблицы содержит 20 некоторое распределение истинностных значений для букв и соответствующие истинностные значения, принимаемые различными формулами, которые возникают при построении окончательной формулы. Примеры. Пример 1. Таблица истинности для отрицания. (См. определение 15.) А и л А ( A ) л и Пример 2. Таблица истинности для конъюнкции. (См. определение 16.) А и л и л В и и л л A  B (А & В) и л л л Пример 3. Таблица истинности для дизъюнкции. (См. определение 17.) А и л и л В и и л л A B и и и л Пример 4. Таблица истинности для импликации. (См. определение 18.) А и л и л В и и л л A  B ( A  B ) ( A  B) и и л и Пример 5. Таблица истинности для эквивалентности. (См. определение 19.) А и л и л В и и л л A B ( A B) и л л и Определение 22. Внешне различные выражения называются равносильными ( A  B или А = В), если их таблицы истинности одинаковы. Например: 1) A  B  A  B и A  B  A  B . 2) A  B  A  B Основные равносильности 1) A  A  A , 2) A  A  A , 3) A 1  A , 4) A 1  A , 5) A  0  0 , 6) A  0  A ,7) A  A  0 , 8) A  A  1 , 9) A  A , 10) A  ( B  A)  A , 11) A  ( B  A)  A . Пример 6. Доказать, что операция эквивалентности выражению (  ( ( A  B)  (A  B) )). Решение. A  B равносильна логическому 21 Построим таблицу истинности функции (  ( ( A  B)  (A  B) )): А л л и и А и и л л В л и л и В и л и л A  B л л и л (A)  B л и л л ( A  B)  (A  B) л и и л  ( ( A  B)  (A  B) ) и л л и Таблицы истинности совпадают, то есть значения в последних столбцах одинаковы, следовательно, A  B = ((( A  B)  (A  B)) . Пример 7. Построить таблицу истинности для формулы: (( A  B)  ((A)  B)) . Решение. А В A  B  А (A)  B ( A  B)  ((A)  B) и и и л л л л и л и и и и л л л л и л л и и л л Замечания. 1. Составление таблицы истинности можно незначительно сократить. Выпишем формулу, для которой надо составить истинностную таблицу. Для каждого распределения истинностных значений пропозициональных букв, входящих в данную формулу, под всеми вхождениями каждой из этих букв подпишем соответствующие истинностные значения. Затем, шаг за шагом, под каждой связкой будем выписывать истинностные значения той составляющей формулы, для которой эта связка – главная, т.е. при построении формулы применяется последней. Например, построим сокращенную таблицу для формулы примера 7. A B и и и л л и и л л л и л  л и и л А л и и л л и и л  л и л л В и и л л 2. В приведенных примерах формулы содержат две буквы: А и В. Если в формуле имеется n различных букв, то тогда возможны 2n различных распределений истинностных значений для букв, следовательно, таблица истинности для такой формулы содержит 2n строк. Пример 8. Построить таблицу истинности для формулы: (((A)  B)  C ) . Решение. Таблица истинности для такой формулы содержит 23 = 8 (n = 3 буквы) строк: А и л и л и л и л В и и л л и и л л С и и и и л л л л А л л л и л и л и (A)  B и и л и и и л и ((A)  B)  C и и и и л л и л 22 Определение 23. Пропозициональная формула, которая истинна, не зависимо от того, какие значения принимают встречающиеся в ней пропозициональные буквы (высказывания), называется тавтологией. Иначе, высказывание – тавтология, если оно истинно. Замечание. Формула является тавтологией тогда и только тогда, когда соответствующая истинностная функция принимает только значение «и» (истинно) или, что то же самое, если в ее таблице истинности столбец под самой пропозициональной формулой состоит только из букв «и». Определение 24. Если импликация A  B является тавтологией, то говорят, что А логически влечет В. Если эквивалентность A  B – тавтология, то говорят, что А и В логически эквивалентны. Примеры. Пример 1. Доказать, что тавтологией является «закон исключения третьего»: A  (A) . Доказательство. Построим таблицу истинности для формулы A  (A) : А  А A  (A) и л и л и и Столбец под самой пропозициональной формулой состоит только из букв «и», следовательно, формула – тавтология. (что и треб. доказать) Пример 2. Доказать или опровергнуть: ( A  B) логически влечет ( A  B) . Решение. По определению 24, если докажем, что формула ( A  B)  ( A  B) является тавтологией, то докажем и истинность утверждения: ( A  B) логически влечет ( A  B) . Построим таблицу истинности для формулы ( A  B)  ( A  B) : А и и л л В и л и л A B и л л и A B и л и и ( A  B )  ( A  B) и и и и Столбец под самой пропозициональной формулой состоит только из букв «и», следовательно, формула – тавтология. (что и треб. доказать) Определение 25. Формула, которая ложна при всех возможных истинностных значениях ее пропозициональных букв, называется противоречием. Замечание. Формула является противоречием тогда и только тогда, когда соответствующая истинностная функция принимает только значение «л» (ложно) или, что то же самое, если в ее таблице истинности столбец под самой пропозициональной формулой состоит только из букв «л». Пример. Доказать, что формула A  (A) – противоречие. Доказательство. Построим таблицу истинности для формулы A  (A) : А  А A  (A) и л л л и л Столбец под самой пропозициональной формулой состоит только из букв «л», следовательно, формула – противоречие. (что и треб. доказать) 23 Теорема 1. Формула Д является тавтологией тогда и только тогда, когда (  Д) есть противоречие. (без доказательства) Замечания. 1. Противоречие и тавтология связаны друг с другом: отрицание противоречия есть тавтология и наоборот. 2. Связь между понятиями равносильности и эквивалентности: если формулы А и В равносильны ( А = В), то формула A  B – тавтология и обратно, если A  B – тавтология, то формулы А и В равносильны. Определение 26. Высказывание (в каком – нибудь естественном языке, вроде русского, или в каком-то искусственном языке), которое получается из какой-либо тавтологии посредством подстановки высказываний вместо пропозициональных букв, при условии, что вхождения одной и той же буквы замещаются одним и тем же высказыванием, называется логически истинным. Пример. Рассмотрим предложение русского языка: « Если идет дождь или идет снег, и не идет снег, то идет дождь», которое можно получить подстановкой в тавтологию: (( A  B)  (B))  A . Задание: доказать самостоятельно, что это тавтология. Определение 27. Высказывание, которое можно получить с помощью подстановки в противоречие, называется логически ложным. Замечание. Существуют и такие виды логических рассуждений, которые не могут быть обоснованы в рамках исчисления высказываний. Корректность этих умозаключений покоится не только на истинностно–функциональных отношениях, но и на внутренней структуре самих предложений. Например, утверждение: « Всякий друг Мартина есть друг Джона; Питер не есть друг Джона, следовательно, Питер не есть друг Мартина». Запишем это утверждение, предварительно обозначив через: m – Мартин, j – Джон, p – Питер, f(x,y) – предикат: f(x,y) : x есть друг y. Тогда x( f ( x, m)  f ( x, j )) , f ( p, j )  f ( p, m) . f ( p, j ) Иногда записывают в виде: x( f ( x, m)  f ( x, j )) . f ( p, m) п. 4. Булевы функции Названы по имени англ. математика Джорджа Буля (1815-1864), младшая дочь которого Этель Лилиан Войнич – автор романа «Овод». Булева функция одной логической переменной . Рассмотрим множество D, состоящее всего из двух элементов. Для простоты и определенности D = {0, 1}. Будем рассматривать числовые функции f(x), определенные на D, но не все, а те, которые принимают только два значения: 0 и 1. Определение 28. Независимая переменная x, которая принимает всего два значения, называется двоичной, или логической переменной. Определение 29. Функция логической переменной, принимающая только два значения, называется булевой функцией одной логической переменной (БФОЛП) или просто булевой функцией. Для БФОЛП можно построить таблицы истинности. (и – 1, л – 0). Примеры. Существуют только четыре булевы функции одной логической переменной: 1) тождественная функция: f(x) = x 2) отрицание: x – не x. 24 3) и 4) функции, отображающие множество D = {0, 1} в себя. Это постоянные f ( x)  1, f ( x)  0. Построим их таблицы: 1) x f(x) = x 1 1 2) x f ( x)  x 1 1 3) x f(x) = 1 1 1 1 4) x f(x) = 0 1 Булева функция двух логических переменных. Рассмотрим две логические переменные x1 и x2: x1 = {0, 1}, x2 = {0, 1}. Рассмотрим функцию f(x1, x2), которая каждому слову (x1 x2) ставит в соответствие некоторое число. Такую функцию можно назвать числовой функцией двух логических переменных. Определение 30. Функция двух логических переменных, принимающая только два значения, называется булевой функцией двух логических переменных (БФДЛП). Областью определения БФДЛП является множество двухбуквенных слов из алфавита {0, 1}: 00, 01, 10, 11. Если принять эти слова за координаты точек на плоскости (x1Оx2), то БФДЛП можем считать заданной на множестве вершин единичного квадрата, например, f(x1, x2) может быть равна 1 во всех вершинах, кроме вершины 01, а в этой вершине обращаться в нуль. Можно построить 16 различных булевых функций двух логических переменных, например, дизъюнкция ( x1  x2 ), конъюнкция ( x1  x2 ), импликация ( x1  x2 ), эквиваленция ( x1 ~ x2 ), симметрическая разность ( x1x2 ). Для БФДЛП можно построить таблицы истинности. (и – 1, л – 0). Так как булевы функции принимают только два значения, то они сами могут служить логическими переменными и соединяться связками: ,, , , ~. В итоге получим композиции. Примеры. Пример 1. Таблица для конъюнкции. x1 x2 x1  x2 0 0 1 0 0 1 1 1 1 Пример 2. Таблица для композиции f(x1, x2) = x1  x2 x1 x2 x1 x1  x2 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 Определение 31 (общее определение) Булева функция – функция f(x1, x2, …, xn), которая по любому набору логических констант выдает логическую константу. 25 Теорема 2. Любая булева функция n переменных может быть задана с помощью композиции, содержащей конечное число только трех связок: дизъюнкции, конъюнкции и отрицания. § 3. Графы Введение. Любой из нас, конечно, прав, Найдя без проволочек, Что он … обыкновенный граф Из палочек и точек. Понятие «граф» – одно из самых простых и самых употребительных понятий в математике и других науках, хотя теория графов зародилась чуть ли не 250 лет тому назад в ходе решения головоломки, и тогда же появились первые теоремы о графах, доказанные самим Леонардом Эйлером. Долгие годы эта теория не находила широких приложений и была известна в основном как средство решения головоломок, логических или развлекательных задач, задач олимпиадного типа или на смекалку. При решении таких задач удобно составлять таблицы, изображать объекты точками, соединять их отрезками или стрелками, подмечать закономерности из полученных рисунков, выполнять над точками и отрезками операции, не похожие на алгебраические и геометрические. И в обычной жизни очень часто мы рисуем на бумаге точки, изображающие химические вещества, V1 Р V2 населенные пункты, генеалогические деревья и А В соединяем эти точки линиями и стрелками, означающими некоторые отношения между S рассматриваемыми объектами. Такие схемы встречаются всюду под различными названиями: электрические цепи (в физике), карты, лабиринты, диаграммы, генеалогические деревья, диаграммы организации (в экономике), социограммы (в психологии) и т.д. В 1936 году Д. Кѐниг предложил называть такие схемы графами и систематически изучать их свойства. Итак, как отдельная математическая дисциплина теория графов была представлена лишь в 30 – е годы ХХ столетия в связи с тем, что в обиход вошли так называемые «большие системы», т.е. системы с большим числом объектов, связанных между собой разнообразными соотношениями: сети железных дорог и авиалиний, телефонные узлы на много тысяч абонентов, системы заводов – потребителей и предприятий – поставщиков, радиосхемы, большие молекулы и т.д. и т. п. Стало ясно, что разобраться в функционировании таких систем невозможно без изучения их конструкции, их структуры. Здесь и пригодилась теория графов. В середине XX века задачи теории графов стали возникать также и в чистой математике (в алгебре, топологии, теории множеств). Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной. Ныне она переживает эпоху бурного возрождения. Графы используются: 1) в теории планирования и управления, 2) в теории расписаний, 3) в социологии, 4) в математической лингвистике, 5) экономике, 6) биологии, 7) химии, 8) медицине, 9) в областях прикладной математики таких, как теория автоматов, электроника, 10) в решении вероятностных и комбинаторных задач и т.д. Наиболее близки к графам – топология и комбинаторика. А D В Рис. 1 C Хронологически первой в теории графов считается задача о семи кенигсбергских мостах, которую решил Эйлер. Она состоит в следующем. Парк города Кенигсберга был расположен на обоих берегах реки Прегель и на двух островах. Острова с берегами и друг с другом были соединены семью мостами так, как на рис. 1. Любимой забавой горожан были поиски такого маршрута, который 26 оканчивался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз. Возможен ли вообще такой маршрут? Для удобства решения составили схему или диаграмму. Части А суши (оба берега и острова) обозначили точками А, В, С, D, а пути их соединяющие и проходящие по мостам, изобразим линиями, соединяющими эти точки. (Рис. 2) Такая схема содержит всю D необходимую информацию о рассматриваемой ситуации и не содержит В ничего лишнего. Глядя на нее, можем заключить только, что четыре объекта – А, В, С, D – попарно как-то связаны между собой ( в данном случае мостами), причем А с В и В с С соединены двойной связью, а D Рис. 2 С с каждым из объектов А, В и С – одинарной. Точки А, В, С, D – вершины, соединяющие их линии – ребра диаграммы. Задача будет решена в ходе работы над схемой рисунка 2. (показано позднее) Очевидно, что подобными схемами можно описать самые различные объекты и ситуации. Например, вершинами могут быть атомы в молекуле, а ребрами – связи между ними. Точно так же можно рассмотреть множество людей и соединить их попарно на схеме линиями в том случае, если они знакомы, или если они родственники. Существуют схемы метрополитена, железных или шоссейных дорог, планы выставок и т.д., словом, схемы и планы без указания масштаба, показывающие лишь связи между принадлежащими объектами, состоящие из вершин и ребер, однако с ними трудно проделывать формальные операции, следовательно, диаграммы из точек и линий надо заменить какими-то более формализованными моделями. Так пришли к графам. п. 1. Основные понятия. Определение 1. Будем говорить, что задан граф G, если задано конечное множество V  a, b, c,... и некоторое множество W неупорядоченных пар различных элементов из V: (a, b), (a, c), ..., (b, u), (v, u). Таким образом, граф – это упорядоченная пара G  V ,W . Элементы множества V называют вершинами графа, а заданные пары этих элементов – ребрами. Множество ребер W, соединяющих элементы множества V, отображают это множество само в себя. Замечание. Определение графа совпадает с определением отношения на множестве. Граф – бинарное отношение на множестве V , т.е. подмножество R множества V  V (множество всех упорядоченных пар вида ( xi , x j ) , где xi , x j  V ). В соответствие каждому графу можно поставить некоторую схему на плоскости, если вершины графа изобразить точками, или кружочками, или квадратиками, а ребра, соединяющие некоторые вершины, – отрезками прямых или кривых линий. Эту схему называют диаграммой графа, геометрическим графом или, для краткости, просто графом. Отсюда, определение 1 можно переписать в виде: Определение 1’. Граф представляет собой непустое множество точек и множество отрезков прямых или кривых линий, оба конца которых принадлежат заданному множеству. Граф с p вершинами и q ребрами называется (p, q) – графом. Обозначения: граф – G или Г; вершины – заглавными различными буквами А, В, С …, или маленькими различными буквами a, b, c... , или одинаковыми буквами с индексами х1, х2,... или числами 1, 2, 3…; ребра – (А, В) или a, u , или (a, b) , или (х1, х2), или (1, 2) (отрезки, соединяющие вершины), или просто u1, u2…(первое ребро, второе и т.д.). Определение 2. Петля – это ребро, концы которого совпадают. Вершины, которые не соединены ребрами, называются изолированными. Задание графа (1 способ) Задать граф можно путем перечисления ребер графа с указанием концов и добавлением списка изолированных вершин, например, граф с множеством вершин V  a, b, c, d  и списком дуг W  (a, d ); (a, c); (b, b), (b, d ), (c, a). 27 Пример. Построить графы: а) Г = ( A, D), ( D, C ), (C, B), b) G  ( A, D), ( B, C ), (C, D), ( B, B). Построение. а) А В С D А b) В С D Один и тот же граф можно изобразить по-разному. В 1) С В А С А D А b 2) Примеры В D Это один и тот же граф D b c a С Это тоже один и тот же граф C a d d Замечание 1. Не всегда точка пересечения ребер принимается за вершину, например, на рис. А точка А – не вершина. Замечание 2. Диаграмма графа наглядно иллюстрирует его свойства. Но не надо отождествлять эти понятия прежде всего потому, что одному и тому же графу можно поставить в соответствие внешне различные диаграммы. Например, графу G  V ,W , где V  a, b, c, d , e, W  (b, a), (b, e), (b, c), (d , c), (d , e), можно поставить в соответствие диаграмму рис.3. Здесь по ошибке точку пересечения ребер (b,e) (c,d) можно принять за вершину, которой она не является. Этот же граф можно изобразить на рис. 4, 5, 6, на которых ребра пересекаются только в вершинах. a b a d b d e c c b e Рис. 3 c e c b e a d Рис. 4 d Рис. 5 a Рис. 6 Определение 3. Два геометрических графа называются изоморфными, если они являются диаграммами одного и того же графа (каждой паре вершин а, b графа G, соединенных ребром соответствует пара вершин a, b графа G так же соединенных ребром). (5, 5) – графы изоморфны (4, 3) – графы неизоморфны Определение 4. Мультиграфами называются графы, у которых пара вершин соединена двумя или несколькими ребрами. (В дальнейшем будем называть просто графами) 28 Пример: мультиграф кенигсбергских мостов Определение 5. Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром. Замечание. В полном графе каждая его вершина принадлежит одному и тому же числу ребер. Определение 6. Если ребро (a, b) соединяет вершины a и b , то говорят, что оно инцидентно вершине а и вершине b. Эти вершины называются смежными и инцидентными ребру (a, b) . Два ребра называются смежными, если они инцидентны одной вершине. Определение 7. Матрицей смежности называется квадратная матрица A  (aij )mm , строки и столбцы которой соответствуют вершинам графа, причем неотрицательный элемент aij равен числу ребер, идущих из вершины xi в вершину xj. Если исходящих дуг нет, то aij  0 . Матрица смежности всегда симметрична. Пример. Составить матрицу смежности графа 2 3 4 1 Решение. Граф имеет 4 вершины, следовательно, матрица смежности имеет размерность 4  4 . Наличие ребер: 1 в 1 – нет ребра, 1 в 2 – есть ребро, 1 в 3 – нет ребра, 1 в 4 – есть ребро. Следовательно, первая строка имеет вид: 0 1 0 1. Вершина 2 соединена только с вершиной 1, следовательно, вторая строка имеет вид: 1 0 0 0. Вершина три – изолированная, следовательно, третья строка – нулевая. Вершина 4 соединена ребром с вершиной 1 и дугой с самой собой, следовательно, четвертая строка: 1 0 0 1. 0 1 0 1   1 0 0 0 Тогда матрица смежности имеет вид: A   . 0 0 0 0   1 0 0 1   Определение 8. Матрицей инцидентности или инциденций называется прямоугольная матрица B  (bij )mn , строки которой соответствуют вершинам графа, а столбцы – ребрам. Если вершина xi и ребро uj инцидентны, то bij  1 , и bij  0 в противном случае. Для ее составления удобно пронумеровать ребра, обозначив их как u1, …, un. Пример. Составить матрицу инциденции для графа. Решение. Обозначим ребра как u1, u2, u3, u4. 2 u1 u2 u3 1 4 3 u4 u2 1 1 0 0   1 0 0 0 Матрица имеет вид: A   . 0 1 1 0   0 0 1 1   1. Замечание. Граф может быть задан не только перечислением ребер графа с указанием концов и добавлением списка изолированных вершин, но и матрицей смежности и матрицей инцидентности (инциденций) Определение 9. Граф Г называется подграфом графа G, если все вершины и ребра графа Г принадлежат графу G. 29 Определение 10. Дополнением графа G называется граф G с теми же вершинами, что и у графа G и с теми и только с теми ребрами, которые необходимо добавить к G , чтобы получился полный граф. Пример. G G Определение 11 . Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Вершина называется нечетной, если ее степень – нечетное число. Вершина называется четной, если ее степень число четное. Петля добавляет 2 в степень вершины. Пример. А Степень А =1 Степень В =2 Степень Е = 0 Степень С = 3 В Е D С Замечание. Степень каждой вершины полного графа на единицу меньше числа его вершин. Пример. Рассмотрим задачу: Как можно пройти по ребрам графа, изображенного на рисунке, из вершины А1 в вершину А5? А2 А1 А4 А3 А5 Решение. Запишем, как можно пройти: 1) (А1А4), (А4А5). 2) (А1А2), (А2А4), (А4А5). 3) (А1А4), (А4А2), (А2А1), (А1А4), (А4А5). 4) (А1А2), (А2 А4), (А4 А3), (А3А1), (А1А4), (А4А5) и другие… В одних ребра повторяются, в других – не повторяются. Но не всякую последовательность ребер, ведущих из А1 в А5 называют путем из А1 в А5. Определение 12. Маршрутом от А1 до Аn в графе называется чередующаяся последовательность вершин и инцидентных им ребер, т.е. такая последовательность ребер, ведущая от А1 до Аn, в которой каждые два соседние ребра имеют общую вершину. Определение 13. Маршрут называется путем или цепью, если все его ребра различны, т.е. никакое ребро не встречается более одного раза. В примере все даны маршруты, при этом 1) и 2) – пути, а 3) и 4) – не пути. Определение 14. Путь называется простой цепью или простым путем, если все его вершины (за исключением, может быть, первой и последней) различны. (Т.е. путь не проходит ни через одну из вершин графа более одного раза). 30 c d abdbe –маршрут, но не цепь, abcdbe – цепь, но не простая а b e abe – простая цепь Определение 15. Цепь, в которой начальная и конечная вершины совпадают, называется циклом. Если при этом цепь – простая, то она называется простым циклом. В примере acbdeba – цикл, но не простой; acdeba – простой цикл. Задача. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания? Решение. Каждого из компании изобразим на рисунке кружком. Если двое знакомы, соединим соответствующие кружки отрезком. Из рассматриваемой компании нельзя выделить ни четырехугольник, ни треугольник, поскольку тогда условие задачи будет нарушено, т.е. схема единственна. Данный граф – цикл. Определение 16. Если все вершины графа имеют одну и ту же степень r, то граф называется однородным графом степени r. Например, простой цикл является однородным графом степени 2. Теорема 1. ( Первая теорема теории графов. Доказана Эйлером.) p Сумма степеней вершин (p, q) – графа равна удвоенному числу его ребер:   ( A )  2q . i 1 i Определение 17. Длиной маршрута называется число ребер в нем, при этом каждое ребро считается столько раз, сколько оно встречается в данном пути. Длиной пути называется число ребер пути. Длиной цикла называется число ребер цикла. Определение 18. Две вершины графа А и В называются связными, если существует путь с концами А и В. Определение 19. Граф называется связным, если каждые две вершины его связные, иначе, если любая пара его вершин соединяется цепью. Граф называется несвязным, если хотя бы две вершины несвязные. Если граф не связан, то его можно разбить на подграфы так, что все вершины в подграфе будут связаны, а вершины из различных подграфов не связаны. Такие подграфы называются компонентами связности графа. Определение 20. Максимально возможный связный подграф графа G называется компонентой графа G. Несвязный граф имеет по крайней мере две компоненты. Определение 21. Ребро (А,В) называется мостом графа G, если в графе, полученном после удаления из графа G ребра (А,В) вершины А и В оказываются несвязными. А А В В 31 п. 2. Изображение одного и того же графа. Один и тот же граф может выглядеть на рисунке по-разному. Необходимое и достаточное условие соответствия двух рисунков одному и тому же графу: между вершинами на рисунках должно существовать взаимно однозначное соответствие, при котором две вершины графа на первом рисунке соединены ребром, если соединена ребром соответствующая пара вершин графа на втором рисунке и наоборот. А Примеры. Один ли граф изображен на этих рисунках? В В С 1. Вершины одинаково обозначены, имеют одинаковые степени, следовательно, на рисунке изображен один и тот же граф. С D Е А Е D 2. Для того, чтобы понять, один ли граф изображен на этом рисунке, обозначим вершины на обоих графах буквами и посчитаем количество вершин и ребер. Решение. С Для графа а): степень вершины А = 2, степень Е = 2, степень В = 3, степень D = 3, степень С = 2. Граф имеет 5 вершин, 6 ребер. Для графа b): степень вершины А = 2, степень Е = 2, степень В = 3, степень D = 3, степень С = 2. Граф имеет 5 вершин, 6 ребер. Вершины на рис. b) обозначены в соответствии с рис. а). Ответ: Это один и тот же граф. А А Е D А В D С А Е а) b) В 3. На этом рисунке изображены два разные графа, так как у первого графа только две вершины А и В имеют степень равную 2. Во втором графе таких вершин больше. В п. 3 Деревья. Определение 22. Всякий связный граф, не имеющий циклов, называется деревом. Несвязный граф, каждая компонента которого является деревом, т.е. представляющий собой объединение деревьев, называется лесом. d а c b f g e 32 Определение 23. Вершина называется изолированной, если степень ее равна нулю. Если степень вершины дерева равна единице, то она называется висячей вершиной. В примере висячими являются вершины a, b, c, d, e, f, g. Дерево с р вершинами содержит р –1 ребер. Многие графы, употребляемые в приложениях, являются деревьями. Например, графы всевозможных сортировок и классификаций. Корреспонденцию, пришедшую в страну, сортируют сначала по городам. Затем, в каждом городе – по отделениям связи, там – по участкам и т.д. Подобно этому живые организмы классифицируют сначала по типам, внутри типа – по классам, затем – по порядкам и т.д. Деревьями являются и всевозможные схемы идентификаций, например, в аналитической химии при качественном анализе пользуются деревом, вершинами которого являются некоторые стандартные тестовые реакции. Выбор ребра, по которому надо двигаться из данной вершины, определяется поведением исследуемого вещества в соответствующей реакции (выпадение в осадок, помутнение и т.п.). В физиологии рассматривают трахеобронхиальное дерево, вершинами которого являются участки раздвоения дыхательных путей, а ребрами – сами эти пути. Наконец, деревьями являются всевозможные схемы происхождения: дерево языков, дерево происхождения видов, фамильное дерево и т.д. Задача. Лист бумаги Плюшкин разрезает на три части. Некоторые из полученных листов он так же разрезает на три части. Несколько новых листиков он вновь разрезает на три более мелкие части и т.д. Сколько Плюшкин получает листиков бумаги, если разрезает k листов? Решение. Листы бумаги обозначим на рисунке кружками. Кружки, соответствующие листам, которые разрезаются, будут белыми крупными, остальные нарисуем маленькими черными. Рис. 8 Рис. 7. Рисунок 7 помогает увидеть, что при разрезании одного листка на три части, число листков увеличивается на два. Если же разрезано k листов, то образовалось (1+2 k) листов (рис. 8). На этом рисунке показано 5 разрезаний. п. 4. Эйлеровы графы. Мы уже говорили, что исторически теория графов (как и топология) зародилась при решении Эйлером головоломок, в которых требуется вычертить на плоскости росчерком замкнутые кривые, обводя каждый участок в точности один раз. Определение 24. Эйлеровым путем в графе называется путь, содержащий все ребра графа. Определение 25. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Определение 26. Граф, обладающий эйлеровым циклом, называется эйлеровым графом. Теорема 2. Если граф обладает эйлеровым циклом, то он связный. 33 Примеры эйлеровых графов: 1) план выставки, если экспонаты расположены по обеим сторонам залов, т.е. можно составить такой замкнутый маршрут, что по каждому залу посетитель сможет пройти в точности два раза – по одному с каждой стороны в разных направлениях. 2) Любой город можно обойти, пройдя по каждой улице ровно два раза – по одному в каждом направлении. 3) На рисунке изображена схема зоопарка. Вершины графа – вход, выход, перекрестки, повороты, тупики. Ребра – дорожки, вдоль которых расположены клетки. Найдите маршрут, по которому экскурсовод мог бы провести посетителей, показав им всех зверей и не проходя более одного раза ни одного участка пути. вход выход Решение. вход выход Замечание. Способ обходить все ребра графа можно использовать, например, для отыскания пути, позволяющего выбраться из лабиринта. Если известно, что у лабиринта все «стенки» связаны друг с другом, т.е. нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт всегда можно обойти весь, касаясь стенки одной рукой, например, правой. Существует правило Тарри (французский математик) – правило обхода любого лабиринта – при обходе лабиринта следует, попадая в любой перекресток А впервые по некоторому пути а, при возвращении в этот перекресток А избегать пользоваться путем а до тех пор, пока это возможно; и лишь только в том случае идти по пути а в обратную сторону, когда все остальные пути из А будут пройдены дважды. Теорема 3. Для того, чтобы связный граф (мультиграф) был эйлеровым, необходимо и достаточно, чтобы степени всех его вершин были четными. Замечание. Данная теорема позволяет решить задачу о семи кенигсбергских мостах. Решение задачи о семи кенигсбергских мостах. Вопрос задачи: возможно ли найти такой маршрут, который оканчивался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз? А В терминах теории графов эта задача может быть сформулирована так: является ли мультиграф семи кенигсбергских мостов эйлеровым графом? В D Найдем степени вершин. Степень А = 3, ст. В =5, ст. D = 3, ст. С =3. Из теоремы 3 следует, что данный мультиграф неэйлеров, так как его вершины имеют нечетную степень. Из этой же теоремы видно, как Рис. 2 С нужно дополнить граф, что бы он стал эйлеровым. Ответ. Такой маршрут не существует. 34 п. 4. Двудольные графы. Определение 27. Граф G  V ,W  называется двудольным, если множество его вершин V можно разбить на два таких непересекающихся подмножества V1 и V2 , что никакие две вершины из одного и того же подмножества не соединены между собой ребрами. Замечание. Чтобы подчеркнуть, что данный граф – двудольный, его вершины на диаграмме располагают параллельными строками или столбцами. Двудольные графы полезны, когда изучаемые объекты разделяются на две группы так, что внутри групп интересующие нас взаимодействия отсутствуют. В генетике, например, это могут быть признаки и гены, в демографии – особи разного пола, в экологии – хищники и жертвы, в экономике – производители и потребители и т. д. V1 V2 Определение 28. Двудольный граф называется полным двудольным, если каждая вершина V1 соединена с каждой вершиной V2. Обозначение: Un,m – полный двудольный граф, множество V1 которого содержит n вершин, а V2 – m вершин. В таком графе имеется (n ∙ m) ребер. U1,5 U3,3 По виду диаграммы графа не всегда просто определить, является ли данный граф двудольным. Ведь совсем не обязательно, чтобы вершины двудольного графа располагались двумя параллельными строками. Например, любая простая незамкнутая цепь – двудольный граф, как и любое дерево. Например: b2 b1 a3 b1 b2 b3 b3 a1 a2 a1 a2 a3 Теорема 4. Граф двудолен тогда и только тогда, когда все его простые циклы имеют четную длину. (Простые циклы – все вершины различны, начальная и конечная вершины совпадают) С двудольными графами связана задача о назначениях. Пусть имеется несколько рабочих мест для строителей, несколько – для слесарей, какое-то число мест для маляров, монтажников и т. д. – всего m рабочих мест. С другой стороны, имеется n претендентов. Причем, некоторые из претендентов владеют несколькими профессиями. Можно ли всех претендентов обеспечить работой, и каждому из них предоставить должность в соответствии с его профессиональной подготовкой? Понятно, что это можно сделать далеко не всегда. Во-первых, должно быть m ≥ n. Но этого мало, пусть, например, вакантными являются три места монтажника и одно место строителя. Тогда группу, состоящую из двух строителей и одного строителя – монтажника, нельзя обеспечить работой. Один из строителей окажется незанятым. Сформулируем задачу в терминах графов. Пусть V1 – множество претендентов, V2 – множество вакантных рабочих мест. Вершину a из V1 соединим ребром с вершиной b из V2, если претендент a способен занять рабочее место b. Тогда получим двудольный граф G (рис. 9) Наша задача заключается в том, чтобы из этого графа выделить подграф G1 , состоящий из компонент, в каждой из которых только две вершины, и эти вершины соединены ребром (рис. 10 ). G1 – подграф назначений. 35 b1 a1 b2 a2 b3 b4 b5 a3 Рис. 9 а4 b6 а5 b7 а6 b1 a1 b2 b3 a2 a3 b4 b5 а4 a5 Рис. 10 b6 b7 а6 Теорема 5 (необходимое и достаточное условие существования подграфа назначения) Пусть множество V1 двудольного графа G содержит n вершин. Для того, чтобы граф G содержал подграф назначений G1, необходимо и достаточно, чтобы для любого подмножества A  V1 , содержащего k вершин, k = 1,2,…,n , нашлось k вершин из V2, каждая из которых соединена ребром хотя бы с одной вершиной из А. В терминах первоначальной задачи это означает, что какую бы группу из k претендентов мы бы ни взяли, найдется k должностей, каждую из которых способен занять хотя бы один человек из взятой группы. Замечание 1. От ограничения m ≥ n можно отказаться и изучать вопрос о том, сколько и каких подграфов назначений с тем или иным числом компонент можно образовать из данного двудольного графа и т. д. Замечание 2. Немецкий математик Герман Вейль называл задачу о назначениях задачей о деревенских свадьбах. В его трактовке V1 и V2 – это множества девушек и юношей, живущих в одной деревне, а ребра графа означают, что юноша и девушка знакомы (или симпатичны) друг с другом. Желая обеспечить каждую девушку женихом из множества знакомых (или симпатичных) парней, мы должны будем отыскать в этом двудольном графе подграф назначений. Замечание 3. Подобно двудольным графам можно рассматривать трехдольные и k-дольные с любым k. п. 5. Планарные и плоские графы. Среди изоморфных диаграмм одного и того же графа могут быть диаграммы с ребрами, пересекающимися не только в вершинах. Некоторыми из таких диаграмм легко заменить изоморфными, лишенными этого недостатка. Определение 29. Граф называется планарным, если его можно изобразить на плоскости диаграммой, ребра которой пересекаются только в вершинах. Саму диаграмму называют плоским графом. Замечание. Одни графы можно нарисовать на плоскости так, чтобы их ребра не имели общих точек, кроме вершин им принадлежащим; другие так рисовать нельзя. В силу этого отдельные графы могут рассматриваться как географические карты, нанесенные на плоскость или сферу. Определение 30. Если планарный граф односвязен, то его плоский граф называется картой. Пример. Рассмотрим карту некоторого графа. 36 А2 а) А2 b) На рис. а) изображен не плоский А1 А3 А5 А1 А4 А3 А4 с) В А5 d) С А В С граф. На рис. b) изображен тот же граф, только плоский. На рис. с) изображен не планарный граф, на рис. d) – изоморфный ему плоский граф – карта. В отличие от географических карт плоский односвязный граф может иметь висячие вершины. А Определение 31. Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Пример. а) 7 4 b) 2 1 3 1 5 2 6 3 5 4 На рис. а) (1,2,4,1) – не грань, так как она содержит внутри себя (1,2,3,1). Всего в графе четыре грани: (1,7,4,1), (1,4,2,3,1), (1,2,3,1), (2.6,5,4,2). На рис. b) (1,2,3,4,1) – грань, так как ребро (4,5) не образует цикла. Определение 32. Цикл, охватывающий все внутренние грани, называется внешней границей карты. Множество точек плоскости, лежащих вне этого цикла, называется границей внешней грани. Замечание. Любому выпуклому трехмерному многограннику можно поставить в соответствие некоторую карту, ребра и грани которой, включая внешнюю, соответствуют ребрам и граням многогранника. Теорема 6. Для любой карты число вершин (В), число ребер (Р) и число граней карты (Г), включая внешнюю, связаны равенством: В + Г – Р = 2 Теорема 7. Полный двудольный граф U3,3 и полный граф U5,5 непланарны. Теорема 8. Для того, чтобы граф G был планарным, необходимо и достаточно, чтобы он не содержал подграф, который можно было бы сузить до U3,3 или U5,5 . Пример (задача о трех домах и трех колодцах) В одной деревне недалеко от трех домов расположены три колодца. В разное время года доступным оказывается то один, то другой колодец (в жару один из колодцев пересыхает, в мороз какой-то из них замерзает и т. д.). Поэтому каждый дом должен быть соединен тропинкой с каждым колодцем, причем, тропинки пересекаются между собой. С этим хозяева домов легко мирились, пока жили в дружбе. Но вот они поссорились, и каждый захотел иметь свои собственные тропинки к колодцам, не пересекающиеся с тропинками соседей. Можно ли проложить такие тропинки? Решение. Решим данную задачу с помощью графов. Обозначим вершины графа как a1, a2, a3, b1, b2, b3, где a1, a2, a3 – дома, b1, b2, b3 – колодцы. Между группой вершин a1, a2, a3 и группой вершин b1, b2, b3 наблюдается соответствие. От каждой вершины отходит три ребра к соответствующим вершинам. 37 По условию задачи, мы имеем полный двудольный граф U3,3 с пересекающимися ребрами. Можно ли построить плоский граф, изоморфный графу U3,3? Иными словами, является ли граф U3,3 планарным? U3,3 b1 а1 b2 а2 b3 Двудольный граф U3,3 изображен на рисунке. Из теоремы 7 следует, что данный граф не является планарным. Т.е. проложить непересекающиеся тропинки нельзя! а3 Замечание. Дорожки можно было бы устроить непересекающимися, если бы один из домов удалось приподнять над землей. Иными словами, если вершины этого графа размещать не в плоскости, а в трехмерном пространстве, его ребра пересекаться не будут. Это свойство присуще любому графу. п. 6. Графы с цветными ребрами. Рассмотрим ситуации, когда одна пара элементов множества находится между собой в одном отношении, другие пары этого же множества – в другом и т. д. Например, 1) среди командучастников баскетбольного турнира к какому-то моменту могут быть такие, которые уже сыграли матчи друг с другом, и такие, которые не сыграли; 2) существуют страны, установившие между собой дипломатические связи, и страны, между которыми они не установлены. Для удобства, на диаграммах графов ребра, соответствующие одному отношению, окрашивают в один цвет, а ребра, соответствующие другому отношению – в другой цвет. Чем больше отношений, тем больше приходится вводить цветов для окраски ребер. Такие графы называют графами с цветными ребрами. Пример. Шесть школьников участвуют в шахматном турнире, который проводится в один круг, т. е. каждый шахматист встречается со всеми участниками по одному разу. Докажите, что среди них всегда найдутся три участника турнира, которые провели уже все встречи между собой или еще не сыграли друг с другом ни одной партии. Решение. Любые два участника находится в одном из двух отношений: они либо уже сыграли друг с другом, либо нет. Каждому участнику поставим в соответствие вершину графа. Соединим вершины попарно ребрами двух цветов. Пусть ребро красного цвета означает, что двое уже сыграли друг с другом, а синего – что не сыграли. Получим полный граф с шестью вершинами и ребрами двух цветов. Теперь для решения задачи достаточно доказать, что в таком графе обязательно найдется «треугольник» с одноцветными сторонами. Примеры других задач: 1. В трехмерном пространстве девять точек размещены так, что никакие три не лежат на одной прямой. Каждая точка соединена отрезками прямых в точности с четырьмя другими. Докажите, что всегда найдется хотя бы один треугольник с вершинами в этих точках. 2. Докажите, что во всякой группе из девяти человек, в которой не найдутся трое попарно незнакомых, найдутся четверо попарно знакомых. п. 7. Ориентированные графы. Вводя понятие графа, мы интерпретировали ребро u как символ связи между двумя объектами. Но часто такая связь бывает неравнозначной. Например: 1. Два человека могут быть не просто знакомыми, а, допустим, один из них по службе подчиняется другому, или один из них является родителем другого. 2. Схема города – граф с вершинами на перекрестках и поворотах, а если ввести одностороннее движение транспорта, то на ребрах необходимо ставить указатели направления движения. Чтобы отразить подчинение одной вершины другой, рассматривают упорядоченные пары вершин, а соответствующий граф называют ориентированным графом или орграфом. 38 Определение 33. Ориентированным графом называется упорядоченная пара G  V ,W , где V  a, b, c,..., v – множество вершин, W  (a, b), (c, a),..., (u, v)– множество упорядоченных пар различных вершин из V. На диаграммах ориентированных графов и мультиграфов ребра снабжают стрелкой, указывающей, в какую вершину идет данное ребро. Определение 34. Упорядоченная пара (a, b)  W называется ориентированным ребром или дугой, идущим из вершины а к вершине b. Иногда ориентированное ребро (или дугу) от А к В обозначают:  A, B  , А – начальная вершина, В – конечная вершина. В отличие от ребер (в простых графах), дуги соединяют две неравноправные вершины: одна из них – начало дуги, другая – конец. Замечание. Ориентированный граф определяется как кортеж V ,W , где V – набор вершин, а W – подмножество прямого произведения V  V , обозначающее ребра. Примеры. 1) Пусть Х – множество лиц некоторой военной организации. Бинарное отношение R на множестве Х введем следующим образом: xRy, если лицо у подчинено лицу х. Итак, (X, G) – граф. Связь любого начальника с подчиненным изобразиться в виде дуги графа (X, G). 2) Орграф – стройка, вершины – работы, дуги – необходимое предшествование работы. Определение 35. можно переписать: Граф, все ребра которого ориентированы, называется ориентированным графом. Соответствующим образом можно определить и ориентированные мультиграфы. Примеры. 1. Изобразить орграф G  V ,W , где V  a, b, c, d , W  (a, c), (b, c), (a, d ). Решение. b a c d 2. Проводится круговой турнир по баскетболу между командами A, B, C, D, E. Каждая команда играет с каждой командой по одному разу. Требуется изобразить итоги турнира: В выиграла все встречи, С проиграла все, А выиграла у С и D и проиграла у В и D. Решение. Поставим командам в соответствие вершины, ориентированный граф имеет вид: X  Y : X выиграла у Y. A B C D соответствующий условию задачи E Степень вершины в орграфе – не одно число, как в простом графе, а пара чисел. Первое число характеризует количество исходящих из вершины дуг, а втрое – входящих. Определение 36. Степенью выхода вершины А ориентированного графа называется число выходящих из А ребер. Степенью входа вершины А называется число ребер, входящих в А. 39 Определение 37. Изолированной вершиной ориентированного графа называется вершина, у которой и степень входа и степень выхода равны нулю. Источником называется вершина, степень выхода которой положительна, а степень входа равна нулю. Стоком называется вершина, степень входа которой положительна, а степень выхода равна нулю. В А F – изолированная вершина, D – источник, С – сток. F С E D Определение 38. Вершина А и дуга u называются инцидентными, если дуга заходит в эту вершину или исходит из нее. Способы задания орграфов. 1. Перечислением дуг графа с указанием концов и добавлением списка изолированных вершин. 2. Заданием множества его вершин V и способа отображения Г множества V в V, таким образом, орграф G есть пара (V, Г), например, орграф, заданный следующим образом Гх1 = х1, Гх2 =  , Гх3 = {x2 , x4 , x5} , Гх4 = {x4 , x5} изображается в виде: х2 х3 х5 х1 х4 3. Заданием матрицы смежности вершин графа с m вершинами. Это квадратная матрица A  (aij )mm , строки и столбцы которой соответствуют вершинам графа, причем неотрицательный элемент aij равен числу дуг, идущих из вершины xi в вершину xj. Если исходящих дуг нет, то aij  0 . 4. Заданием матрицы инциденций (инцидентности) графа с m вершинами и n дугами. Это прямоугольная матрица B  (bij )mn , строки которой соответствуют вершинам графа, а столбцы – дугам. Если xi является началом дуги uj, то есть дуга исходит из вершины, то bij  1 ; если xj – конец дуги uj, то есть дуга заходит в вершину, то bij  1 . Петле соответствует элемент, равный 2 (в некоторых источниках, равный 0). Пример. Ориентированный граф определяется следующим образом: Гх1 = х1, Гх2 =  , Гх3 = {x2 , x4 , x5} , Гх4 = {x3 , x4 } , Гх5 = х4 , Гх6 = х7, Гх7 =  . Записать матрицу смежности и матрицу инциденций. Решение. х7 х1 х6 х5 х3 х4 х2 40 Для матрицы инциденций пронумеруем пути: u1– (х1, х1), u2 – (х2, х3), u3 – (х3, х4), u4 – (х4, х3), u5 – (х4, х4), u6 – (х3, х5), u7 – (х5, х4), u8 – (х6, х7). Матрица смежности графа имеет вид: 1  0 0  A  0 0  0  0 1 1 1 1 1 1 Матрица инциденций графа имеет вид: 0  0 0  0 0  1  0 2 0 0 0  0 1 0 0 0 1 1 1  B  0 0 1 1 0 0 0 0  0 0 0 0  0 0 0 0 0 0 0 0  0 0 0 0 0 1 0 0  2 0 1 0  0 1 1 0  0 0 0 1  0 0 0  1 Определение 39. Маршрут – чередующаяся последовательность вершин и дуг (вершины могут повторяться). Определение 40. Путем в ориентированном графе от А1 до Аn называется последовательность ориентированных ребер  A1, A2  ,…,  An 1 , An  , т.е. маршрут, такой, что конец каждого предыдущего орребра совпадает с началом следующего и ни одно орребро не встречается более одного раза. Определение 41. Простым (элементарным) путем в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза. Определение 42. Цепь – последовательность вершин и ориентированных ребер, образующих путь. Всякий путь – цепь (обратное верно лишь для неориентированных графов, в которых понятие пути и цепи совпадают). Определение 43. Замкнутый путь в ориентированном графе называется ориентированным циклом. Замечание. Есть и другое определение: если начальная вершина совпадает с конечной, то такой путь называют контуром длины k. Определение 44. Эйлеровым путем в ориентированном графе называется путь, содержащий все его ориентированные дуги. Пример. На рисунке А) изображен эйлеров орграф, так как имеется ориентированный цикл abcdeca, содержащий все его ориентированные дуги. Изменение ориентации в одной дуге, например (c,b) вместо (b,c), превращает этот орграф в неэйлеров (рис. В). В пункт b можно приехать по двум дорогам, но нельзя оттуда выехать. A) b d B) b d a c e a c e Определение 45. Длиной пути в ориентированном графе называется число дуг в этом пути. Замечание. Путь нулевой длины состоит из одной вершины. Путь может быть конечным и бесконечным. 41 Определение 46. Путь минимальной длины называют кратчайшим путем. Путь максимальной длины – максимальным путем. Определение 47. Расстоянием от А до В в ориентированном графе называется длина наикратчайшего пути от А до В. Замечание. Среди огромного числа задач теории графов отметим следующие три задачи, относящиеся к задачам о кратчайшем пути и имеющие важное прикладное значение. Задача 1. Найти в графе (X, G) путь, ведущий от вершины А к вершине В. Задача 2. Найти путь наименьшей длины, ведущий от А к В. Задача 3. Каждой дуге графа (X, G) отнесем число, которое назовем длиной дуги. Требуется найти путь, ведущий из данной вершины А в данную вершину В такой, что его полная длина была наименьшей. Пример.  0 1 0 0    0 0 1 0 Найти число максимальных путей графа с матрицей смежности А порядка 4: A   . 0 0 0 1    0 0 0 0   Решение. Граф состоит из 4-х вершин и 3-х дуг: (х1, х2), (х2, х3), (х3, х4). Путь х1 u1 х2 u2 х3 u3 x4, длина которого равна 3, является максимальной, следовательно, число максимальных путей равно 1. Определение 48. Полный путь – это путь от начальной вершины х1 до конечной хn. Определение 49. Полным ориентированным графом называется граф, каждая пара вершин которого соединена в плоскости одним ориентированным ребром. Полный ориентированный граф с пятью вершинами. Теорема 9. Всякий полный ориентированный граф с n вершинами имеет простой ориентированный путь, проходящий через все вершины графа. Иногда встречаются графы, часть ребер которых ориентирована, а другая – нет. Такие графы называют смешанными. Смешанный граф можно превратить в ориентированный мультграф, если каждое его неориентированное ребро a, b заменить двумя ориентированными и противоположно направленными: (а,b) и (b,а). Примером смешанного графа является сеть городских улиц, если на некоторых улицах установлено одностороннее движение, а на других – двустороннее. Определение 50. Ориентированный граф называется связным, если каждые две его вершины связные, иначе, если любая пара его вершин соединяется путем. Граф называется несвязным, если хотя бы две вершины несвязные. Ориентированный граф называется сильно-связным, если в нѐм существует ориентированный путь из любой вершины в любую другую. Ориентированный граф называется слабо-связным, если является связным неориентированный граф, полученный из него заменой ориентированных ребер неориентированными. Например, все компьютеры, включенные в сеть Интернет, образуют связный граф, и хотя отдельная пара компьютеров может быть не соединена напрямую (в формулировке для графов — не быть соединены ребром), от каждого компьютера можно передать информацию к любому другому (есть путь из любой вершины графа в любую другую). п. 8. Сетевые графы или графики Рассмотрим пример из повседневной жизни. Строится школа. Как организовать работу, как распределить рабочую силу, финансы, с какого участка взять людей для переделок и т. д. и т.п., так, 42 чтобы все обошлось максимально дешево? Это задача для специальных графов, с помощью которых можно построить сеть сложного комплекса работ, определить по сети самые ответственные работы, вычислить время завершения всего комплекса, найти резервы времени для отдельных событий и работ. Основными понятиями этих спец. графов являются понятия работы и события. Определение 51. Работа – любые действия, сопровождающиеся затратами ресурсов и времени и приводящие к определенным результатам. Определение 52. Всякий намеченный комплекс работ, необходимых для достижения цели, называют проектом. Проект расчленяется на отдельные работы. Например, если проект – строительство школы, то отдельные работы: подвоз материалов, рытье котлована и т. д. При выполнении комплекса работ всегда можно выделить ряд событий, т. е. итогов какой-то деятельности, позволяющих приступить к выполнению следующих работ. Определение 53. Событие – результат завершения одной или нескольких работ – является предпосылкой выполнения работ, следующих за ним. Любая работа может быть определена двумя событиями, между которыми она находится. Событием может начинаться или заканчиваться несколько работ. Если каждому событию поставить в соответствие вершину графа, а каждой работе – ориентированное ребро, то получится граф, отражающий последовательность выполнения работ. А если над ребрами поставить время, необходимое для завершения работы, то получится сеть. Определение 54. Изображение сети называется сетевым графиком. С математической точки зрения сетевой график – это связный орграф без петель и контуров. Он обладает рядом особенностей. В частности, имеет только одно исходное событие (исток сети) и только одно завершающее (окончание всех работ). Основные правила построения сетевого графика. 1. Каждую стрелку на ребре рисуют так, чтобы ее конец находился правее начала, по возможности горизонтально. 2. Строят без лишних пересечений. 3. Во все вершины, кроме той, которая соответствует исходному событию, должна входить, по меньшей мере, одна стрелка (т. к. все события, кроме исходного, имеют предшествующую работу). 4. Из всех вершин, кроме завершающей, должны выходить стрелки. 5. Не должно образовываться циклов. 6. Если одно событие служит началом для двух и более работ, после завершения которых начинается выполнение следующей работы, то вводится штриховая стрелка и дополнительное событие со своим номером. Примеры правильного и неправильного построения сетевых графиков. а с неправильно 1 2 3 b а 2 с 1 3 правильно 4 b а 1 с 2 b d 4 5 правильно 3 43 Имея сеть работ некоторого проекта, можно посчитать время выполнения всего проекта и различных его частей, состоящих из разного набора работ. Определение 55. Путь в сети от исходного события до завершающего называют полным путем (L). Определение 56. Продолжительностью пути называется время, необходимое для выполнения всех работ, лежащих на этом пути. (t(L)). Пример. L1 4 1 3 5 Найти продолжительности полных путей L1, L2, L3 в сетевом графике. Решение. 2 L2 5 6 3 1 7 L3 2 2 4 2 3 t(L1) = 3 + 4 +2 = 9, t(L2) = 5 + 6 = 11, t(L3) = 1 + 2 +2 + 3 = 8. 6 Определение 57. Путь, имеющий наибольшую продолжительность, называется критическим путем. Он определяет минимальное время выполнения всех работ комплекса. Определение 58. Минимальное время называют критическим сроком и обозначают tкр. В примере выше, критический путь L2, критический срок tкр = 11. В сети м. б. несколько критических путей. Определение 59. Работы и события, лежащие на критическом пути, называются критическими работами. Все остальные работы и события – некритическими. Задержка любой критической работы вызывает задержку выполнения всего комплекса. Следовательно, чтобы уменьшить время выполнения комплекса работ, надо сократить сроки критических работ. Некритические работы допускают некоторое запаздывание их выполнения без нарушения критического срока. Это запаздывание измеряется резервом времени событий и работ. Определение 60. Свершением события называется момент, к которому заканчиваются все входящие в него работы и может быть начата любая выходящая работа. Некоторые события можно совершать в разные моменты, то есть варьировать свершение этих событий. Поэтому для событий различают ранний и поздний сроки свершения. Определение 61. Ранним сроком tр свершения события называется самый ранний момент времени, к которому завершатся все работы, предшествующие этому событию. Обозримость сетевого графика или его частей значительно облегчает восприятие существа всей системы, взаимосвязей всех работ, упрощает весь последующий процесс по руководству системой при ее реализации. Замечания. 1. Для отыскания критического пути используются деревья. Например, в генетике они применяются для наглядного описания вероятностей независимых и равновозможных событий, составляющих полную группу. 2. Сети оказываются естественным и удобным средством для описания и анализа сложных проектов. Сетевые модели сложных комплексов работ были разработаны, и начали люди ими пользоваться лишь в 50-ых годах 20 века. Сетевая модель была применена в США при создании баллистических ракет «Поларис». Сетевой график включал в себя более 10000 событий. Первая и наиболее распространенная система планирования и управления в США носит название «ПСРТ». Американские специалисты подсчитали, что сети позволяют на треть сократить продолжительность работ. 44