Файл: Дискрет.матем_Ч.2_УП.pdf

Федеральное агентство по образованию 

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

УПРАВЛЕНИЯ  И  РАДИОЭЛЕКТРОНИКИ  (ТУСУР) 

Кафедра компьютерных систем в управлении и  

проектировании (КСУП) 

Е.Ф. Жигалова 

ДИСКРЕТНАЯ

МАТЕМАТИКА

Часть

 2 

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

2004 

Корректор: Осипова Е.А. 
 
 
 
 
Жигалова Е.Ф. Дискретная математика. Часть 2: Учебное посо-
бие. 

− Томск: Томский межвузовский центр дистанционного об-

разования,  2004. 

− 102 c. 

В пособии на общей теоретической основе изложены основные поня-

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

К  пособию  прилагаются  электронные  версии  обучающих  программ 

базовых алгоритмов  задач  теории графов. 

Пособие рассчитано на студентов технических университетов.  

© Жигалова Елена Федоровна,           2004                  

© Томский межвузовский центр 

                                                              дистанционного образования,        2004

3 

СОДЕРЖАНИЕ

Введение................................................................................................5 
1 Теоретические основы комбинаторного анализа ..........................7 

1.1 Основные определения ............................................................ 10 
1.2 Простейшие задачи перечисления.......................................... 16 
1.3 Метод производящих функций............................................... 19 

1.3.1 Экспоненциальная производящая функция..................... 24 
1.3.2 Производящие функции и рекуррентные соотношения...... 26 

1.4 Метод включения и исключения ............................................ 30 
1.5 Системы различных представителей ..................................... 34 

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

2.1 Основные определения ............................................................ 38 
2.2 Задание графов с помощью матриц........................................ 40 
2.3 Основные типы графов ............................................................ 42 
2.4 Обыкновенные графы. Графы Кенига. Графы Бержа .......... 43 
2.5 Части с экстремальными свойствами в графах ..................... 53 

3 Связность графов ........................................................................... 60 

3.1 Маршруты, цепи и циклы ........................................................ 60 
3.2 Отделимость и соединимость. Компоненты связности ....... 67 
3.3 Метрика графа .......................................................................... 69 
3.4 Обходы графа............................................................................ 71 

3.4.1 Алгоритм Флёри нахождения эйлерова цикла ................ 73 
3.4.2  Цикломатическое число .................................................... 74 

3.5 Графы без циклов ..................................................................... 75 

3.5.1 Алгоритм Степанеца, Влэдуца нахождения каркаса             

графа..................................................................................... 76 

3.5.2 Анализ цикломатических свойств графа по матрице 

инциденций ......................................................................... 77 

3.5.3 Определение числа каркасов ............................................. 78 

4 Ориентированные графы............................................................... 80 

4.1 Маршруты на ориентированном графе.................................. 80 

4.1.1 Транзитивные и квазитранзитивные графы..................... 82 
4.1.2 Транзитивное замыкание ................................................... 83 

4.2 Бикомпоненты графа................................................................ 84 

4.2.1 Базы вершин. Ядра.............................................................. 86 
4.2.2 Алгоритм Рудяну нахождения ядер графа ....................... 88 

4 

5 Раскраска графов............................................................................ 91 

5.1 Раскраска вершин графа .......................................................... 91 

5.1.1 Нахождение минимальной раскраски путём                                        

использования соцветных вершин.................................... 93 

5.1.2 Алгоритм  Витавера нахождения минимальной              

раскраски  вершин .............................................................. 94 

5.2 Определение хроматического числа плоского графа........... 99 

5.2.1 Проблема четырёх красок ................................................ 101 

5 

ВВЕДЕНИЕ

Предмет теории графов и комбинаторики 
Выделение  теории  графов  и  комбинаторной  теории  в  само-

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

Чтобы  яснее  представить  область  приложения  теории  гра-

фов и комбинаторики, приведем несколько примеров. 

1.  Теория  электрических  цепей 

−  одна  из  наиболее  старых 

областей  применения  графов.  Здесь  решаются  задачи  анализа  и 
синтеза электрических цепей. 

2.  Теория  логических  сетей,  релейно-контактных  схем,  ав-

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

3. Теория транспортных сетей. Опираясь на теорию графов, 

теория  транспортных  сетей  представляет  один  из  эффективных