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

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

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

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

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

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

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

ДИСКРЕТНАЯ

МАТЕМАТИКА

Часть

 2 

Учебное

методическое

пособие

2004 

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

− 

Томск:  Томский  межвузовский  центр  дистанционного  образования,  
2004. 

− 94 c. 

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

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

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

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

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

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

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

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

3 

СОДЕРЖАНИЕ

КОНТРОЛЬНАЯ РАБОТА №1....................................................... 4

Тема 1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ                                 

ТЕОРИИ ГРАФОВ ............................................................ 26

1.1 Определение графа........................................................... 26

1.2 Классы графов .................................................................. 28

1.3 Способы задания графов.................................................. 30

1.3.1 Геометрический ........................................................ 30

1.3.2 Описание графа через предикат (инцидентор) P... 30

1.3.3 Матричный................................................................ 30

1.4 Числовые характеристики вершин графа....................... 33

1.5 Маршруты, цепи и циклы ................................................ 33

1.6 Определение числа маршрутов длины «L» на графе .... 35

Тема 2. УНАРНЫЕ ОПЕРАЦИИ НА ГРАФЕ ............................. 37

2.1 Удаление вершины........................................................... 37

2.2 Удаление ребра ................................................................. 37

2.3 Замыкание (отождествление) вершин ............................ 38

2.4 Стягивание вершин графа по ребру................................ 38

Тема 3. ЧАСТИ ГРАФА ................................................................ 40

3.1 Подграф ............................................................................. 40

3.2 Суграф (частичный граф) ................................................ 41

Тема 4. ВЗВЕШЕННЫЕ ГРАФЫ. МЕТРИКА ГРАФА.............. 42

Тема 5. СТРУКТУРНЫЙ АНАЛИЗ ГРАФОВ ............................ 47

КОНТРОЛЬНАЯ РАБОТА №2

…………...……………..….………...

54 

Тема 6. МАРШРУТЫ СПЕЦИАЛЬНОГО ВИДА

………………..

73 

Тема 7. РАСКРАСКА ГРАФОВ. ХРОМАТИЧЕСКОЕ ЧИСЛО

…

79 

Тема 8. БИХРОМАТИЧЕСКИЕ ГРАФЫ

…………...……………..

83 

Тема 9. КОМПОНЕНТЫ СВЯЗНОСТИ

…………………………...

86 

Тема 10. ОПТИМАЛЬНЫЕ ПОТОКИ В ТРАНСПОРТНЫХ/  

ИНФОРМАЦИОННЫХ СЕТЯХ

…………………………

90 

4 

КОНТРОЛЬНАЯ

РАБОТА

№

1 

 
Контрольная работа №1 содержит 8 заданий. 
Для  выполнения  контрольной  работы  необходимо  выбрать 

свой вариант, пользуясь общим правилом вычисления его номе-
ра N (N= K div100, где  K – число,  образованное  последними 
двумя цифрами пароля студента). 

 
Задание 1. 
Для графа G=(X,U) ( рисунок 1) выполнить следующее: 
1.1.  Построить: 
- матрицу смежности; 
- матрицу инциденций. 
1.2. Определить степени S(x

i

) для всех вершин {x

i

} данного графа. 

(Указать каким способом вычисляли S(x

i

)). 

1.3. а). Подсчитать количество маршрутов 

j

i,

μ

 длиной 

3

=

l

 в 

графе  G=(X,U) для каждой пары вершин. 

б). Построить все  

j

i,

μ

 длиной 

3

=

l

, связывающие  вершины  х

i

и х

k

  ( помечены  * ).' 

Маршруты записать в форме: 

)

( p

ij

μ

=( х

i

 ,… х

t

 ,…, х

k

), где p 

− 

номер маршрута. Указать ребра, через которые проходят маршруты. 

Примечание. Для выполнения п.1.3а) составить программу 

на алгоритмическом языке Паскаль (к отчёту приложить исход-
ный код программы и exe-file). 

 
Задание 2. 
По матрицам А (рисунок 2) и С (рисунок 3) построить гра-

фы G1 и G2. 

 
Задание 3. 
Для  графа  G=(X,U) ( рисунок 1) построить  минимальные 

маршруты,  связывающие  вершину,  помеченную * (любую  из 
двух),  с остальными вершинами, указать их длину. Описать способ 
решения данной задачи.   

5 

Задание 4. 
Для  графа,  представленного  на  рисунке    1  выполнить  сле-

дующее: 

4.1. Привести примеры подграфов 3-х вершинных, 4-х вершин-

ных, 1-вершинных. 

4.2. Привести пример суграфа данного графа. 
4.3. Выполнить унарные  операции для вершин, помеченных *. 
 
Задание 5. 
Для графа G=(X,U) ( рисунок 1) выполнить следующее: 
5.1. Построить матрицу метрики (отклонений). 
5.2. Вычислить радиус и диаметр. 
5.3. Определить периферийные точки. 
 
Задание 6. 
Произвести  произвольно  ориентацию  рёбер  графа  G=(X,U) 

(рисунок 1) и для  нового графа 

N

G

 выполнить задания 1.1, 1.3, 5. 

 
Задание 7. 
Построить скелет графа 

N

G

. 

 
Задание 8. 
В графе G=(X,U) ( рисунок 1) найти все максимальные пол-

ные  и  максимальные  пустые  подграфы  с  помощью  алгоритма 
Магу-Уэйсмана. 

 
ВНИМАНИЕ ! Отчёт  по  контрольной  работе  №1  выполнять  в 

текстовом редакторе WORD.