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

6 

5. Заключение — в данном разделе приводятся основные выводы по 

результатам выполненных расчётов (сопоставление прогнозируемых и по-

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

задачи и др.). 

7.  Список  литературы  —  список  источников,  используемых  для 

выполнения работы. 

7 

ㇷÓð‡ÚÓð̇fl ð‡·ÓÚ‡ ‹ 1 

ñÂθ ··Óð‡ÚÓðÌÓÈ ð‡·ÓÚ˚ ‹ 1 
Изучить  основные  понятия,  определения  и  терминологию  теории 

графов,  классы  графов,  способы  задания  графа,  простейшие  операции  на 

графах, числовые характеристики графа и способы их вычисления. 

ᇉ‡ÌË ̇ ··Óð‡ÚÓðÌÛ˛ ð‡·ÓÚÛ ‹ 1 

Задание 1. 

По матрицам (рис. 2; 3) построить диаграммы графов, оп-

ределив предварительно вид данных матриц.  

Задание 

2.  Методами  поиска  «в  глубину»  и  «в  ширину»  выделить  в 

графе (рис. 1) между его вершинами наибольший минимальный маршрут. 

Задание 

3.  Для  каждой  пары  вершин  графа  (рис. 1)  аналитическим 

способом  вычислить  количество  маршрутов  длины,  равной 4, и  выделить 

те пары вершин, для которых их количество ≥ 3, но не более 10. Выписать 

эти маршруты для какой-либо из выделенных пар. В описании маршрутов 

указывать вершины и рёбра, входящие в него.  

Задание 

4. Построить матрицу метрики графа (рис. 1). 

Задание 

5.  С  помощью  алгоритма  Магу—Вейсмана  выполнить  пра-

вильную раскраску вершин графа с минимальным количеством цветов. 

Задание 

6. Определить число вершинного покрытия графа (рис. 1). 

Задание 

7. Определить содержит ли граф (рис. 1) эйлерову цепь или 

эйлеров цикл? 

Ответ обосновать. 

Варианты  исходных данных для выполнения пп. 1—7 лабораторной 

работы № 1 представлены в Приложении Б. 

Задание 

8.  Аналитическим  способом  определить  число  компонент 

связности графа.  

8 

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

Дан неорграф G(X,U).  

Дана  матрица  смежности R=(ri,j) графа G (значения  элементов  мат-

рицы смежности R(r[i,j]) представлены в Приложении В). 

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

Разработать алгоритм для вычисления числа компонент связности данного 

графа. В отчёте привести все промежуточные решения. 

Примечание:  

*

  Значения  элементов  матрицы R, симметричных  указанным,  полу-

чить самостоятельно.  

* Значения неуказанных элементов приравнять «нулю». 

По результатам выполнения лабораторной работы оформить отчёт. 

9 

ㇷÓð‡ÚÓð̇fl ð‡·ÓÚ‡ ‹ 2 

ñÂθ ··Óð‡ÚÓðÌÓÈ ð‡·ÓÚ˚ ‹ 2 
Изучить  алгоритм  Дейкстры  нахождения  кратчайшего  маршрута  на 

взвешенном  (нагруженном)  графе,  алгоритм  Форда—Фалкерсона  нахож-

дения 

максимального  потока  в  транспортной  сети

,  способ  минимизации 

булевых функций с помощью карт Карно. 

ᇉ‡ÌË ̇ ··Óð‡ÚÓðÌÛ˛ ð‡·ÓÚÛ ‹ 2 

Задание  1.

  Решить  задачу  нахождения  кратчайшего  маршрута  на 

взвешенном графе с помощью алгоритма Дейкстры. 

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

вершина х

0

 — начальная; 

вершина х

7

 — конечная. 

Примечание: 

*

r[i,j] — элементы  матрицы  R  длин  рёбер  (или  дуг)  данного  графа 

G=(X, U).  Значение r[i,j]  равно  длине  ребра  (дуги),  соединяющего 

i-ю и j-ю вершины графа. 

*

Значения симметричных элементов получить самостоятельно. 

Варианты графов представлены в Приложении Г. 

Задание 2. 

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

Исходные  данные  к  задаче  нахождения  гамильтонова  цикла  в  графе 

(задача коммивояжёра) представлены в Приложении Д. 

Задание  3

.  Решить  задачу  нахождения  максимального  потока  в 

транспортной сети с помощью алгоритма Форда—Фалкерсона. 

10 

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

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

x

0  

—

исток сети; x

7 

— сток сети, где x

0 

∈X; x

7

∈X. 

Значения  пропускной  r

i,j

  способности  дуг  сети  представлены  в  При-

ложении Е. 

Задание:  

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

алгоритм Форда—Фалкерсона. 

2). Построить разрез сети S. 

Примечание: 

*

Значения пропускных способностей дуг r

i,j

 заданы по направлению 

ориентации дуг: от индекса i к индексу j. 

Задание  4

.  Выполнить  минимизацию  булевой  функции  с  помощью 

карты Карно.  

Варианты булевой функции представлены в Приложении Ж. 

По результатам выполнения лабораторной работы оформить отчёт.