3 8 7 6 Министерство образования Республики Беларусь БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра «Теоретическая механика» С.Г. Бохан С.И. Пармон ДИСКРЕТНАЯ МАТЕМАТИКА Методическое пособие Часть 1 М и н с к Б Н Т У 2 О 1 О Министерство образования Республики Беларусь БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра «Теоретическая механика» С.Г. Бохан С.И. Пармон ДИСКРЕТНАЯ МАТЕМАТИКА Методическое пособие по лабораторным работам для студентов машиностроительного факультета специальностей 1-55 01 01 «Интеллектуальные приборы, машины и производства», 1-55 01 03 «Компьютерная мехатроника», 1-36 01 01 «Технология машиностроения», 1-36 01 04 «Оборудование и технологии высокоэффективных процессов обработки материалов», 1-53 01 01 «Автоматизация технологических процессов и производств» В 2 частях Часть 1 Минск БИТУ 2010 УДК 519.1(076.5X075.8) •ББК-22.176И7 Б86 Р е ц е н з е н т ы : О. И. Чичко, Е.В. Польшкова Бохан, С.Г. Б86 Дискретная математика: методическое пособие по лабораторным работам для студентов машиностроительного факультета специальностей 1-55 01 01 «Интеллектуальные приборы, машины и производства», 1-55 01 03 «Компьютерная мехатроника», 1-36 01 01 «Технология машиностроения», 1-36 01 04 «Оборудование и технологии высокоэффективных процессов об- работки материалов», 1-53 01 01 «Автоматизация технологических процессов и производств»: в 2 ч. / С.Г. Бохан, С.И. Пармон. - Минск: БНТУ, 2010. - Ч. 1 . -74 с. ISBN 978-985-525-384-7 (4.1). В методическом пособии излагается материал по курсу лекций «Дис- кретная математика», читаемых на дневном и заочном отделениях машино- строительного факультета. Первая часть пособия включает материалы кур- са, связанные с математической логикой, теорией множеств, комбинатор- ными алгоритмами и теорией графов. УДК 519.1(076.5X075.8) ББК 22.176я7 ISBN 978-985-525-384-7 (4.1) ISBN 978-985-525-385-4 © Бохан С.Г., Пармон С.И., 2010 ©БНТУ, 2010 ВВЕДЕНИЕ Целью выполнения лабораторных работ является изучение алгоритмов решения типовых технических задач и овладение методами дискретной математики, наиболее приемлемыми для их решения. В современной иерархии математических наук дискретная математика является промежуточным звеном между рядом дисциплин естественно-научного и технического профиля. Задачами курса дискретной математики являются ознаком- ление и освоение основных моделей и методов формализован- ного представления: теоретико-множественных, логических, графических. Мощным фундаментом современной дискретной математики являются теория множеств, математическая логика и теория графов. Дискретная математика была и остается одной из наиболее динамичных математических дисциплин. Она изучается почти во всех вузах технического и экономического профиля. Основное отличие дискретной математики от классической заключается в отсутствии понятий предела и непрерывности, а основными носителями являются, например, целые числа и многочлены, векторы и матрицы, чертежи и рисунки, слова и команды и т.п. В курсе закрепляются умения оперировать аппаратом тео- рии множеств, в том числе с отношениями и функциями; использовать основные законы алгебры логики для преобра- зования логических функций, распознавать различные ком- бинаторные конфигурации и подсчитывать их число, осуще- ствлять операции над графами, строить и программировать алгоритмы для обработки различных графов. Для изучения дисциплины «Дискретная математика» тре- буется математическое образование, основанное на ряде математических курсов, таких, как математический анализ, аналитическая геометрия, линейная алгебра и т.д. На материале этой дисциплины в значительной степени базируется содержание дисциплины «Математическое моделирование физических и технических процессов». Знание дискретной математики необходимо также при изучении таких дисциплин, как «Теоретические основы электротехни- ки», «Исследование операций», «Электроника и микропроцес- сорная техника» и др. При изучении дисциплины необходимо обращать внимание студентов на то, что недостаточно знать рассматриваемые алгоритмы дискретной математики, надо уметь разрабатывать реализующие их алгоритмы и компьютерные программы. В связи с этим, полезно на примере нескольких алгоритмов показать студентам, каким образом традиционное изложение алгоритмов, ориентированное на решение задач на графах «вручную», переработать применительно к обработке их матриц смежности или инцидентности, что позволит их запрограммировать. На сегодняшний день наиболее значимым направлением развития дискретной математики являются информационные технологии. Это объясняется, прежде всего, необходимостью создания и эксплуатации персональных ЭВМ, компьютерных сетей, систем управления, а также автоматизированных средств обработки информации. Комплекс лабораторных работ предназначен для закрепле- ния материала курса «Дискретная математика» с помощью компьютерных технологий. Для всех лабораторных работ предусмотрены 14 вариантов индивидуальных заданий (по количеству компьютеров в классе). Эти варианты помещены в электронное издание «Дискретная математика» и находятся в научной библиотеке БНТУ. По количеству часов весь лекционный материал можно представить в виде следующей диаграммы (рис. 1). 25 20 15 10 " W матема тическа I Ряд1 12 теория множвс комбина | теория торика графов 22 теория чисел г 4 . • - ^ Рис. I. Диаграмма распределения учебных часов При чтении этого курса в технических вузах, как правило, выбираются следующие разделы и подразделы дискретной математики (табл. 1). Таблица 1 Разделы и подразделы учебного курса Раздел Подраздел Математическая логика Логические операции. Высказывания и высказывательные формы. Элементарные и составные предложения. Конъюнкция и дизъюнкция. Импликация и эквивален- ция. Язык логики высказываний. Форму- лы логики высказываний. Составление таблиц истинности для заданных формул. СДНФ и СКНФ. Кванторы. Переключа- тельные схемы Раздел Подраздел Элементы теории множеств Конечные и бесконечные множества, способы их задания. Понятие и свойства подмножества. Границы числовых множеств. Универсальное множество. Упорядоченное множество. Операции над множествами. Тождества алгебры множеств. Разбиение множества Элементы теории булевых функций Понятие булевой функции. Булевы функции нуля, одной и двух переменных. Логические формулы. Тавтологии, противоречивые и непротиворечивые формулы. Законы булевой алгебры. Конъюнктивная и дизъюнктивная нор- мальные формы Комбинаторика Комбинаторные конфигурации. Подста- новки. Инверсии. Биномиальные коэффи- циенты. Разбиения. Принцип включения и исключения Теория графов Понятие графа. Неориентированные, смешанные и орграфы. Матрицы смеж- ности и инцидентности графа. Подграф, полный граф, дополнение графа. Степень, степень входа, степень выхода вершины. Цепи, циклы, пути, контуры. Гамильгоно- вы и эйлеровы цепи, циклы, пути, контуры. Взвешенные графы. Вес, тонкость, ширина графа, пути, цепи. Связность графов. Деревья, корневые деревья, венки, остовы. Двудольный граф. Изоморфизм графов. Транспортная сеть. Разрез транспортной сети. Пропускная способность разреза. Поток на транспортной сети Окончание табл. 1 Раздел Подраздел Теория чисел Наибольший общий делитель. Наимень- шее общее кратное. Простые числа. Сравнение, свойства сравнений. Полная система вычетов. Функция Эйлера. Функция Мебиуса. Формула обращения Мебиуса ЛАБОРАТОРНЫЕ РАБОТЫ Лабораторная работа № 1 МАТЕМАТИЧЕСКАЯ ЛОГИКА Цель работы: ознакомиться с предметом математической логики. Рассмотреть и изучить основные элементы матема- тической логики с помощью электронной таблицы Excel. Методические указания Загрузите программу Excel. Перейдите на новый рабочий лист. Дайте ему имя «Логика». Введите в ячейку А1 формулу: =7>5. Она вернет значение ИСТИНА. Скопируйте содержимое А1 в А2 и исправьте в А2 формулу: =3>5. Эта формула вернет значение ЛОЖЬ. Правые части обеих формул представляют собой высказывания, т.е. утверждения, относительно которых можно заключить, верны они или нет. Рассмотрим другой пример. Введем в ячейку А4 число 2, а в ячейку В4 формулу =А4>3. Формула возвращает значение ЛОЖЬ. Введем в А4 число 6. Формула возвращает значение ИСТИНА. В В4 записан предикат, т.е. высказывание с пере- менными (в данном случае переменная одна). В зависимости от значения переменных предикат может принимать значения ИСТИНА и ЛОЖЬ. В этом примере формула как бы дает ответ на вопрос: «Число (или результат вычислений по формуле), хранящееся в ячейке А4, превышает 3?» В зависимости от значения А4 ответ будет ДА (ИСТИНА) или НЕТ (ЛОЖЬ). Сравнение двух арифметических выражений, содержащих переменные, дает предикат. В формуле =А4>3 ее составные части (А4 и 3) можно считать арифметическими выраже- ниями, только очень простыми. Более сложный пример: =(А4л 2-1)>(2*А4+1). В этом выражении скобки можно опу- стать, потому что арифметические операции имеют более вы- сокий приоритет, чем операции сравнения, но скобки придают формуле наглядность. Высказывание и предикат имеют общее название - логиче- ское выражение. Имеются логические операции, которые позволяют строить сложные логические выражения. Эти операции реализованы в Excel как функции. Можно провести аналогию с арифметическими опера- торами: отрицанию соответствует унарный минус, конъ- юнкции- логическое умножение, дизъюнкции- логическое сложение (табл. 2). На самом деле, в Excel приоритет логи- ческих операций не имеет значения, так как они реализованы в виде функций. Таблица 2 Перечень логических операций Название Обозначение Функция Excel Отрицание —1 НЕ Конъюнкция А (&) И Дизъюнкция V ИЛИ У логических функций аргументы могут принимать только два значения: ИСТИНА и ЛОЖЬ. Поэтому логические функции можно задать таблицей, где перечислены все возможные значения аргументов и соответствующие им значения функций. Такие таблицы называются таблицами истинности (табл. 3). Таблица 3 Таблица истинности JC У И(х,у) ИЛИ(х,у) ЛОЖЬ л о ж ь л о ж ь л о ж ь л о ж ь ИСТИНА л о ж ь ИСТИНА ИСТИНА л о ж ь л о ж ь ИСТИНА ИСТИНА ИСТИНА ИСТИНА ИСТИНА X НЕ(х) ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ Выполните свой вариант задания. Вариант задания опреде- ляется по номеру системного блока компьютера. Пример варианта задания Пример 1 В ячейке А2 (с именем z) записано число. Выяснить, при- надлежит ли оно отрезку [2, 5]. Решение Присвоим ячейке Аб имя z. Введем в А6 число 3. Сначала сконструируем логическое выражение, решающее задачу: ze[2, 5] <=> (z > 2) л (z < 5). Для того чтобы z принадлежал отрезку [2, 5], нужно, чтобы одновременно были истинны два предиката: г > 2 и г < 5. В ячейке В6 разместим формулу =H(z>=2;z<=5). В В6 получим значение ИСТИНА. Пример 2 В ячейке А7 (с именем X) записано число. Выяснить, при- надлежит ли оно одному из лучей на числовой оси: (-оо, 2) или (5, оо). Решение Сконструируем логическое выражение, решающее задачу: ze(-со, 2) и (5, оо) <=> (z < 2) v (z > 5), где значок «и» обозначает операцию объединения множеств. Для того чтобы z принадлежал хотя бы одному из лучей, нужно, чтобы был истинным хотя бы один из предикатов: z <2 или z > 5. В ячей- ке D6 разместим формулу =ИЛИ(Х<2;Х>5). А7 содержит число 3, поэтому формула возвращает ЛОЖЬ. Задачу можно было решить иначе с учетом того обсто- ятельства, что на рабочем листе есть формула проверки принадлежности числа z отрезку [2, 5]. Упомянутые два луча составляют на числовой оси дополнение к этому отрезку. Введем в ячейку Е6 формулу =НЕ(В6). Убедитесь, вводя в ячейку А7 различные числа, что формулы в ячейках D6 и Е6 дают идентичные результаты. Мы воспользовались одним из законов Де Моргана: -i ( а д Ъ) = -\а v -,b. Пример 3 На практике «в чистом виде» логические выражения, как правило, не используются. Логическое выражение служит первым аргументом функции ЕСЛИ: «ЕСЛЩлогвыражение, значение_если_истина, значение_если_ложь)». Во втором аргументе записывается выражение, которое будет вычислено, если логвыражение возвращает значение ИСТИНА, а в третьем аргументе - выражение, вычисляемое, если логвы- ражение возвращает ЛОЖЬ. В языках программирования высокого уровня этой функции соответствует оператор «если лог выражение то действие 1, иначе действие 2». Пример 4 1. Введем в ячейку В8 формулу, которая возвращает z + 1, если z > 1, и z в противном случае: =EGJEi(z>l;z+l;z) (в «Мас- тере функций» ЕСЛИ находится в категории «Логические», так же, как функции И, ИЛИ, НЕ). 2. Если z > 60, то в ячейке В9 выводить сообщение «Превышено пороговое значение», в противном случае выводить z: =ЕСЛИ(г>60,"Превышено пороговое значение"^). 3. Если z е [10, 25], то возвращать z, если z < 10, то возвращать 10, если z > 25, то возвращать 25. Сконструируем выражение (одно из возможных): «если z < 10 то 10 иначе (если z < 25 то z иначе 25)». Запишем формулу в С9: =ЕСЛИ(г < 10; 10; ЕСЛИ(г <= 25;z; 25)). Задача 1 Дайте ячейкам А20, В20 и С20 имена и, v, w. В самих ячейках содержатся числа. Введите в ячейки А21, А22 и так далее логические формулы, которые возвращают значение ИСТИНА тогда и только тогда, когда: а) каждое из чисел и, v, w является положительным; б) хотя бы одно из чисел и, v, w является положительным; в) только одно из чисел и, v, w является положительным; г) ни одно из чисел и, v, w не является положительным; д) хотя бы одно из чисел и, v, w не является положи- тельным. Задача 2 Торговый агент получает процент от сумхмы совершенной сделки. Если объем сделки до 3000, то 5 %; если объем до 10 ООО, то 2 %; если выше 10 000, то 1,5 %. Введите в ячейку А10 текст «Объем сделки», в ячейку АН - «Размер воз- награждения». В ячейку В10 введите объем сделки, а в В11 - формулу, вычисляющую размер вознаграждения. Задача 3 В трех ячейках записаны числа. Если все они ненулевые, вернуть 1, в противном случае - 0. Решить задачу с исполь- зованием только одной функции ЕСЛИ (без вложений). Задача 4 Экзаменатор проверяет письменную работу, состоящую из пяти задач. За каждую задачу он проставляет оценку - целое число в диапазоне от 0 до 4. Иногда (в виде исключения) он может поставить нецелое число, например 3,5. Введите в А24:Е24 порядковые номера задач (от 1 до 5), в Р24 - строку «Сумма». Экзаменатор вводит оценки в диапазон А25:Е25. В Р25 автоматически должна вычисляться сумма оценок. При переходе к ячейке подсказка не выводится, при неверном вводе выводится предупреждение. Указание. Перед вызовом меню «Данные/ Проверка» выде- лите диапазон А25:Е25. Контрольные вопросы 1. Назовите известные Вам логические операции. 2. Отличие высказываний от высказывательных форм. 3. Формулы логики высказываний. 4. Конъюнкция и дизъюнкция. 5. Таблицы истинности. 6. Какие предложения являются составными, а какие элементарными? 7. Логические связки и их использование. Лабораторная работа № 2 ЛОГИЧЕСКИЕ ОПЕРАЦИИ Цель работы; изучить логические операции и научиться применять законы логики для решения задач с помощью таблиц Excel. Методические указания Загрузите программу Excel. Перейдите на новый рабочий лист. Дайте ему имя «Логические операции». Логическая операция, соответствующая союзу «если..., то» называется импликацией. Обозначается символом ->. Логическая операция, соответствующая союзу «тогда и только тогда, когда», называется эквиваленцией. Обозна- чается символом Преобразование формул Формулам математической логики свойственны следующие законы: А.Х=Х-закон тождества. 2.Х а X = л - закон противоречия. 3. X v X = и - закон исключенного третьего. 4. Х = Х- закон двойного отрицания. X v Х=Х- законы идемпотентности. 6.Х л Y а X; X v Y=Y v Х- законы коммутативности. 7 . ( 1 л 7 ) л Z = X a ( 7 л Z); ( I v 7) v Z = X v (7 v Z) - законы ассоциативности. 8. XAY = XVY; ——- — - - законы Де Моргана. Переключательные схемы Переключательная схема- это устройство из переклю- чателей (контактов) и проводов, связывающих 2 полюса- вход и выход. Рассмотрим схему с одним контактом (рис. 2). -^чэ—5 Рис. 2. Схема с одним контактом Сопоставим контакту Р переменную х, а состоянию контакта «замкнут» - значение ИСТИНА, состоянию контакта «разомкнут» - значение ЛОЖЬ. Если взять два контакта, соединенных последовательно, то полученная схема будет выражаться формулой вида: Х1 лХ2(рис. 3). Рис. 3. Схема с последовательными контактами Если контакты Pi и Рг соединены параллельно, то цепь замкнута, когда хотя бы один из контактов замкнут, и разомкнута, когда оба они разомкнуты. Такой схеме соответствует формула Xj v Хг (рис. 4). Рис. 4. Схема с параллельными контактами Установленные соответствия дают возможность описать любую цепь с последовательно или параллельно соеди- ненными контактами формулами логики высказываний. С другой стороны, любую формулу логики высказываний можно смоделировать в виде переключательной схемы. Пример варианта задания Вариант 1 1. Определить, эквивалентны ли следующие формулы {Х Y)Y v Zh(XaF)vZ. Составить таблицы истинности. 2. Доказать, что заданная формула является тавтологией: ( />->(0->/>))_ 3. Записать следующие высказывания словами и опреде- лить истинность их значений: Vx((x>2 л х<1)<->х^х). 4. Построить переключательную схему для формулы ( X - * Y ) Y V Z . Контрольные вопросы 1. Импликация и эквиваленция. 2. Тавтология и противоречие. 3. Построение переключательных схем. 4. Построение СДНФ и СКНФ. 5. Упрощение формул. 6. Законы логики. Лабораторная работа № 3 ТЕОРИЯ МНОЖЕСТВ Цель работы 1. Ознакомиться с теорией множеств. 2. Рассмотреть основные элементы теории множеств с по- мощью программирования на различных языках или с ис- пользованием различных пакетов прикладных программ (MathCad, Maple, Mathematica и т.д.). Методические указания Множество- фундаментальное неопределяемое понятие. Интуитивно под множеством понимают совокупность опре- деленных вполне различаемых объектов, рассматриваемых как единое целое. Множество четных чисел описывается: А = {х\х - четное}. Множество конечное, если число его элементов конечно, т.е. если существует натуральное число N, являющееся чис- лом элементов множества. Пустое множество - множество, не содержащее ни одного элемента, обозначается 0 , например: {хеф2-х+1 = 0} = 0 . Подмножество. Множество X является подмножеством множества У-Хе Y, если любой элемент множества X при- надлежит к множеству У. Объединение множеств X и Y - множество X\J Y, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X и Y, X{J У={х|хеХ; или хеУ}. Q x - ^ n . - . n ^ . i=i Пересечение множеств X и Y - множество Х П / , сос- тоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y, XU Y ~{х\ п xGX; или Xе Y}. П - П Х „ . 1=1 Разность множеств X и Y - множество X\Y, состоящее из тех и только тех элементов, которые принадлежат X и не принадлежат Y, XXY- {х| хеХ; и x£Y}. Универсальное множество I - множество, удовлетворя- ющее условию ХП I = Х. Дополнение множества X - множество X , дополнявшее множество X до универсального X - 1\Х . Тождества алгебры множеств: i . ( x u r ) n z = ( x n z ) u ( r n z ) . 2_ ( X f i r ) U Z = (XUZ)n(FUZ)_ 3. Xf]Y = Y, XUY = X , YeX. 4. X f ] X = X , X\JX = X. 5. X{jY = X f ) Y . 6.Tn? = X\jY. Разбиения множеств Пусть x ={х1,...,х«| - система множеств, М - множество. Система % - разбиение множества М, если выполнено: 1) VX€X[XeM]; 2) УХ,Гех [Х*Г->ХПГ = 0]; 3) UХ = М. Кортеж - последовательность элементов или совокупность элементов множества, в которой каждый элемент занимает определенное место. Прямое произведение множеств Хи У - множество X*Y, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X , а вторая - множеству Y, X*Y={(x,y)\x£X, ye Y}. Пример варианта задания Задача 1 Пусть Х = {xeR\0-) е R21x2 + у2 < 1}, В = {(xj;) е R21 х2 + (>-1)2 < 1}. Задача 3 Составить композицию. Изделие Рабочий Станок Смена 1 2 3 4 5 6 1 2 3 1 2 1 * * * 2 * * * * 3 * * * 1 * 4 * * * * Задача 4 Геометрические множества Х- { 0;1;4;9 }, Y- {1;4;9;16 }, Z = { 1;2;5;8;9;10;13;16;17;18;20;25}. Найти: XU Y, ХП Y, X\J Z, Xf)Z, XU ZU Y. Задача 5 Найти прямое декартовое произведение множеств: Х={0,1}, Г= {0,1,4,9}. Задача 6* А = {а,Ъ,с}, В = {1,2,3,4}, Р1 с АхВ, Р2 с 52. Изобразите Р\, Р2 графически. Найдите [ (PI * Р2 ) - 1 ]. Проверьте, является ли отношение Р2 рефлексивным, анти- симметричным, транзитивным? Контрольные вопросы 1. Способы задания множеств. 2. Парадокс Рассела. 3. Подмножества и надмножества. 4. Диаграммы Эйлера-Венна. 5. Операции над множествами. 6. Алгебраические преобразования множеств. 7. Упорядоченные множества. 8. Свойства отношений. 9. Отношения эквивалентности, порядка, доминирования. 10. Задание соответствий. 11. Обратное соответствие и композиция соответствий. 12. Отображения и их свойства. Лабораторная работа N9 4 КОМБИНАТОРИКА Цель работы: изучить комбинаторные формулы и на- учиться решать задачи с применением комбинаторных алго- ритмов, а также программировать заданные алгоритмы. Методические указания Во многих практических случаях возникает необходимость знать возможные наборы объектов множества, удовлетво- ряющие определенным условиям. Такие задачи называют комбинаторными, а возможные наборы объектов - выборками. Комбинаторные задачи оценивают с точки зрения числа выборок, а алгоритм этого выбора - с точки зрения его слож- ности. При этом различают сложность алгоритма по времени, т.е. числу шагов алгоритма, и по памяти, т.е. объему памяти для выполнения поставленной задачи. Множества элементов, состоящие из одних и тех же раз- личных элементов и отличающиеся друг от друга только их порядком, называются перестановками этих элементов. Число всевозможных перестановок из п элементов обозначают через Р„, это число равно п\: Рп=п\. (1) Замечание 1. Для пустого множества принимается соглаше- ние: пустое множество можно упорядочить только одним способом; по определению полагают 0! = 1. Размещениями называют множества, составленные из п различных элементов по т элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений определяется формулой А™ = и - ( и - 1 ) - ( и - 2 ) - . . . - ( и - « + 1) (2) Сочетаниями из п различных элементов по т называются множества, содержащие т элементов из числа п заданных, и которые отличаются хотя бы одним элементом. Число сочетаний из п элементов по т обозначают: С™ или С ) . Это число выражается формулой С т = гт> и тЦп-т)\ ' k } Замечание 2. По определению полагают С° = 1. Для числа сочетаний справедливы равенства: Cm /-in-m /~<т+1 ли . /-11Я+1 * , 4+1 = С и + С в . (4) Отметим, что числа перестановок, размещений и сочетаний связаны: Ат (5) *т Замечание 3. Выше предполагалось, что все п элементов различны. Если же некоторые элементы повторяются, то в этом случае множества с повторениями вычисляют по другим формулам. Например, если среди п элементов есть щ элементов одного вида, пг элементов другого вида и т.д., то число перестановок с повторениями определяется следующей формулой: п\ Рп(щ,п2,...,пк) = —~ (6) пх\-п1\-...-пк\ где т+ П2 + ... + Щ = п. Число размещений по т элементов с повторениями из и элементов равно пт, т.е. )повтор ~~ п • С )^ Число сочетаний с повторениями из п элементов по т элементов равно числу сочетаний без повторений из п + т - 1 элементов по т элементов, т.е. (Сп )повтор ~Qt+m-l- При решении задач комбинаторики используют следующие правила. Правило суммы. Если некоторый объект А может быть выбран из множества объектов т способами, а другой объект В может быть выбран п способами, то выбрать либо А, либо В можно т + п способами. Правило произведения. Если объект А можно выбрать из множества объектов т способами и после каждого такого выбора объект В можно выбрать п способами, то пара объектов (А, В) в указанном порядке может быть выбрана т п способами. Пример варианта задания Пример решения Сколько экзаменационных комиссий, состоящих из 7 членов, можно образовать из 14 преподавателей? Решение Загрузите программу Excel. Перейдите на новый рабочий лист. Дайте ему имя «Комбинаторика». Для решения используем формулу (3): sym и "** n\ " ml-(n -m)l Очевидно столько, сколько существует семиэлементных подмножеств у четырнадцатиэлементного множества. 14' С " = — = 3432. 7 7!-(14-7)! Присваиваем значения ячеек в Excel соответственно каждому сомножителю данной формулы, т.е. например при- сваиваем: А1:= 7; В1:=14; С1:= ФАКТР(В 1-А1); А2:= ФАКТР(А1); В2;= ФАКТР(В1); С2:=В2/(С 1 * А2). В результате в ячейке С2 появиться значение соответствующее ответу: 3432. Задача 1 На 5 одинаковых карточках написаны буквы М, И, Н, С, К. Эти карточки наудачу разложены в ряд. Какова вероятность того, что получится слово МИНСК? Задача 2 Из десяти билетов выигрышными являются два. Чему равна вероятность того, что среди взятых наудачу пяти билетов один выигрышный? Контрольные вопросы 1. Что называют перестановками? 2. По какой форме вычисляют число перестановок из п различных элементов? 3. Что называют размещениями? 4. По какой формуле вычисляют число размещений из п различных элементов по т элементов? 5. Что называют сочетаниями? 6. По какой формуле вычисляют число сочетаний из п элементов по т элементов? 7. Каким равенством связаны числа перестановок, раз- мещений и сочетаний? 8. По какой формуле вычисляется число перестановок из п элементов, если некоторые элементы повторяются? 9. Какой формулой определяется число размещений по т элементов с повторениями из п элементов? 10. Какой формулой определяется число сочетаний с пов- торениями из п элементов по т элементов Лабораторная работа N9 5 ПРЕДСТАВЛЕНИЕ ГРАФОВ В ВИДЕ МАТРИЦ Цель работы: изучить основные понятия теории графов и научиться использовать матрицы графов для решения задач и применять их при программировании. Методические указания Представление графов в ЭВМ в виде матриц смежности, инцидентности и весов. Пусть N— мощность множества X вершин графа G. Построим матрицу Му, строки и столбцы которой соот- ветственно равны вершинам графа, а элементы определяются следующим образом: П.еслиЭ U={XhX/}; MtJ= J 0, если неЗ U={XhXj}. Такая матрица М называется матрицей смежности (рис. 5). Примеры Рис. 5. Неограф Матрица смежности для графа на рис. 5: f \ 1 О 1 о о V1 О 1 о О 0 1 Для описания графов используется матрица инцидент- ности. Каждой вершине ставится в соответствие каждая строка, а ребру или дуге - столбец матрицы (рис. 6). Для ориентированных графов: 1, если Vt - вершина дуги ei; -1, если Vf - конец дуги ; О, если Vi и е, неинцидентны. Рис. 6. Орграф Матрица инцидентности для графа на рис. 6: 1 -1 Р - 1 0 0 0 1 о О О -1) Матрица весов реберно-взвешенного графа есть квадратная матрица, число строк и столбцов которой равно числу вершин графа (рис. 7). Позиции матрицы весов (х„ xj) при / * j оп- ределяются соотношением гоо, если г =,/; \Jy, если вершина х, смежна вершине ху и вес ребра 11}. Рис. 7. Реберно-взвешенный граф Матрица весов для графа на рис. 7. р x l х2 хЗ х4 х5 хб x l ОС 2 4 х2 2 ос 8 5 хЗ 8 ос 8 5 х4 4 8 ос х5 5 ос 4 хб 5 4 ос Пример варианта задания Построить для заданных графов следующие матрицы: - смежности для неографа графа G1 (рис. 8); - инцидентности для орграфа G2 (рис. 9); - весов для реберно-взвешенного графа G3 (рис. 10). Рис. 8. Граф G1 Рис. 9. Граф G2 Рис. 10. Граф G3 Контрольные вопросы 1. Определение графа, его вершин и ребер. 2. Связность графов. 3. Определение пути в графе и связных компонент графа. 4. Определить цепи, простые цепи, циклы, простые циклы. 5. Неографы и орграфы. 6. Степени вершин в графе. Лабораторная работа № 6 ПУТИ В ГРАФАХ Цель работы: научиться находить кратчайшие, длинней- шие, тончайшие и широчайшие пути в графах при решении различных задач. Методические указания Путем в орграфах G называется такая последовательность дуг (М), в которой конец каждой предыдущей совпадает с каждой последующей. Путь, в котором ни какая дуга не встречается дважды, называется простым. Путь, в котором никакая вершина не встречается дважды, называется элементарным. Контур - это путь, у которого начальная вершина совпа- дает с конечной вершиной. Контур, который проходит через все вершины графа, причем только по одному разу, называется гамильтоновым. Контур, который включает все дуги графа, причем только по одному разу, называется эйлеровым. Весом графа называется сумма составляющих его ребер или дут. Тонкость пути - вес самого тяжелого, ширина пути - вес самого легкого из его ребер и дуг. Длиной пути М невзвешенного графа называется число L, равное числу дуг, составляющих этот путь. Длина пути взвешенного графа определяется как сумма длин дуг, входящих в этот путь. Тончайший путь - путь минимальной тонкости. Широчайший путь - путь максимальной ширины. Алгоритм Дейкстры Поиск кратчайшего пути в графе от одной вершины к другой. Шаг 1. Ставим метки: d(xo) = 0, окрашиваем; d(x,) = +оо. Шаг 2. Для каждой неокрашенной вершины, связанной с последней окрашенной вершиной у дугой {у, х,), пересчитываем ее метку по формуле d(x() = min{d(x,), d(y)+l(y, х,)}. Шаг 3. Среди неокрашенных вершин находим вершину xs с минимальной меткой и окрашиваем ее и ведущую в нее из одной из ранее окрашенных вершин ух дугу (ух, xs), удовлетворяющую условию d(xj) = d(yx) + l(yx, xs). Если при этом закрашенной оказалась конечная вершина, то задача решена, иначе нужно перейти к шагу 2. Получится дерево закрашенных дуг с корнем х0, отобра- жающее кратчайшие пути из этой вершины в другие. Поиск длиннейшего пути в графе от одной вершины к другой. Шаг 1. Ставим метки: d(xo) = 0, окрашиваем; d(x,) = go. Шаг 2. Для каждой неокрашенной вершины, связанной с последней окрашенной вершиной у дугой (у, х,), пересчитываем ее метку по формуле d(x;) = = max {d(x;), d(у) + 1{у, х/)}. Если при этом изменяется метка у ранее окрашенной вершины, то краска с нее и инцидентной ей дуги снимается. Если все вершины окрашены, то задача решена, иначе переходим к шагу 3. Шаг 3. Среди неокрашенных вершин находим вершину х$ и дугу, ведущую в нее из ранее окрашенной вершины, чтобы удовлетворялось условие: d(xs) = d(yr) + l(yr, xs). Закрашиваем их. Если при этом закрашенной оказалась конечная вершина, то задача решена, иначе нужно перейти к шагу 2. Поиск тончайшего пути в графе от одной вершины к другой. Шаг 1. Ставим метки: d(xo) = -да, окрашиваем; d(x,) = +00. Шаг 2. Для каждой неокрашенной вершины, связанной с последней окрашенной вершиной у дугой (у, х пересчитываемое метку по формуле d(x,) = min{max{d(>), l(y, х,)}, d(x;)}. Шаг 3. Среди неокрашенных вершин находим вершину xs с максимальной меткой и такую дугу, ведущую в нее из ранее окрашенной вершины, чтобы удовлет- ворялось условие: d(x,s) = max{dOv), l(yr, Зна- чение d(xK0H) будет искомым значением тонкости тончайшего пути до хКОн- Поиск широчайшего пути в графе от одной вершины к другой. Шаг 1. Ставим метки: d(xo) = -оо, окрашиваем; d(x,) = +оо. Шаг 2. Для каждой неокрашенной вершины, связанной с последней окрашенной вершиной у дугой (у, х,), пересчитываем ее метку по формуле d(x,) = max{min{d(y), l(y, х,)}, d(Xj)}. Шаг 3. Среди неокрашенных вершин находим вершину (назовем ее х^) с максимальной меткой и такую дугу, ведущую в нее из ранее окрашенной вер- шины, чтобы удовлетворялось условие: d(x5) = = mm{d(yr), 1(Уг, xs)}- Окрашиваем найденные вер- шину и дугу. Если конечная вершина окрашена, то задача решена, иначе переходим к шагу 2. Значение d(xKoH) будет искомым значением ширины широчайшего пути до хкон- Пример В графе (рис. 11) найти длину кратчайшего пути из в Х\. Рис. 11. Граф G1 Решение Составим таблицу пошагово. 1 2 3 4 5 6 7 8 S ' Xi 00 00 00 оо 00 1*2 1*2 7^4 Х2 оо СО 00 6*5 х3 ОО 3^4 3^4 3 ,х4 t *4 0^4 00 2Л 2^4 *6 00 м 4 XI 00 00 00 9Л 9 л 6*2 6*2 00 00 4л, 4Л 4Л 4*6 На первом шаге вершине s присваиваем метку (0, s), а остальным (оо). Выбираем из всех меток наименьшую (у, Х4) и делаем ее постоянной. Из этой «постоянной» вершины пытаемся пометить достижимые из нее вершины и присваиваем метку: метка = гшп(старая метка, метка посто- янной вершины + длина ребра). Метки недостижимых вершин сохраняются. У постоянных вершин метки не меняют точки. Процесс продолжаем, пока постоянной меткой не будет помечена вершина t. Метка вершины t равна длине крат- чайшего пути. В нашем случае 2 = 7. Маршрут восстанавли- ваем из второй части меток, которые содержат индекс вершины, из которых они помечены. Тогда кратчайший маршрут: (хь х2, хз, Х4) или (Х4, хз, х2, xi). Пример варианта задания Найти кратчайший и длиннейший пути из вершины хн в вершину хк для графа, представленного на рис. 12. Рис. 12. Реберно-взвешенный граф Контрольные вопросы 1. Гамильтонов контур. 2. Эйлеров контур. 3. Основные характеристики графа. 4. Тонкость и ширина графа. 5. Поиск кратчайшего пути в графах. Лабораторная работа N9 7 ПОТОКИ В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ И ТРАНСПОРТНЫХ СИСТЕМАХ Цель работы: изучить основные положения теории о транспортных потоках. Научиться решать задачи поиска наи- большего потока с помощью алгоритма Форда-Фалкерсона. Методические указания Подобные задачи возникают при выборе маршрутов в вычислительных сетях и транспортных системах. В вычисли- тельных сетях решение подобных задач определяет состав и структуру сетевых протоколов для обслуживания движения пакетов информации. По данным о загрузке каналов, направ- лении и протяженности вычисляется наиболее оптимальный маршрут прохождения пакета информации. В транспортных системах решение подобных задач опре- деляет наиболее экономный по стоимости или по времени маршрут движения транспортной единицы. При работе транспортной системы, когда осуществляется обмен транспортными единицами между узлами сети, возни- кает задача передачи максимального числа транспортных еди- ниц в заданный отрезок времени. При передаче энергии в электрических сетях, жидкости в трубопроводных системах возникает задача распределения и передачи максимального объема энергии или вещества в заданный отрезок времени. Особенностью сети является наличие вершины-истока и вершины-стока, ориентация всех отрезков линий в графе и отсутствие петель и кратных дуг. Объем информации, энергии или вещества, передаваемый в сети от узла х, к узлу хр называют потоком и обозначают <ру. Формулировка задачи При заданной конфигурации транспортной сети и извест- ной пропускной способности ребер найти наибольшее значе- ние потока, который может пропустить транспортная сеть, а также распределение этого потока по ребрам. Алгоритм Форда-Фалкерсона Шаг 1. Всем вершинам транспортной сети присваиваем обозначения х0,хх,х2, •••, хп, где х, - обозначение источника, х„ - стока. Шаг 2. Заполняем таблицу размером пхп пропускными способностями dij=d(xi,xj) ребер транспортной сети. При этом имеем в виду, что неориен- тированное ребро может пропускать поток в обоих направлениях. Числа 0, 1, 2, ..., п будем называть номерами столбцов и строк. Шаг 3. Помечаем столбцы таблицы номерами строк. Нулевой столбец помечаем номером 0. Далее последовательно просматриваем те строки, номера которых совпадают с номерами уже помеченных столбцов. Если при этом просматриваемая строка содержит число, большее нуля, а столбец, в котором расположено это число, еще не помечен, то последний помечаем номером просматриваемой строки. Пометив столбцы, мы тем самым пометили вершины транспортной сети номерами других вершин, из которых в них входят ненасыщенные ребра. При этом, если последний столбец остался непомеченным, то переходим к заключительному шагу 7. Шаг 4. По пометкам столбцов находим ненасыщенный путь из источника в сток по следующей схеме: х„ <- вершина, номер которой равен метке столбца п вершина, номер которой равен метке столбца последующей вершины ... <- х0. Шаг 5. Помечаем клетки таблицы. Если ребро О,,* •) во- шло в найденный на предыдущем шаге путь, то клетку ij помечаем символом «-», а симметричную ей клетку ji - символом «+». Шаг 6. Строим новую таблицу. Среди чисел, помеченных символом «-», находим минимальное, вычитаем его из клеток, помеченных символом «-», и добавляем в клетки, помеченные символом «+». Остальные клетки оставляем без изменений. Переходим к шагу 3. Шаг 7. Заключительный. Из таблицы, полученной на ша- ге 2, вычитаем поклеточно таблицу, полученную на последней итерации на шаге 5. Клетки резуль- тирующей таблицы будут содержать пропускные способности соответствующих ребер. Величина искомого максимального потока равна сумме чисел последнего столбца иди первой строки. Пример Найти максимальный поток на транспортной сети, представленной на рис. 13. Рис. 13. Ориентированный граф, представляющий транспортную сеть Решение Шаг 1. Вершины пронумерованы в нужном порядке. Шаг 2. Строим таблицу и заполняем ее пропускными спо- собностями ребер. Шаг 3. Помечаем столбцы таблицы. Последний столбец помечен, значит переходим к шагу 4. Шаг 4. Метки столбцов определяют следующий путь х4 х2 <— х0. Шаг 5. Помечаем клетки таблицы. Из помеченных минусом минимальным является число 4. Шаг 6. Строим новую таблицу, вычитая число 4 из клеток (0,2) и (2,4) и добавляя его в клетки (2,0) и (4,2). Шаг 3. Помечаем столбцы. Шаг 4. Выбираем ненасыщенный путь х4 х3 х1 <- х0 . Шаг 5. Помечаем клетки таблицы. Шаг 6. Переходим к новой таблице. Шаг 5. Помечаем клетки таблицы. Так как при этом последний столбец остался не помеченным, то пе- реходим к заключительному шагу. Шаг 7. Из первой таблицы вычитаем последнюю. Величина максимального потока равна 8. Примечание. Клетки таблицы содержат распределение по- тока по ребрам. 0 0 0 1 2 0 0 0 1 3 *2 *3 *о *1 *2 х3 х 4 * 4- 1 хп * 4 5- х1 + * 2 6- X, * 2 6 х2 4 2 * 2 4- X-, + 2 * 2 х3 + 2 # 4 2 * 4- Х4 4 + * х 4 + # 0 2 0 2 *о х2 *4 * 1 X, 4 * 2 2 х2 4 2 * 2 *э 4 2 * *4 4 4 * Xq X, Х2 х3 *4 х0 * 4 4 X, -4 * 4 х2 -4 * 4 х3 -4 * 4 х4 -4 -4 * Пример варианта задания Найти наибольший поток на заданной транспортной сети (рис. 14). Х З ^ Х 4 Рисунок 14. Граф, представляющий транспортную сеть Контрольные вопросы 1. Определение транспортной сети. 2. Основные характеристики транспортной сети. 3. Пропускная способность ребер и дуг. 4. Потоки на транспортной сети. 5. Поиск максимального потока. 6. Разрезы на транспортной сети. Лабораторная работа Ns 8 ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ Цель работы: научиться использовать поиски потоков ми- нимальной стоимости для решения транспортных задач. Методические указания Задача о потоке минимальной стоимости формулируется следующим образом: при заданной конфигурации транспорт- ной сети и известной пропускной способности ребер найти поток минимальной стоимости, который может пропустить транспортная сеть. Решить поставленную задачу можно с помощью алгоритма Басакера-Гоуэна. Алгоритм Басакера-Гоуэна Шаг 1. В исходной сети величину потока, а также все ре- берные потоки полагаем равными нулю, т.е. <р2 = О, = 0 ViJ = 1,77, где п = \х\. Шаг 2. Находим путь ц минимальной стоимости из источника jcq в сток z по алгоритму поиска кратчайшего пути в графе, используя в качестве длин ребер дуговые стоимости с^ на первой итерации и модифицированные дуговые стоимости на последующих. Шаг 3. Определяем пропускную способность 0 найденного пути ц: 0 = min {dy - фгЛ. (xhxj)eii Шаг 4. Увеличиваем величину потока cpz и поток фу на ребрах, составляющих путь ц на величину 8' = mm{0,5~9z}: v=0, (pz = 0 . Шаг 2. Находим путь минимальной стоимости. M'l = (х0,х15х3,х5) , |0.2 = (х0,х2,хъ,х5) . Шаг 3. Находим пропускные способности путей: 9j = 1, 02 =1. Так как общее ребро (*3,х5) имеет про- пускную способность 1, то из двух путей вынуждены выбрать один, например, щ. Шаг 4. Увеличиваем величину потока cpz:- <рг + 8j = 1 < В и реберные потоки еру := ф^ +0, на ребрах из . Шаг 5. Добавляем симметричные ориентированные ребра, устанавливаем их пропускные способности и реберные стоимости (рис. 16). Рис. 16. Модификация ребер на транспортной сети Шаг 6. Модифицируем реберные стоимости: с13, Шаг 2. Находим путь минимальной стоимости, при этом принимаем во внимание и симметричные ребра: Ml ={X0'X2^X3'XUX4'X5~) ' М-2 =(*0> х1> х4> "*:5)- Шаг 3. Gj = 1, 62 =1. Учитываем оба найденных пути, так как общие ребра имеют пропускные способности, равные двум. Шаг 4. 9' = min{2,3-l} = 2, значит ф2:=1 + 2 = 3, реберные потоки Фо2,Ф23'Фо1 увеличиваем на единицу, реберные потоки ф14 и ф45 увеличиваем на 2. Так как после этого ф2 = 3 = В, то задача решена, поток минимальной стоимости отмечен на сети. Стоимость найденного потока равна сф = 1 • 1 + 1 х X 2 + 1 • 1 + 2 ( 1 + 2 + 2) = 14. Замечание 1. Если на шаге 2 найдено несколько путей ми- нимальной стоимости, то желательно их обрабатывать одновременно. При этом, если такие пути содержат общие ребра, необходимо сравнивать сумму пропускных способ- ностей путей с пропускными способностями общих ребер. Если эта сумма больше минимальной пропускной способ- ности общих ребер, то суммарный поток необходимо умень- шить до этой минимальной пропускной способности. Замечание 2. При поиске пути минимальной стоимости необходимо принимать во внимание и симметричные ребра с учетом их ориентации. Найти максимальный поток минимальной стоимости для графа, представленного на рис. 17. Первая цифра - величина потока, вторая - стоимость провоза единицы вещества по данной дуге. Рис. 17. Транспортная сеть, нагруженная величиной потока и стоимостью 1. Определение величины потока на заданной транспортной сети. 2. Определение пропускной способности ребер на транспортной сети. 3. Определение минимальной стоимости единицы потока. 4. Понятие минимального разреза на транспортной сети. 5. Постановка задачи о потоке минимальной стоимости. 6. Постановка задачи о максимальном потоке минимальной стоимости. Пример варианта задания Контрольные вопросы Лабораторная работа № 9 ОПЕРАЦИИ НАД ГРАФАМИ. РАДИУС И ДИАМЕТР ГРАФА Цель работы: изучение операций, выполняемых над гра- фами; изучение метрических параметров графов. Методические указания Операции над графами 1. Дополнение графа (рис. 18). Дополнение графа G(X,E) до полного графа G = (X,Ё = {е е X х X \ е <£ Е}), Обратите внимание на стрелки. 1 2 1 2 Рис. 18. Дополнение графа 2. Объединение (рис. 19). GiUG2-G(X1UX2 , EI\JE2). GJU G2 Рис. 19. Объединение графов Обратите внимание - ребра Ев и Ею — это разные связи вершин 2 и 4 (разные дороги между пунктами 2 и 4). 3. Пересечение (рис. 20) при условии Х1С[Х2ф0,Е1(]Е2Ф0. G\ П Gi = G{X\ ni2,£i Г\Ег). Рис. 20. Пересечение графов 4. Кольцевая сумма (рис. 21). Gx Ф G2 = G(X=Xi U Х г , Е = Et ® Ег= № 2 U Щ ) . Замечание. Операции 2-4 коммутативные бинарные опера- ции, но могут быть расширены на большее число графов. Gj©G 2 Рис. 21. Кольцевая сумма 5. Произведение (рис. 22). GxXG2=G(X,E), где Х = Х1хХ2, Е = {(АД, Д262) Е Е, V( А, = А2) Л (6,, 62) Е е Е 2 v V ( ^ = b2) л (aj, а 2 ) е -^l))- В произведении графов вершины обозначаются парами ab, где символы а и Ь - обозначения вершин в G\ и G2 соответ- ственно. Пример Ребро (1х, 1_у) с_ Е, так как первые символы совпадают (1=1), а в G2 есть ребро (х, у). Аналогично и для других ребер. G • 1 •2 x G2 У z 2x 2y Рис. 22. Пример произведения графов Произведение G\ х 02 означает, что каждая вершина G\ за- меняется на копию Ga - G2, а каждая вершина Gi заменяется на копию Gb~G\. 6. Композиция (рис. 23). G1[G2] = G(X = Xj X х 2 , Е = {(а^, а262) е Е, V( а, = а2) л 62) е e £ 2 v V (а15 а2)е£,}). В композиции графов, как и в произведении графов, верши- ны обозначаются парами ab, где символы а и Ъ - обозначения вершин в G\ и G2 соответственно. Пример G , Рис. 23. Композиция графов Композиция GifGy означает, что каждая вершина G\ заменяется на копию Ga ~ G2, а затем, если (а\, ai) е Е\, то между любыми вершинами bi из Ga 1 и 62 из Ga2 проводится ребро (дуга) (bu Ь2). 7. Разность. где Е = {[хь хг)\ *ь *2 е ЛГЛАГг л [хь х2] е Е\ л [хь х2] ££2}- 8. Удаление вершины. В результате поддается подграф, содержащий все ребра, инцидентные множеству Л\{х/}. 9. Удаление ребра (рис. 24). Удаляется ребро, но при этом сохраняются концевые вершины, получается частный подграф. G1\G2 = G(Xl\X2,E), G(X,E)\{Xi}. G\{et}. => Рис. 24. Удаление ребра графа 10. Добавление вершины. G(Xь £1) + {х} = ОДU {*}, Е = Ех), {х} 11. Добавление ребра. G(X\, Е,) + {е} = ОД £ = £iU{e}), {e}tEx. Радиус и диаметр графа Обозначим через d(а, Ь) длину (число ребер или дуг) крат- чайшего маршрута между вершинами а и Ъ. Для d(а, Ь) справедливы следующие утверждения: 1) d(а, а) - 0; 2) d(«, b) > 0; 3) d(a, 6) = 0 => а = Ъ. Для неорграфа расстояния симметричны: 4)d(a, b) = d(b, a); 5) d(a, 6) < d(a, с) + d(c, 6). Пример (рис. 25) Рассмотрим вершину xf. d(xb х2) = d(xb х4) = d(xb xs) = 1, d(xb x3) = 2, max d(xi, x,) = d(xi, *з) = 2. х , е Х Рис. 25. Пример графа Для каждой вершины xt существует максимальный крат- чайший маршрут до некоторой вершины Xj, он называется экс- центриситетом вершины и обозначается е(хг). Максимальный из всех эксцентриситетов графа - это диа- метр графа: D(G) = шах е(х,). Пример варианта задания Рассчитать радиус и диаметр для графа, построенного на основе карты Республики Беларусь (рис. 26) и таблицы расстояний (табл. 4). Gmwwhck Российская Федерация КоийКК) Рис. 26. Карта Республики Беларусь По карте можно построить граф (рис. 27), а по графу можно построить матрицу смежности, а затем рассчитать нужные параметры (рис. 28). Рис. 27. Граф, построенный по карте Республики Беларусь Таблица 4 Таблица расстояний Название города Минск Гродно Витебск Могилев Гомель Брест Минск 00 260 275 203 291 Гродно 260 00 340 463 269 Витебск 275 340 00 163 340 Могилев 203 463 163 00 177 Гомель 291 ШяшШщ 1 340 177 00 536 Брест 342 269 617 Ч 545 536 00 00 260 275 203 291 342N е(1): = 342; 260 00 340 463 551 269 е(2) -551; 275 340 00 163 340 617 е(3) = 617; d(G) = 617; 203 463 163 оо 177 545 е(4) = 545; r(G) = 342; 291 551 340 177 оо 536 е(5) = 551; 342 269 617 536 536 00 У е(6) = 617; Рис. 28. Матрица расстояний Контрольные вопросы 1. Радиус графа. 2. Диаметр графа. 3. Операции над графами. 4. Операции удаления вершины, удаления ребра, разбиения ребра. Лабораторная работа № 10 ПАРОСОЧЕТАНИЯ МАКСИМАЛЬНОЙ МОЩНОСТИ Цель работы: приобрести и закрепить навыки построения паросочетания максимальной мощности при помощи алго- ритма Эдмансона. Методические указания Алгоритм ЭДМАНСОНА построения паросочетания максимальной мощности Шаг 1. Определение начальных условий. Обозначить рас- сматриваемый граф через Go. Выбрать любое паросочетание Мо графа Go. Все открытые вершины считать неисследованными. Положить г: = 0. Шаг 2. Исследование открытой вершины. Если в графе G, имеется только одна неисследованная открытая вершина, то перейти к шагу 6, в противном случае выбрать любую неисследованную открытую для паросочетания Mi вершину v и построить чередую- щееся дерево с корнем в этой вершине. Если при построении этого дерева найдена увеличивающаяся чередующаяся цепь, то перейти к шагу 3, если обнаружен нечетный цикл, перейти к шагу 4, если алгоритм привел к построению венгерского дерева, то перейти к шагу 5. Шаг 3. Обработка увеличивающейся цепи. Этот шаг выполняется только после того, как с помощью алгоритма построения чередующегося дерева получена увеличивающаяся чередующаяся цепь. Исключить из паросочетания А/, ребра, входящие в найденную цепь, и включить ранее не входившие в него ребра этой цепи. В результате мощность паро- сочетания возрастет на единицу, а вершина v стано- вится вершиной паросочетания. Шаг 4. Обработка нечетного цикла. Этот шаг выполняется только после того, как с помощью алгоритма построения чередующегося дерева получен нечетный цикл. Положить /: = /'+ 1. Найденный не- четный цикл обозначить Gt. Построить новый граф Gj, в котором нечетный цикл Gt заменен одной вершиной ai, а все ребра, инцидентные вершинам цикла Gj графа G,-.ь становятся инцидентными вершине а, графа Gt. В остальном графы G, и G,.i совпадают. Переходим к шагу 2, выбирая для исследования в качестве открытой вершины отображение вершины vb графе Gt. Шаг 5. Обработка венгерского дерева. Этот шаг выполняется только после того, как с помощью алгоритма построения чередующегося дерева построено венгерское дерево. Считать вершину v (корень дерева) просмотренной, вернуться к шагу 2. Шаг 6. Восстановление стянутых в вершину нечетных циклов. Этот шаг выполняется только после того, как все открытые вершины (кроме одной) графа G, просмотрены или стали инцидентными ребрам паросочетания. При этом в результате повторения шага 4 получена последовательность графов G b G2,...,Gt И последовательность фиктивных вершин а\, а2, ..., at. Для каждого графа Gh i = 1, t было получено паросочетание Mi, i = 1, t. Обозначим через M*i паросочетание максимальной мощности для графа G,. Для графа Gt паросочетанием максимальной мощности яв- ляется Mt, т.е. M*t - Mt. Для графа Gt.\ паросочетание максимальной мощности M*t-1 строим следующим образом: а) если фиктивная вершина at не является вершиной паро- сочетания М% то M*t-1 включает все ребра паросочетания M*t плюс любое сочетание несмежных между собой ребер из Gt с учетом условия, чтобы открытой осталась лишь одна вершина этого цикла; б) если фиктивная вершина яг является вершиной паросочетания М% то M*t-1 включает все ребра паросо- четания M*t плюс любое сочетание несмежных между собой ребер из Gt, которые инцидентны всем открытым относи- тельно M*t вершинам этого цикла. Паросочетания максимальной мощности M*t-2, M*t-3, М* 0 строятся последовательно, аналогично построению паросочетания M*t-1. Пример решения Найти паросочетания максимальной мощности для графа, представленного на рис. 29. Шаг 1. Граф обозначим Go, выбираем паросочетание Мо (ребра этого паросочетания на рис. 29 обозначены буквой М), i:= 0. Шаг 2. Для исследования выбираем открытую вершину а. Строим чередующееся дерево: помечаем а как внешнюю; окрашиваем в оранжевый цвет ребра (а, d) и (d, b). Вершину d помечаем как внутреннюю, Ъ - как внешнюю. Окрашиваем в оранжевый цвет ребро (а, Ь), в результате чего получаем нечетный оранжевый цикл {(a, d), (d, b), (а, b)}. Переходим к шагу 4. Шаг 4. /:= / + 1. Строим граф G\ (рис. 30). Переходим к шагу 2. Шаг 2. Для исследования выбираем вершину а\ как отображение в графе G\ рассматриваемой на предыдущем шаге вершины а графа Go- В соответствии с алгоритмом построения чередующегося дерева помечаем а\ как внешнюю, выбираем ребро (а\, с), с - открытая непомеченная, следовательно, найдена увеличивающаяся цепь из одного ребра (сц, с). Переходим к шагу 3. Шаг 3. К паросочетанию М\ графа G\ добавляем ребро (а и с). Переходим к шагу 2. Шаг 2. Для просмотра выбираем вершину g и строим чередующееся дерево. Помечаем g как внешнюю, окрашиваем в оранжевый цвет ребра (g, И) и (h, f j . Вершину h помечаем как внутреннюю, / - как внешнюю. Выбираем и окрашиваем в оранжевый цвет ребро ( f , i). В результате найдена чередующаяся цепь {(g, h), (h,J), ( f , /)}. Переходим к шагу 3. Шаг 3. Из паросочетания исключаем ребро (h, f ) и включаем в него ребра (g, И)и i f , i). Переходим к шагу 2. Шаг 2. Открытой является единственная вершина е. Переходим к шагу 6. Шаг 6. Паросочетание максимальной мощности М* 1 для графа G\ показано на рис. 30, д. Преобразовываем вершину а\ в исходный для нее нечетный цикл. Из трех вершин а, Ъ и d вершина b является вершиной паросочетания. Следовательно, в искомое паросочетание включаем ребро (a, d). Задача решена. Пример варианта задания Найти паросочетание максимальной мощности с помощью алгоритма Эдмонса. Рис. 31. Паросочетание Примечание. Паросочетание М - выделено штрихпунк- тирной линией. Контрольные вопросы 1. Определение паросочетаний в графе и их разновид- ностей. 2. Определение двудольного графа. 3. Алгоритм выбора наибольшего паросочетания в двудоль- ном графе. ПРИЛОЖЕНИЯ ПРИЛОЖЕНИЕ А Индивидуальное задание 1. Составить три множества из букв «Фамилии Имени Отчества» студента. 2. Представить полученные множества в виде кругов Эйлера. 3. Представить буквы множеств «Фамилия Имя Отчество» в двоичной системе. 4. Представить диаграмму Вена. 5. Построить СНДФ из букв множеств «Фамилия Имя Отчество». 6. Определить классы толерантности. 7. Представить карту и матрицу толерантности. 8. Построить граф отношения. Пример решения Составить множества из букв «Фамилии Имени Отчества». МОРОЗОВ ОЛЕГ ЕВГЕНЬЕВИЧ Ф = { М, О, Р, 3, В }; И = { О, Л, Е, Г }; О = { Е, В, Г, Н, Ь, И, Ч }; Круги Эйлера Буквы алфавита в двоичной системе А 00001 л 01011 ц 10110 Б 00010 м 01100 ч 10111 В 00011 н 01101 ш 11000 Г 00100 0 01110 щ 11001 Д 00101 п 01111 ъ 11010 Е 00110 р 10000 ы 11011 Ж 00111 с 10001 ь 11100 3 01000 т 10010 э 11101 И 01001 У 10011 ю 11110 к 01010 ф 10100 я 11111 X 10101 Буквы ФИО в двоичной системе М о р 3 в о л £ г Е в Г Н ь и ч 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 3 л 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1 0 8 F2 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 10 F3 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 8 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 6 СНДФ из букв ФИО xl х2 хЪ х4 F1 F2 F3 0. 0 0 0 0 1 1 0 1. 0 0 0 1 1 1 1 2. 0 0 1 0 0 0 0 3. 0 0 1 1 1 0 0 4. 0 1 0 0 0 0 1 5. 0 1 0 1 1 1 1 6. 0 1 1 0 1 0 1 7. 0 1 1 1 0 1 1 8. 1 0 0 0 0 1 0 9. 1 0 0 1 0 1 1 10. 1 0 1 0 0 0 1 11. 1 0 1 1 0 1 0 ! 12. 1 1 0 0 1 1 0 13. 1 1 0 1 1 1 0 14. 1 1 1 0 1 0 0 15. 1 1 1 1 0 1 1 F1 — х 1x2x3x4 U х 1x2x3x4 U х 1x2x3x4 U xlx2x3x4 U U xlx2x3x4 U х 1x2x3x4 U х 1x2x3x4 U xlx2x3x4 F2 =xlx2x3x4 U xlx2x3x4 U xlx2x3x4 U xlx2x3x4 U и х 1x2x3x4 и х 1x2x3x4 U xlx2x3x4 U xlx2x3x4 U U xlx2x3x4 U х1x2x3x4 F3 = х 1x2x3x4 U xlx2x3x4 U xlx2x3x4 U xlx2x3x4 U U xlx2x3x4 U х 1x2x3x4 U xlx2x3x4 U xlx2x3x4 Диаграммы Вена F1 F3 Анализ F на толерантность и эквивалентность xl х2 хЗ х4 х5 хб х7 х8 х9 х10 xl l х12 х13 х14 дс15 аЛ_ а2 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 аЗ 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 6 7 0 4 1 7 5 3 2 3 1 2 6 6 4 #1 = {a l ,a2} Я6 = { al, а2, аЗ } Я11 = {аЗ} т = { al, a2, a3 } 111 = {al, аЗ } Я12 = {а2} /73 = { 0 } т = { а.2, аЗ } Я13 = { al, а2} Н4 = { a l } Н9 = {а2} Я14 = {al, а2} Я5 = {аЗ} я ю = {а2, аЗ } Я15 = { a l } L1 = {xl ,x2, х4, хб, х7, х13,х14, х15 } L2 = {x l ,x2 ,x8 ,x9 ,x l0 ,x l2 ,x l3 ,x l4 } L3 = { х2, х5, хб, xl, х8, xlO, xl 1} Классы эквивалентности М 1 = { x l , x l 3 , x l 4 } М5 = {xl} М2 = {х2,х6} М6 = {х8, xlO} М 3 = {х4,х15 } М7= {х9,х12 } М 4 = {x5 ,x l l } Классы толерантности К\=М\ U Ml U МЗ U М5 К2 - Ml (J М2 U Мб U Ml КЗ = М2 U М4 U М5 U Мб Матрица эквивалентности Mi Мг Ms Мл }Ms ' Ms » Мг Карта отношения толерантности XI XI3 JCH Х2 Xf Xt JOi Л'5 xu XI xs хы X9 хш XI 1 1 1 хм 1 1 1 ДГ14 1 1 1 ЛИ 1 1 Xt 1 1 Х4 1 1 XiS L 1 xs 1 1 ха 1 1 Х7 1 XS 1 1 хш 1 1 X9 1 1 XII 1 1 Граф отношения толерантности xl* х2 • хЗ • • a l х4 • х5 • хб • х7 • х8» • a2 х9 • л:10 • дс11 • х12 • jc13 • • a3 х14 • х15» ПРИЛОЖЕНИЕ Б Основные определения теории графов Часть 1. Для всех специальностей 1. Теория графов - математический язык для формализо- ванного определения понятий, связанных с анализом и синтезом структур, систем и процессов. 2. Граф - пара G-(V, Е), где V - непустое множество, задаваемое вершинами, а Е — множество пар et = (v,/, v^), которые задают ребра. V называется множеством вершин, а Е - множеством ребер. 3. Вершина графа - элемент множества вершин графа, 4. Ребро графа - элемент множества ребер графа. 5. Дуга - ориентированное ребро. 6. Число вершин - мощность множества вершинр = | FJ. 7. Число ребер - мощность множества ребер q = \Е\ 8. Смежными называются две вершины, если сущест- вует соединяющее их ребро. 9. Смежными называются ребра, если они опираются на общую вершину. 10. Инцидентными называются вершина графа v и некото- рое его ребро е, если е = (v, w) или е = (w, v), где w - некоторая вершина графа. 11. Петля - ребро, инцидентное одной вершине (единст- венной). Может быть несколько петель. 12. Орграф (ориентированный граф) - граф, ребра которо- го имеют некоторое направление. 13. Неограф (неориентированный граф) - граф, ребра которого не имеют направления (двусторонние). 14. Мультиграф - граф, содержащий мультиребра или петли. 15. Висячее ребро - ребро, инцидентное висячей вершине. 16. Мультиребро - множество ребер, инцидентных одной и той же паре вершин (и, v). 17. Степень вершины - число инцидентных ей ребер (обозначается deg(v)). 18. Вес вершины - любое число (действительное, целое или рациональное), которое устанавливается в соответствие данной вершине по каким-либо логическим соображениям. 19. Вес ребра - любое число (действительное, целое или рациональное), которое устанавливается в соответствие данной вершине по каким-либо логическим соображениям. 20. Регулярным называется граф, если степени всех его вершин одинаковы. 21. Цепь в графе G - {V, Е) - последовательность вершин vo, vi, ...v„ - такая, что п> 0 и v„ v7 соединены ребром. Если вершины, входящие в цепь, различны, то цепь - простая, иначе - составная. 22. Цикл - замкнутая цепь. 23. Обход графа - цикл, проходящий через все вершины графа по одному разу. 24. Связный граф - граф, в котором из любой вершины можно найти цепь в любую другую вершину. Несвязный граф распадается на компоненты связности (максимальные связные подграфы). 25. Корень - обычно так называют специально выделен- ную по тем или иным причинам вершину дерева. 26. Обыкновенный граф - граф, не содержащий мульти- ребер и петель. 27. Полный граф - это обыкновенный граф G = (V, Е), в котором любая пара вершин смежна. Обозначается Кр, где P = \V\, при этом \Е\ =р(р-1)/2. 28. Ациклический граф (лес) - обыкновенный граф без циклов. 29. Дерево - связный ациклический граф. 30. Полный двудольный граф - двудольный граф G = (А\, А2, Е), у которого любая пара вершин х е А\ и у е А2 смежна. Обозначается Кщп, где т = \А\\, п = \А2\, \Е\ = т х п. 31. Граф-звезда - полный двудольный граф K\t„. 32. Эйлеров граф - связный граф, не содержащий вершин нечетной степени. 33. Матрица расстояний (кратчайших цепей) графа G - квадратная матрица D = {dy}, в которой элемент dy=r(Xj, xj), т.е. численно равен расстоянию от вершины xt до вершины х, в графе G. 34. Изоморфизм графов. Два графа G = {X, U)vlL = (X', Щ изоморфны, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохра- няющие смежность и ориентацию для дуг. 35. Остов графа (остовное дерево, покрывающее дерево, каркас) - суграф графа G, не содержащий циклов и имеющий столько же компонент связности, что и G. 36. Сильная компонента орграфа G - максимальный подграф орграфа G, в котором любая пара вершин сильно связна. 37. Маршрут или путь - чередующаяся последователь- ность хь щ, хг, и2, ..., Хк вершин х, и ребер и„ обладающая тем свойством, что любая пара соседних элементов инцидентна. 38. Цепь - маршрут, в котором все ребра различны. 39. Простая цепь - цепь, в которой все вершины различны. 40. Цикл - цепь, у которой начальная и конечная вершины совпадают. 41. Простой цикл - простая цепь, у которой концевые вершины совпадают. 42. Ориентированная цепь - цепь орграфа G, в которой ориентация дуг (ребер) совпадает. 43. Контур - ориентированная цепь, у которой начальная и конечная вершины совпадают. 44. Эйлерова цепь - цепь, содержащая все ребра графа в точности один раз. 45. Эйлеров цикл - эйлерова цепь, у которой начальная и конечная вершины совпадают. 46. Гамильтонова цепь - простая цепь, которая содержит все вершины графа. 47. Гамильтонов цикл - гамильтонова цепь, у которой начальная и конечная вершины совпадают. 48. Взвешенный граф - граф, вершинам и/или (обычно) ребрам которого поставлены в соответствие целые или вещественные числа (веса). 49. Вес (длина) - значение числа, поставленного в соответ- ствие взвешенному элементу. 50. Планарный граф - граф, для которого можно постро- ить укладку на плоскости без пересечений ребер. Часть 2. Для специальностей 1-55 01 01 «Интеллектуаль- ные системы» и 1-55 01 03 «Компьютерная мехатроника» 51. Эксцентриситет вершины - максимальное расстояние от v до других вершин графа. 52. Диаметр графа - максимальный эксцентриситет его вершин. 53. Радиус графа - наименьший из эксцентриситетов его вершин. 54. Центральная вершина - вершина, эксцентриситет которой равен радиусу. 55. Периферийная вершина - вершина, эксцентриситет которой равен диаметру. 56. Цикломатическое число графа r|(G) - наименьшее число ребер, удаление которых оставляет граф без циклов, образуя остов (каркас) графа. 57. Удаление вершины. Из графа удаляется вершина вме- сте с инцидентными ребрами. 58. Добавление вершины. К заданному множеству вершин (х\, хг,..., хк) добавляется новая вершина^, смежная с хь х2>..., хь 59. Стягивание вершин. Заданное множество вершин объединяется в одну вершину, а полученные петли удаляются. 60. Удаление (ребра) дуги. В графе удаляется ребро без инцидентных вершин. 61. Добавление ребра (дуги). Для заданной пары вершин х, у добавляется ребро (х, у). 62. Стягивание ребра (дуги) - вершины х и у, инцидентные заданному ребру, стягиваются. 63. «-раскрашиваемый граф - граф G, у которого хроматическое число X(G) = п. 64. Сильносвязный орграф (сильный орграф) (strongly connected graph) - орграф, у которого любые две вершины взаимодостижимы. 65. Односторонне связный орграф (односторонний орг- раф) - орграф, у которого любая пара вершин односторонне связна. 66. Слабосвязный орграф (слабый орграф) - орграф, который после дезориентации дуг будет связным. 67. Однородный или регулярный (Лг-регулярный) граф - граф, все вершины которого имеют одну и ту же степень, равную к. 68. Число вершинной связности графа G - наименьшее число вершин, удаление которых приводит к несвязному графу. 69. Число реберной связности графа G - наименьшее число ребер, удаление которых приводит к несвязному графу. 70. Хроматическое число (chromatic number) X(G) - наименьшее число п, для которого граф G имеет я-раскраску. 71. Укладка графа на поверхность S в трехмерном эвкли- довом пространстве - построение изоморфного G графа L, лежащего на S вершинами (точками), ребрами (непрерывными линиями конечной длины) и дугами (ориентированными линиями конечной длины), причем линии на поверхности S не пересекаются. 72. Раскраска (вершинная) - приписывание цветов (нату- ральных чисел) вершинам графа, такое, что никакие две смежные вершины не получают одинаковые цвета (числа). 73. и-раскраска - раскраска, в которой используется п цветов. 74. Раскраска реберная - приписывание цветов ребрам графа, такое, что никакие два смежных ребра не получают одинакового цвета. 75. и-раскраска реберная - раскраска ребер, использую- щая точно п цветов. 76. Полная раскраска - раскраска вершин графа, такая, что для любых двух цветов найдутся две смежные вершины, окрашенные в эти цвета. 77. Генерация графов - процедура построения графов. 78. Объединение графов (помеченных графов) G\ = (Х\, U\) и G2=(X2, U2) - граф G1UG2, множеством вершин которого являетсяХ=Х\ UX2, а множеством ребер U= Lri U U2. 79. Пересечение графов (помеченных графов) G\ - (Х\, U\) и G2 — (Х2, U2) - граф GiflG2, множеством вершин которого является Х-Х\ Г\Х2, а множеством ребер U= U\f]U2, где U\ и U2 - множество неупорядоченных пар вершин. 80. Соединение графов G\ = (Х\, U\) и G2 = (Х2, Ui), таких, что Xi f]X2 = Ж, t/ifl t /2= Ж - граф G] + G2, который состоит из G\ U G2V)K{X\, Xi), где К(Х\, Х2) - полный двудольный граф с множеством вершин Х\ и Х2 в долях. 81. Сумма графов Gj = (X\, U\) и G2=(X2, U2) - граф G]®G2, состоящий из множества вершин Х=Х\(ВХ2 и две вершины 5 = (хь х2) и t = (yh у2) (s, t е X, хи yi е Хи х2, у2 е Х2) смежны в GI®G2 тогда и только тогда, когда х\=у\ и х2 смежна с у2 или х2 - у2 и х2 смежна с у\. 82. Симметрическая разность графов G\ и G2 - граф GiVG2 = G iUG 2 -G , r iG 2 . 83. Разность графов (помеченных графов) - граф G\-G2,, который получается из Gi удалением элементов, соответст- вующих графу G2. 84. Композиция графов (лексикографическое произве- дение графов) Gi = (Xh Ui) и G2 = (Х2, U2) - граф G = Gi[G2], состоящий из множества вершин Х=Х\®Х2, и две вершины s = (хь хг) и t = (уи у2) смежны в G тогда и только тогда, когда xi смежна с у\ или х\ и х2 смежна с уг- 85. Разрез (сечение графа) - множество элементов, удале- ние которых увеличивает число компонент (односторонних компонент, слабых компонент) связности графа. 86. Простой разрез - разрез, у которого любое собственное подмножество элементов не является разрезом. 87. Смешанный разрез - разрез, элементами которого выступают как ребра (дуги), так и вершины. 88. Реберный разрез - все элементы разреза ребра (дуги). 89. Вершинный разрез. Все элементы разреза - вершины. 90. (s, 0-разрез _ разрез, при удалении которого вершина t не достижима из s. 91. Минимальный разрез - разрез с наименьшим числом элементов. 92. Минимальная цепь - (s, 0-цепь с минимальным чис- лом ребер. 93. Максимальный разрез - разрез с наибольшим числом элементов среди всех простых разрезов графа. 94. Максимальная цепь - простая (s, /)-цепь с максималь- но возможным числом ребер. 95. Максимальное паросочетание - паросочетание с максимально возможным числом ребер в паросочетания данного графа (числом реберной независимости). 96. Фундаментальный цикл (контур) - цикл, определяе- мый некоторым остовом и хордой графа (орграфа). 97. Одноцветный класс - множество всех вершин одного цвета. 98. Наибольшее паросочетание - паросочетание с наи- большей величиной. 99. Хорда - ребро графа, не принадлежащее остову. ЛИТЕРАТУРА Основная 1. Басакер, Р. Конечные графы и сети / Р. Басакер, Т. Са- ати. - М.: Наука, 1997. 2. Иванов, Б.Н. Дискретная математика / Б.Н. Иванов. - М.: Лаборатория Базовых Знаний, 2001. 3.Кузнецов, О.М. Дискретная математика для инженера/ О.М. Кузнецов, Г.М. Адельсон-Вельский. - М.: Энерго- атомиздат, 1988. - 480 с. 4. Лихтарников, Л.М. Математическая логика: курс лек- ций/ Л.М. Лихтарников, В.М.Сукачева. - СПб.: Лань, 1998.-288 с. 5. Никольская, И.Л. Знакомство с математической логи- кой / И.Л. Никольская. - М.: Флита, 1998. 6. Новиков, Ф.А. Дискретная математика для программи- стов / Ф.А. Новиков. - СПб.: Питер, 2000. - 304 с. 7. Пономарев, В.Ф. Дискретная математика для информати- ков-экономистов: учебное пособие/ В.Ф. Пономарев. - Калининград: КГТУ и КИМБ, 2002. - 239 с. 8. Редькин, Н.П. Дискретная математика: курс лекций для сту- дентов-механиков / НЛ. Редькин. - СПб.: Лань, 2003. - 96 с. 9. Сачков, В.Н. Введение в комбинаторные методы дис- кретной математики / В.Н. Сачков. - М . : Наука, 1982.- 384 с. 10. Судоплатов, С.В. Элементы дискретной математики: учебник/ С.В. Судоплатов, Е.В.Овчинникова.- М.: ИНФРА-М; Изд-во НГТУ, 2002. - 280с. 11. Уилсон, Р. Введение в теорию графов / Р. Уилсон. - М.: Мир, 1977. 12.Яблонский, С.В. Введение в дискретную математику/ С.В. Яблонский. - М . : Наука, 1986. Дополнительная 1. Грей, П. Логика, алгебра и базы данных / П. Грей. - М.: Машиностроение, 1989. - 360 с. 2. Иванов, Б.Н. Дискретная математика. Алгоритмы и про- граммы / Б.Н. Иванов. - 2-е изд. - М.: Едиториал УРСС, 2003.-296 с. 3. Кириллов, В.И. Логика / В.И. Кириллов, А.А. Стар- ченко. - М.: Высшая школа, 1987. 4. Кук, Д. Компьютерная математика / Д. Кук, Г. Бейз. - М.: Наука, 1990. - 384 с. 5. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. - М.: Физматлиз, 2001. - 255 с. 6. Мендельсон, Э. Введение в математическую логику / Э. Мендельсон. - М . : Наука, 1984. 7. Непейвода, Н.Н. Прикладная логика: учебное посо- бие / Н.Н. Непейвода. - 2-е изд., испр. и доп. - Новоси- бирск: Изд-во Новосиб. ун-та, 2000. - 521 с. 8. Новиков, Ф.А. Дискретная математика / Ф.А. Новиков. СПб.: Питер, 2001. 9. Сачков, В.Н. Введение в комбинаторные методы дис- кретной математики / В.Н. Сачков. - М.: Наука, 1982. 10. Харари, Ф. Теория графов/ Ф. Харари; под ред. Г.П. Гаврилова. - М . : Мир, 1973. СОДЕРЖАНИЕ ВВЕДЕНИЕ 3 ЛАБОРАТОРНЫЕ РАБОТЫ 8 Лабораторная работа № 1. МАТЕМАТИЧЕСКАЯ ЛОГИКА... 8 Лабораторная работа № 2. ЛОГИЧЕСКИЕ ОПЕРАЦИИ 13 Лабораторная работа № 3. ТЕОРИЯ МНОЖЕСТВ 16 Лабораторная работа № 4. КОМБИНАТОРИКА 20 Лабораторная работа № 5. ПРЕДСТАВЛЕНИЕ ГРАФОВ В ВИДЕ МАТРИЦ 24 Лабораторная работа № 6. ПУТИ В ГРАФАХ 28 Лабораторная работа № 7. ПОТОКИ В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ И ТРАНСПОРТНЫХ СИСТЕМАХ 33 Лабораторная работа № 8. ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ 38 Лабораторная работа № 9. ОПЕРАЦИИ НАД ГРАФАМИ. РАДИУС И ДИАМЕТР ГРАФА 43 Лабораторная работа № 10. ПАРОСОЧЕТАНИЯ МАКСИМАЛЬНОЙ МОЩНОСТИ 51 ПРИЛОЖЕНИЯ 57 ЛИТЕРАТУРА 71 Учебное издание БОХАН Сергей Гавриилович ПАРМОН Светлана Ивановна ДИСКРЕТНАЯ МАТЕМАТИКА Методическое пособие по лабораторным работам для студентов машиностроительного факультета специальностей 1-55 01 01 «Интеллектуальные приборы, машины и производства», 1-55 01 03 «Компьютерная мехатроника», 1-36 01 01 «Технология машиностроения», 1-36 01 04 «Оборудование и технологии высокоэффективных процессов обработки материалов», 1-53 01 01 «Автоматизация технологических процессов и производств» В 2 частях Часть 1 Редактор Т.А. Подолякова Компьютерная верстка Д.А. Исаева Подписано в печать 27.10.2010. Формат 60x84 '/16. Бумага офсетная. Отпечатано на ризографе. Гарнитура Тайме. Усл. печ. л. 4,30. Уч.-изд. л. 3,37. Тираж 100. Заказ 399. Издатель и полиграфическое исполнение: Белорусский национальный технический университет. ЛИ № 02330/0494349 от 16.03.2009. Проспект Независимости, 65. 220013, Минск.