ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Уфимский государственный авиационный технический университет

 

Бронштейн Е.М.

 

ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

 

Учебное пособие

 

Уфа – 2011

 

УДК

ББК

Б88

 

Рецензенты:

доктор физ.-мат. наук, проф.

доктор физ.-мат. наук, проф.

Бронштейн Е.М.

Основы дискретной математики, учебное пособие / Е.М.Бронштейн; Уфимск. гос. авиац. Техн. Ун-т. – Уфа, УГАТУ, 2010. – 79 с.

ISBN

 

Пособие основано на курсе лекций для студентов специальности «Математические методы в экономике». В пособие включен конспект лекций и задачи, как для практических занятий, так и для самостоятельной работы, по темам: «Комбинаторика», «Теория множеств», «Теория графов». Включены список рекомендованной литературы с комментариями, перечень терминов, в конце разделов приведены вопросы для самоконтроля. Может использоваться студентами математических, экономических направлений и направлений, связанных с информатикой.

 

Табл.:2; Ил.: 2; Библиогр.: 16 назв.

 

УДК

ББК

 

 

ISBN© Уфимский

государственный авиационный

технический университет, 2011

 

Оглавление

Оглавление. 3

Введение. 5

1. Комбинаторика в задачах. 6

1.1 Основной принцип комбинаторики. 6

1.2 Размещения с повторениями. 6

1.3 Размещения без повторений. 7

1.4 Перестановки. 8

1.5 Сочетания (без повторений) 8

1.6 Свойства биномиальных коэффициентов. 9

1.7 Разбиения множеств. 9

1.8 Сочетания с повторениями. 10

1.9 Разные задачи. 10

1.10 Производящие функции. 12

1.11 Использование рекуррентных соотношений. 13

1.12 Формула включений и исключений. 14

1.13 Комбинаторные величины при больших значениях параметров 15

2 Множества и функции. 15

2.1 Множества и простейшие операции над ними. 16

2.2 Булеан множества. 20

2.3 Прямое произведение множеств. 21

2.4 Отношения на множествах. 22

2.5 Отображения (функции) 26

2.6 Мощность множеств. 30

2.7 Счетные множества. 35

2.8 Некоторые свойства бесконечных множеств. 37

2.9 Вопросы для самопроверки. 39

2.10 Упражнения. 40

3 Основы теории графов. 44

3.1 Основные понятия. 44

3.2 Компьютерные представления графов. 46

3.3 Маршруты и связность. 48

3.4 Кратчайшие пути в графах. 49

3.5 Деревья. 52

3.6 Кодирование деревьев. 54

3.7 Центр дерева. 54

3.8 Минимальное остовное дерево (остов) 55

3.9 Эйлеровы графы.. 56

3.10 Гамильтоновы графы.. 58

3.11 Графовые векторы.. 60

3.12 Паросочетания и реберные покрытия. 62

3.13 Паросочетания в двудольных графах. 64

3.14 Правильная нумерация вершин графа. 66

3.15 Сетевые графики. 67

3.16 Потоки в сетях. 68

3.17 Вопросы для самопроверки. 71

3.18 Упражнения. 72

Рекомендуемая литература. 75

Предметный указатель. 76

 

Введение

 

В пособии излагается краткий курс дискретной математики для студентов специальности «Математические методы в экономике». Курс состоит из трех разделов. Особенность первого раздела «Комбинаторика в задачах» состоит в том, что теоретические результаты возникают в процессе решения циклов задач, практика показала эффективность такого подхода. Второй раздел «Множества и функции» начинается с самых элементарных сведений об операциях над множествами, заканчивается при этом глубокими результатами, в частности, теоремой о несуществовании множества максимальной мощности. Второй и третий разделы сопровождаются вопросами для самопроверки и упражнениями.

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

Следует иметь в виду, что дискретная математика – математическая дисциплина, кардинально отличающаяся от математического анализа или линейной алгебры: ее предметом являются объекты, «отделимые» друг от друга. Например, какое вещественное число является соседним с 1? Такого нет! А такое натуральное число есть (это, как всем понятно, 2). Методы дискретной математики также весьма специфичны, очень поучительны и элегантны. Изучение этой дисциплины, надеюсь, доставит удовольствие любому заинтересованному читателю. Алгоритмы теории графов широко применяются при решении различных практических задач.

 

Комбинаторика в задачах

 

В этом разделе все рассматриваемые числа целые неотрицательные (0,1,2,…).

 

Основной принцип комбинаторики

1.1.1 . От Москвы до Уфы можно добраться поездом, самолетом или теплоходом, а от Уфы до Чишмов – поездом, автобусом или на такси. Сколькими… 1.1.2 . На почте продаются конверты без марок 5 видов, марки 10 видов по 1… 1.1.3 . Сколькими способами можно выбрать на шахматной доске одну черную и одну белую клетки? А так, чтобы они не…

Размещения с повторениями

1.2.1 . Замок в автоматической камере хранения состоит из 4 дисков, на каждом из которых написаны буквы а, б, в, г, д, е. Сколько различных кодов… 1.2.2 . В группе из 25 человек разыгрываются три приза, причем призы… 1.2.3 . В пачке 20 экзаменационных билетов. Экзамен организован следующим (достаточно странным!) образом. Студент…

Размещения без повторений

1.3.1 . Сколько словарей следует издать, чтобы можно было переводить тексты непосредственно с любого из шести языков на каждый из них? А если языков… 1.3.2 . Каков ответ в задаче 1.2.2, если каждый студент не может получить… 1.3.3 . Каков ответ в задаче 1.2.3, если билеты в пачку не возвращаются?

Перестановки

1.4.1 .Сколькими способами могут встать в очередь 10 человек? 1.4.2 . Каков ответ в задаче 1.3.3, если студентов 20? 1.4.3 . Каков ответ в задаче 1.3.4, если различных стульев 10?

Сочетания (без повторений)

1.5.1 .В шахматном турнире участвовали 10 человек. Сколько состоялось партий, если каждая пара игроков встретилась один раз? 1.5.2 .Из колоды карт (36 штук) игрок получает 6. Сколько различных наборов он… 1.5.3 .Каков ответ в задаче 1.2.2, если все призы одинаковые?

Свойства биномиальных коэффициентов

1.6.1. Докажите, что . Сделайте это четырьмя способами: по определению, по формуле и используя результаты задач 1.5.6 и 1.5.7. 1.6.2. Докажите, что .

Разбиения множеств

Число сочетаний можно интерпретировать как число способов, которым n-элементное множество можно разбить на два подмножества, в одном из которых… 1.7.1. В группе 25 студентов. 12 из них надо отправить на практику на одно… 1.7.2. Сколькими способами можно расположить в цепочку (переставить) 12 предметов трех типов, если предметов каждого…

Сочетания с повторениями

1.8.1. В магазине продаются карандаши двух видов. Сколькими способами можно купить пять штук? А если надо купить 8 карандашей 4 видов? 1.8.2. Каков ответ в задаче 1.2.4, если стулья одинаковые? 1.8.3. Сколько решений в целых неотрицательных числах имеет уравнение (Сравните с предыдущей задачей)

Разные задачи

В предыдущих параграфах вы познакомились с основными приемами элементарной комбинаторики. В этом параграфе эти приемы (или их комбинации)… 1.9.1. Сколько существует трехцветных флагов, состоящих из горизонтальных… 1.9.2. Для покраски помещения необходимо выбрать краски 3 цветов, при этом всего имеется краска семи цветов.…

Производящие функции

По биному Ньютона (задача 1.5.7) коэффициентами многочлена являются величины . 1.10.1. Каков смысл коэффициентов при zm многочленов  

Использование рекуррентных соотношений

1.11.1. Пусть f(n.m) – число сочетаний с повторениями из n по m (задача 8.4). Проверьте, что 1.11.2. f(n.0)=1, f(n.1)=n, f(n.m)=f(n-1.m)+f(n.m-1) при 1≤m≤… 1.11.3. Пусть An(z)= . Проверьте, что An(z)= An-1(z)/(1-z).

Формула включений и исключений

1.12.1. В группе 25 студентов, 15 занимаются лыжами, 12 – коньками, 8 и тем, и другим. Сколько студентов не занимается этими видами спорта? 1.12.2. (Обобщение) Проверьте, что если A и B – конечные множества, то … 1.12.3. В группе 15 студентов занимаются футболом, 13 – волейболом, 12 – баскетболом, 10 – футболом и волейболом, 11 –…

Комбинаторные величины при больших значениях параметров

1.13.1. Докажите, что при n≥2. 1.13.2. Докажите, что биномиальные коэффициенты возрастают при возрастании… 1.13.3. Проверьте, что .

Множества и функции

 

Множества и простейшие операции над ними

 

С понятием множества каждый сталкивается постоянно. Для нас это первичное понятие, стало быть, дать множеству формальное определение нельзя, можно только пояснить, что имеется в виду. Множество состоит из элементов. Множества мы будем обозначать большими латинскими буквами, элементы – малыми. Здесь есть некоторая несогласованность, поскольку множество может быть и элементом некоторого множества. Множество задано, если про любой объект в мире можно сказать, является он элементом множества или нет. Первое отношение обозначается aÎA, второе – aÏA.

Таким образом, понятие множества имеет двойственную природу: с одной стороны, это нечто единое, с другой состоит из элементов. Важно отметить, что множество ПОЛНОСТЬЮ характеризуется набором своих элементов. Множества совпадают, если каждый элемент одного является элементом другого. Обозначение стандартное: A=B. Если всякий элемент множества A является элементом множества B, то A называется подмножеством B, обозначение: AÌB. Обычно множества изображаются в виде областей на плоскости.

Таким образом, равенство A=B равносильно тому, что одновременно AÌB и BÌA. Роль числа 0 в алгебре множеств (см. далее) играет пустое множествоÆ, т.е. множество, в котором нет элементов. Мы полагаем, что Здесь использован знак , который в математической логике называется квантором всеобщности (читается «для каждого»). Наряду с квантором всеобщности используется квантор существования (читается «существует»). Происхождение этих необычных знаков очень простое: это просто перевернутые первые буквы английских слов All (каждый) и Exist (существует).

Множество может задаваться перечислением его элементов. Обозначается это так: {a.b,c} – множество, состоящее из трех записанных букв. Подчеркнем, что элементы множества должны различаться и поэтому {a.b,a}={a.b}. Как уже отмечалось, множество определяется набором элементов, поэтому, например, {a.b,c}={c,a.b}. Следует различать одноэлементное множество и сам этот элемент. Например, про множество {2} нельзя сказать, что оно четное, а про его единственный элемент, число 2 – можно.

Если известно некоторое более обширное множество, то можно выделить подмножество элементов с некоторым свойством. Поясним это на примере. Используем стандартное обозначение множества натуральных чисел N. {aÎN: bÎN (a=2b)} это множество четных натуральных чисел.

Напомним определения простейших операций над множествами.

Объединением множествA и B называется множество AÈB, , состоящее из элементов, каждый из которых принадлежит хотя бы одному из множеств A,B. Иначе говоря, AÈB={a: aÎA или aÎB}.

Пересечением множествA и B называется множество AÇB, состоящее из элементов, каждый из которых принадлежит обоим множествам A,B, т.е. AÇB={a: aÎA и aÎB}. Иногда путают знаки объединения и пересечения. Запомнить их легко, если заметить, что знак объединения похож на букву U – первую букву английского слова Union – союз, объединение.

Объединение множеств также называется суммой множеств, а пересечение – произведением. Однако аналогия с числами полной не является, как будет видно далее.

Разностью множествA и B называется множество AB, образованное элементами, каждый из которых входит в A и не входит в B, т.е. AB={a: aÎA, aÏB}.

Еще одна операция, которая достаточно широко используется - симметрическая разностьADB=(AB)È(BA)=(AÈB)(AÇB). Докажите последнее равенство! Полезное свойство симметрической разности состоит в том, что ADB=Æ тогда и только тогда, когда A=B.

Часто вводится в рассмотрение универсальное множествоили универсум U. Это в некотором смысле наша вселенная. Для нас не существуют элементы, не входящие в U, т.е. все рассматриваемые множества являются подмножествами U. В этом случае дополнением множестваA называется множество Дополнение является аналогом логической операции отрицания.

Введенные операции на множествах обладают рядом алгебраических свойств. Приведем их.

1. (Коммутативность) AÈB=BÈA, AÇB=BÇA. Эти свойства очевидны.

2. (Ассоциативность) (AÈB)ÈС=AÈ(BÈС). Эти свойства также очевидны. Они позволяют опускать скобки, не опасаясь разночтений.

3. (Дистрибутивность объединения относительно пересечения) (AÈB)ÇС=(AÇС)È(BÇС). Это свойство не столь очевидно. Приведем формальное рассуждение. Пусть aÎ(AÈB)ÇС. По определению пересечения, одновременно aÎAÈB и aÎС. Возможны два случая: aÎA, aÏA. В первом случае aÎA и aÎС. Отсюда, aÎAÇС, т.е. aÎ(AÇС)È(BÇС). Во втором случае из соотношений aÎAÈB и aÏA следует, что aÎB. Отсюда аналогично aÎ BÇС, т.е. aÎ(AÇ С)È(BÇС). Тем самым ВСЕГДА aÎ(AÇС) È(BÇС). Вопрос. Доказано ли нужное свойство? Ответ. Нет. Пока лишь доказано, что (AÈB)ÇСÌ(AÇС)È(BÇС). Для доказательства обратного включения рассмотрим элемент aÎ(AÇС)È(BÇС). Возможны два случая: aÎ(AÇС) и aÏ(AÇС). В первом случае одновременно aÎA (откуда aÎAÈB) и aÎС. Следовательно, в этом случае aÎ(AÈB)ÇС. Во втором случае аналогично предыдущему вытекает принадлежность aÎB (т.е. aÎAÈB), откуда aÎ(AÈB)ÇС. Теперь равенство доказано. Далее формальными рассуждениями мы будем пользоваться редко. Обычно будем пользоваться графической иллюстрацией.

Для графического доказательства множества изобразим на плоскости. Весьма тонким является следующий вопрос. Множества могут иметь различную природу. Верно ли, что рассмотрения множеств на плоскости достаточно для доказательства общих утверждений о множествах? Можно доказать, что для анализа простейших свойств, которые мы сейчас рассматриваем, это так. Надо только множества изображать в общем виде, т.е. так (подобные рисунки иногда называют диаграммами Эйлера – это замечательное имя нам еще встретится!).

 

B

A

C

 

Затем на двух экземплярах такого рисунка следует отметить левую и правую части равенства и убедиться, что множества совпадают.

Свойства 1-3 имеют аналоги для чисел. Но в законе дистрибутивности для чисел знаки сложения и умножения нельзя поменять местами (убедитесь в этом!) А для множеств такой закон справедлив!

4. (Дистрибутивность объединения относительно пересечения) (AÇB)ÈС=(AÈС)Ç(BÈС). Докажите это свойство, используя графическое представление.

5. AÈA=AÇA=A. Эти свойства также не имеют числовых аналогов.

6. AÈÆ=AÇU=A, AÇÆ=Æ, AÈU= U. Отсюда видно, что пустое множество в алгебре множеств выполняет функции числа 0, универсальное множество U числового аналога не имеет.

7. - правило двойного дополнения, в логике его аналог называется правилом двойного отрицания.

8. Законы де Моргана (аналогичны одноименным законам логики). . Эти формулы легче всего проверить на рисунках. Очень наглядно получается! Особенно, если множества расположить так.

9.

U

A

B

. Эти законы являются фундаментальными в логике Аристотеля. Первый называется законом исключенного третьего (по латыни «терциум нон датур» – третьего не дано).

10. (Законы поглощения) AÇ(AÈB)=AÈ(AÇB)=A. Проверьте эти формулы с помощью рисунка! Здесь интересно то обстоятельство, что хотя в левых частях формально присутствует множество B, от него ничего не зависит.

 

Булеан множества

Каждое множество порождает новое множество несколько необычным образом. ОПРЕДЕЛЕНИЕ 1. Булеаном множестваA называется совокупность всех подмножеств… Примеры. (единственный элемент булеана – пустое множество). (у одноэлементного множества два подмножества:…

Прямое произведение множеств

ОПРЕДЕЛЕНИЕ 2. Прямым произведением множествA1, A2,…, An называется множество A1´A2´…´ An={(a1 a2,…,an): a1ÎA1, a2ÎA2,…,… Элементы прямого произведения (a1 a2,…,an) называются векторами или кортежами. Слово «кортеж» вам встречалось,…

Отношения на множествах

ОПРЕДЕЛЕНИЕ 3. n-арным отношением на множествеA называется подмножество G прямого произведения An. Таким образом, n-арное отношение на A это… При n=1 это просто подмножество A,такое отношение называют свойством. Так,… При n=2 отношение называется бинарным, это будет основным объектом рассмотрения в этом параграфе.

Отображения (функции)

С понятием «функция»в некоторых частных случаях вы познакомились в школе. Приведем общее определение. ОПРЕДЕЛЕНИЕ 7. Пусть A, B - множества. Отображением(функцией) f из A в B… Примеры.

Мощность множеств

Речь пойдет о том, как сравнивать между собой разные множества. Начнем с простого примера. Перед вами кучки болтов и гаек. Требуется ответить на… Фактически этой процедурой мы пытались установить взаимно однозначное… ПРЕДЛОЖЕНИЕ.Для того, чтобы между конечными множествамиA и B существовало взаимно однозначное соответствие, необходимо…

Счетные множества

ОПРЕДЕЛЕНИЕ 15. Множество, равномощное множеству N, называется счетным. Иными словами счетными являются такие множества, элементы которых можно… Подтверждением высказанного странного утверждения о «малости» такой бесконечности являются следующие результаты.

Некоторые свойства бесконечных множеств

Уже отмечалось, что конечное множество не равномощно своей части, в то же время, бесконечное множество может быть равномощным своей части.… Теорема 12.Всякое бесконечное множество равномощно некоторой своей части. Доказательство. Пусть A – бесконечное множество. По теореме 9, существует счетное множество . Не исключается случай…

Вопросы для самопроверки

1. Что такое объединение, пересечение, дополнение, симметрическая разность множеств? 2. Какими алгебраическими свойствами обладают операции над множествами? 3. Что такое булеан множества?

Упражнения

1. Существуют ли такие множества A,B,C, что 2. Справедливы ли следующие утверждения для любых A,B,C? А) Если A¹B и B¹ C, то A¹С.

Основы теории графов

 

Основные понятия

 

После путешествия по джунглям бесконечных множеств вернемся к множествам конечным.

Началом рассмотрения графов как самостоятельного объекта считается 1736 год, когда Леонард Эйлер поставил задачу о Кенигсбергских мостах. Примерно через 100 лет (в 1847 году) немецкий физик Густав Роберт Кирхгоф (кстати, уроженец Кенигсберга!) применил подобные конструкции к анализу электрических цепей. Примерно в то же время выдающийся ирландский математик Уильям Роуэн Гамильтон придумал игру, которая по существу сводилась к построению цикла в некотором графе (определения см. далее). Во второй половине 19 века она была столь же популярна, как через век кубик Рубика.

Геометрически граф это семейство точек и соединяющих их линий (или стрелок). Формально граф определяется так.

ОПРЕДЕЛЕНИЕ 16. ГрафомГ называется пара (V,E), где V – конечное множество, E – антирефлексивное бинарное отношение на V. Элементы множества V называются вершинамиграфа, множества E – дугамиили ребрамиграфа. Число вершин обычно обозначается через p, число дуг – через q.

Таким образом, каждая дуга является парой различных вершин графа. Графически дуга изображается стрелочкой.

Если отношение E симметричное, то граф называется неориентированным, в противном случае – ориентированным. В неориентированном графе стрелки не нужны.

Если бинарное отношение на V не является антирефлексивным, то соответствующий объект называется псевдографом. Иногда полезно считать, что некоторые вершины соединяются несколькими дугами. Такой объект называется мультиграфом. Далее мы не используем эти термины.

Вершины a,bÎV называются смежными, если (a,b)ÎE или (b,a)ÎE, т.е. если эти вершины на картинке соединяются дугой.

Дуги графа называются смежными, если у них есть общая вершина (это понятие обычно применяется к неориентированным графам).

Вершина aÎV и дуга (a,b)ÎE или (b,a)ÎE (т.е. если вершина является одним из концов дуги) называются инцидентными.

Граф называется помеченным, если его вершины различимы. Обычно пометки это номера вершин.

Важно выделить те пары графов, которые мы считаем в некотором смысле совпадающими. В теории графов это совпадение называется изоморфизмом.

ОПРЕДЕЛЕНИЕ 17.Графы Г₁=(V₁,E₁) и Г₂=(V₂,E₂) называются изоморфными, если существует взаимно однозначное соответствие , переводящее дуги в дуги, т.е. такое, что (a,b)ÎE₁ тогда и только тогда, когда (f(a), f(b))ÎE₂.

Отсюда следует, что у изоморфных графов поровну вершин и поровну дуг. Обратное неверно: этого для изоморфизма недостаточно!

Для помеченных графов взаимно однозначное соответствие множеств вершин при проверке изоморфизма устанавливается по номерам вершин.

Примеры применения изоморфизма – разные изображения графа K_3,3, известная задача о шахматных конях на доске 3´3.

Каждому ориентированному графу сопоставляется единственный (с точностью до изоморфизма) неориентированный граф: геометрически он получается «стиранием» стрелок на дугах, аналитически – симметризацией бинарного отношения E (т.е. добавлением в E пары (j,i), если (i,j)ÎE). В то же время, неориентированному графу соответствует множество ориентированных графов.

Введем следующее понятие.

ОПРЕДЕЛЕНИЕ 18.Граф Г₂=(V₂,E₂) называется подграфомграфа Г₁=(V₁,E₁), если . Подграф называется остовным, если , т.е. Г₂ образован из Г₁ удалением некоторых дуг. Подграф называется порожденным, если из условий a,bÎE₂, (a,b)ÎE₁ следует, что (a,b)ÎE₂. Это означает, что Г₂ образован из Г₁ удалением некоторых вершин и инцидентных им дуг.

Примеры неориентированных графов.

1. Полный граф K_p.

2. Вполне несвязный граф .

3. Цикл.

4. Цепь.

5. Полный двудольный граф K_m,n.

ОПРЕДЕЛЕНИЕ 19.Степенью вершинынеориентированного графа называется число дуг графа, ей инцидентных. Обозначение: deg(a). Для вершины ориентированного графа определены полустепени выхода и входаdeg^-(a) и deg⁺(a)–числа дуг соответственно начинающихся и заканчивающихся вершиной a.

Следующее утверждение очень простое, но полезное.

ПРЕДЛОЖЕНИЕ.В неориентированном графе . Здесь, как и выше, p – число вершин, q – число дуг графа.

В ориентированном графе .

Для доказательства достаточно заметить, что в первой сумме каждая дуга учитывается дважды (с каждым из концов), второе утверждение проверяется аналогично.

В ориентированном графе вершины, у которых полустепень входа (выхода) нулевая, называются истоками (стоками).

Существует множество красивых и полезных конструкций, которые по данным графам позволяют строить новые графы (сумма, произведение, объединение и т.д.). Приведем две такие конструкции.

ОПРЕДЕЛЕНИЕ 20. Пусть Г – неориентированный граф. Смежным (или реберным)графом называется граф, вершины которого взаимно однозначно сопоставлены ребрам Г, причем они смежные тогда и только тогда, когда смежными являются соответствующие ребра Г.

Еще одна полезная конструкция.

ОПРЕДЕЛЕНИЕ 21. Пусть Г – неориентированный граф. Дополнительнымграфом называется граф с теми же вершинами, в котором вершины являются смежными тогда и только тогда, когда они не смежные в Г.

 

Компьютерные представления графов

Естественно, графы представляются в виде некоторых наборов данных. Подобных представлений существует множество, у каждого есть свои достоинства и… 1. Матрица смежностиS(Г). Это квадратная матрица размеров p´p (как обычно, p – число вершин). Для ее построения надо занумеровать вершины.…

Маршруты и связность

ОПРЕДЕЛЕНИЕ 22.Маршрутом (путем)в графе называется последовательность вида , где v – вершины, e – дуги, . Этот маршрут соединяет вершины и … Маршрут называется замкнутым (циклом), если . Маршрут называется цепью, если в нем все дуги различные (при этом вершины могут повторяться).

Кратчайшие пути в графах

Рассмотрим следующую задачу. В графе Г выделены две вершины: b (начальная) и e (конечная). Требуется найти все пути минимальной длины из b в e (если… Для решения этой задачи используется очень эффективный волновой алгоритм. Идея… Волновой алгоритм тем самым состоит из двух этапов. Прямой ход позволяет найти длину кратчайшего пути (далее…

Деревья

ОПРЕДЕЛЕНИЕ 25.Лесомназывается неориентированный граф без циклов. Деревомназывается связный лес. Таким образом, дерево характеризуется тремя свойствами: - неориентированность,

ПРЕДЛОЖЕНИЕ.

2. Если в дереве не менее двух вершин, то у него не менее двух листов. Доказательство. 1. Поскольку дерево является связным графом, то всякие его вершины можно соединить хотя бы одной цепью. Если для…

Кодирование деревьев

Для помеченных деревьев существует эффективный способ кодирования(его можно использовать для компьютерного представления деревьев). Найдем лист с минимальным номером, удалим его вместе с инцидентной дугой и… Разумеется, код полезен тогда, когда существует метод декодирования, т.е. восстановления дерева по коду. Опишем…

Центр дерева

Под расстоянием d(a,b) между вершинами неориентированного графа, как и ранее, понимается минимальное число дуг в пути, соединяющем эти вершины. ОПРЕДЕЛЕНИЕ 26.Эксцентриситетомвершины a неориентированного связного графа… Центр дерева устроен очень просто.

Минимальное остовное дерево(остов)

Пусть некоторое семейство пунктов требуется связать сетью дорог. Известна стоимость прокладки дороги между теми парами пунктов, для которых это… Естественно, сеть дорог должна быть связной (любой пункт должен быть доступен… Известно множество эффективных алгоритмов решения этой задачи. В основном они были разработаны в середине 20 века.…

Эйлеровы графы

Вернемся к задаче Эйлера о кенигсбергских мостах. По существу, задача сводится к построению в графе цикла, который содержит каждую дугу графа по… ОПРЕДЕЛЕНИЕ 27.Цикл в графе называется эйлеровым, если каждая дуга графа… Легко привести примеры таких графов. Проверка эйлеровости графа очень проста.

Гамильтоновы графы

Понятие гамильтонова графа очень близко к понятию эйлерова графа, но между ними пропасть, как вскоре выяснится! ОПРЕДЕЛЕНИЕ 28.Цикл в графе называется гамильтоновым, если каждая вершина… Понятия эйлерова и гамильтонова графа независимы: для любой комбинации свойств «эйлеров – не эйлеров», «гамильтонов –…

Графовые векторы

Понятие степени вершины было введено выше. ОПРЕДЕЛЕНИЕ 29.Графовым вектором(иногда говорят о графовом разбиении)… Примеры. У полного графа все компоненты графового вектора равны (p-1), у вполне несвязного – 0, у цикла – 2.

Паросочетания и реберные покрытия

ОПРЕДЕЛЕНИЕ 30.Паросочетаниемв неориентированном графе называется семейство дуг, попарно не имеющих общих вершин. Очевидно, что подмножество паросочетания также является паросочетанием.… ОПРЕДЕЛЕНИЕ 31.Семейство дуг (ребер) в неориентированном графе без изолированных вершин называется реберным покрытием,…

Паросочетания в двудольных графах

Двудольные графы упоминались ранее, но формального определения не было. ОПРЕДЕЛЕНИЕ 32.Граф Г называется двудольным, если множество его вершин… Таким образом, смежными в двудольном графе могут быть только вершины из разных множеств.

Правильная нумерация вершин графа

ОПРЕДЕЛЕНИЕ 33.Нумерация вершин в ориентированном графе называется правильной(или топологической), если наличие дуги (vi,vj) означает, что i<j. В… Теорема 26. Для того, чтобы в ориентированном графе существовала правильная… Доказательство. Пусть в ориентированном графе есть цикл. Докажем, что правильной нумерации вершин не существует. Пусть…

Сетевые графики

ОПРЕДЕЛЕНИЕ 34.Сетевым графикомназывается ориентированный взвешенный ациклический граф с единственным истоком и единственным стоком. Сетевые графики широко используются при организации производства сложных… Алгоритм построения критического пути начинается с правильной нумерации вершин графа (она возможна, поскольку граф…

Потоки в сетях

Весам дуг можно дать иную интерпретацию, в результате возникает интересная и важная задача. Пусть в ориентированном взвешенном графе выделены две… ОПРЕДЕЛЕНИЕ 35.Потоком в сетиот вершины b к вершине e называется определенная… x(u,v)≤ c(u,v);

Вопросы для самопроверки

1. Что такое граф? Из чего он состоит? Какие виды графов вы знаете? 2. Какие вершины, дуги называются смежными? Инцидентными? 3. Какие графы называются изоморфными?

Упражнения

1. Существует ли неориентированный граф, степени всех вершин которого различны? 2. Постройте неориентированный граф, степени вершин которого равны… 3. Постройте все неизоморфные неориентированные графы, у которых 4, 5, 6 вершин. Тот же вопрос для ориентированных…

Рекомендуемая литература

По дискретной математике книги различного уровня издаются постоянно. Приведем несколько достойных (по мнению автора) изданий. Большинство книг доступно в сети.

1. Кузнецов О.П. Дискретная математика для инженера. — СПб.: Лань, 2004 (предыдущие издания совместно с Адельсоном-Вельским Г.М.)

2. Романовский И. В. Дискретный анализ. — 4-е изд. — СПб.: Невский Диалект; БХВ-Петербург, 2008.

3. Андерсон Дж. Дискретная математика и комбинаторика — М.: «Вильямс», 2006.

4. Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1979

5. Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. — М.: Наука, 1963.

6. Юлмухаметов Р. С., Исаев К.П., Трунов К.В. Дискретная математика: курс лекций Уфа : РИО БашГУ, 2005.

По комбинаторике можно порекомендовать несколько замечательных книг. Первая популярная, примечательна еще и тем, что три ее автора это дед, отец и внук. Вторая это очень глубокое изложение материала. Третья содержит богатейший материал, изложенный доступно и неформально.

7. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. – М.: ФИМА, МЦНМО, 2006.

8. Стенли Р. Перечислительная комбинаторика. — М.: Мир, 1990.

9. Кнут Д., Грэхем Ф., Поташник О. Конкретная математика. Основы информатики. – М.: Мир, 2006.

Издается множество книг, посвященных теории графов. Перечислю несколько из них.

10. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

11. Харари Ф. Теория графов. – М.: Либроком, 2009 г.

12. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. – М.: Либроком, 2009 г.

13. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.

14. Дистель Р. Теория графов. – Новосибирск: Изд-во Института математики, 2002.

15. Свами М., Тхулалираман К. Графы, сети и алгоритмы. – М: Мир, 1984.

16. Татт У. Теория графов. – М: Мир, 1988.

Ряд упражнений заимствован из пособия Исаева К.П., Трунова К.В. «Задачи по дискретной математике» (Уфа, БашГУ, 2006).

 

 

Предметный указатель

  n-арное отношение на множестве, 21 алгоритм Дейкстры, 50