Контрольная работа по "Дискретной математике"

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

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

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

 

Факультет дистанционного обучения

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

 

 

 

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

по дисциплине «Дискретная математика»

(Учебное пособие «Дискретная  математика,

часть 2», автор Е.Ф. Жигалова, 2004 г.)

Вариант 14.

 

 

                                                   Выполнил:

студент ФДО

гр.:

специалности: 220201

  2013г.

 

         

 

 

2013 г.

Задание 1.

Решить задачу коммивояжёра.

Исходные данные:

Значения элементов  матрицы расстояний:

a(1,1)=  a(2.1)=53                a(3.1)=32                 a(4.1)=11

a(1.2)=25 a(2.2)=             a(3.2)=72               a(4.2)=35

a(1.3)=15 a(2.3)=24            a(3.3)=               a(4.3)=79

a(1.4)=13 a(2.4)=36            a(3.4)=118             a(4.4)=

a(1.5)=46 a(2.5)=75             a(3.5)=24              a(4.5)=38

a(5.1)=22 a(5.4)=16

a(5.2)=13 a(5.5)=

a(5.3)=34

Решение:

Составим матрицу C.

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

Вычтем минимумы из элементов строк

 

Теперь найдем минимумы по столбцам для полученной матрицы.

Вычтем их из каждого столбца

Найдем ребро  ветвления

Наибольшая  сумма, равная 35, получилась в клетке (3,5), следовательно,  множество разобьем на два подмножества (3,5) и (3*,5*).

В результате получим  следующую матрицу:

для которой  получим ребро ветвления:

Наибольшая  сумма, равная 33, получилась в клетке (4,1) , следовательно, множество разбивается на два подмножества (4,1) и (4*,1*).

В результате получим  следующую матрицу:

В ней найдем ребро ветвления

Наибольшая сумма констант составляет 10, принадлежит ребру (1,3). Множество разбивается на два подмножества (1,3) и (1*,3*).

После операции приведения получим следующую матрицу.

В результате полученных вычислений мы должны включить в  гамильтонов  цикл следующие ребра:

(3,5), (5,4), (4,1), (1,2), (2,3),

Тогда длина  маршрута получится равной 24+16+11+25+24=100.

Сравним с длиной любого маршрута, например:

(3,5), (5,2), (2,4), (4,1), (1,3). Длина этого маршрута равна  24+13+36+11+15=99.

 

Задание 2.

Найти минимальную  раскраску графа своего варианта с помощью алгоритма Магу. Определить хроматическое число.

Решение:

Рассмотрим  граф G = (X, U) и «раскрасим» его вершины так, чтобы смежные вершины не были окрашены в один цвет. Такую раскраску назовем правильной.

Если на правильную раскраску затрачено р цветов, то граф называется р-хроматическим.

Наименьшее  натуральное число р, для которого граф является p-хроматическим, называется хроматическим числом графа и обозначается g(G).

Все максимально  пустые подграфы данного графа были найдены в кр1.

(x₂ ,x_{3 ,}x_5,x_6, x_{8, ,}x₁₀);  (x₂ ,x_{3 ,}x_5,x₁₀);  (x₂ ,x_{3 ,}x_4,x_8,x₉ );  (x₂ ,x_{3 ,}x_4,x_7,x₉ );  (x₂ ,x_{3 ,}x_4,x_7,x₁₀ ); 

(x₂ ,x_{3 ,}x_4,x_8,x₁₀ );  (x₂ ,x_{3 ,}x_6,x_8,x₉ );  (x₁ ,x_{5 ,}x_6,x₁₀ );  (x₁ ,x_{7 ,}x₁₀ );  (x₁ ,x_{7 ,}x₉ );  (x₁ ,x_{6 ,}x₉ ).

Вершинам, принадлежащим  одному максимальному  пустому подграфу,   приписываем один цвет. Таким образом,  для  правильной раскраски вершин графа G требуется 11 цветов, т.е. p=11.

Граф G является  11-хроматическим.

Упорядочим  полученные множества вершин в порядке  убывания их кардинальных чисел:

(x₂ ,x_{3 ,}x_5,x_6, x_{8, ,}x₁₀);  (x₂ ,x_{3 ,}x_4,x_8,x₉ );  (x₂ ,x_{3 ,}x_4,x_7,x₉ );  (x₂ ,x_{3 ,}x_4,x_7,x₁₀ );  (x₂ ,x_{3 ,}x_4,x_8,x₁₀ ); 

(x₂ ,x_{3 ,}x_6,x_8,x₉ );  (x₁ ,x_{5 ,}x_6,x₁₀ );  (x₂ ,x_{3 ,}x_5,x₁₀);  (x₁ ,x_{7 ,}x₁₀ );  (x₁ ,x_{7 ,}x₉ );  (x₁ ,x_{6 ,}x₉ ).

Припишем вершинам множества (x₂ ,x_{3 ,}x_5,x_6, x_{8, ,}x₁₀) цвет «1».

Удалим раскрашенные вершины из всех множеств:

(x_4, x₉ );  (x_4,x_7,x₉ );  (x_4,x₇ );  (x₄);  (x₉ );  (x₁);   (x₁ ,x₇  );  (x₁ ,x_{7 ,}x₉);  (x₁ ,x₉ ).

Припишем вершинам множества (x_4,x_7,x₉ ) цвет «2».

Удалим раскрашенные вершины из всех множеств:

(x₁);   (x₁);  (x₁);  (x₁).

Припишем вершинам множества (x₁) цвет «3». Удалив все раскрашенные вершины получим пустое множество.

Это говорит  о том, что все вершины графа G – раскрашены. Для раскраски  потребовалось всего три цвета, т.е. хроматическое число g(G) графа G равно 3.

 

Задание 3.

ЗАДАЧА о  максимальном потоке на сети.

Исходные  данные: 

Дана сеть    S(X,U)

x₀  - исток сети;  x₇ – сток сети, где  x₀  ÎX;  x₇ÎX.

1. Вычислить  значение максимального потока  на сети S, с помощью алгоритма

Форда-Фалкерсона.

2. Построить   минимальный разрез сети S.

Варианты значений  пропускных   r_i,j   способностей  дуг сети (значения пропускных способностей дуг  r_i,j  заданы по направлению ориентации дуг: от  индекса i к индексу j):

r[0,1] = 19             r[4,7] = 14      r[6,3] = 13      r[5,7] = 43

r[0,2] = 10             r[4,2] = 18      r[6,7] = 35      r[5,4] = 26

r[0,3] = 9               r[2,5] = 21      r[2,1] = 81      r[6,5] = 41    

r[1,4] = 25             r[2,6] = 15      r[3,2] = 32

 

Решение:

Построим граф

Шаг 1. Выбираем произвольный поток, например, 0-1-4-7. Его  пропускная способность равна минимальной  из всех пропускных способностей входящих в него дуг, то есть 14.  Уменьшаем  пропускные способности дуг потока на 14, насыщенную дугу 4-7 вычеркиваем

Шаг 2. Выбираем произвольный поток, например, 0-1-4-5-7. Его  пропускная способность равна минимальной  из всех пропускных способностей входящих в него дуг, то есть 5.  Уменьшаем  пропускные способности дуг потока на 5, насыщенную дугу 0-1 вычеркиваем. 

Шаг 3. Выбираем произвольный поток, например, 0-3-2-5-7. Его  пропускная способность равна минимальной  из всех пропускных способностей входящих в него дуг, то есть 9.  Уменьшаем  пропускные способности дуг этого  потока на 9, насыщенную дугу 0-3 вычеркиваем. 

Шаг 4. Выбираем произвольный поток, например, 0-2-5-7. Его  пропускная способность равна минимальной  из всех пропускных способностей входящих в него дуг, то есть 10.  Уменьшаем  пропускные способности дуг этого  потока на 10, насыщенную дугу 0-2 вычеркиваем. 

Больше путей  нет. Суммарный поток 14+5+9+10=38.Начинаем расстановку пометок. Начальная  вершина (источник) 0 имеет пометку 0. Из этой вершины нет ненасыщенных дуг, больше пометки расставить нельзя. Значит, максимальный поток найден, причем  множество {1,2,3,4,5,6,7} образует разрез.

СПИСОК ЛИТЕРАТУРЫ

 

Дискретная математика	Жигалова Елена Федоровна	Электронное учебное  пособие
Дискретная математика. Часть 2	Жигалова Елена Федоровна	Учебное пособие
Дискретная математика. Часть 2.	Жигалова Елена Федоровна	Учебно-методическое пособие

 

 

Работу выполнил: