[ВСЭИ] Теория графов и сетей (курсовая работа, задачи, C++)

В архиве сама работа и исходные коды программ на языке C++.

В курсовой работе определяется, является ли граф симметрическим. Особенность этой задачи состоит в том, что граф задан матрицей инциденций. Для этого задания написана программа на языке С++ (в среде разработки Visual C++ 2010 Express).

Во втором задании выполнено поэтапное разбиение графа, заданного матрицей смежности, на максимальные сильно связанные подграфы методом Мальгранжа. Для этого задания также написана программа на языке С++. Разбиение производится, начиная с вершины 14.

Задание 1

Постановка задачи

Разработать алгоритм, написать и отладить программу решения задачи: Граф, представленный матрицей смежности, формируется случайным образом. Построить три порожденных подграфа, включающие несколько вершин (n<5), номера которых также задаются случайным образом. 8<n<12.

Математическая формулировка задания

Имеется граф, состоящий из 15 вершин, представлен в виде матрицы смежности (состоит из 0 и 1).

Необходимо найти 3 порожденных подграфа, включающие несколько вершин. Для каждого подграфа число вершин выбирается случайным образом. Все три подграфа состоят исключительно из вершин, которые лежат в диапазоне.

Задание 2

Постановка задачи

Разработать алгоритм, написать и отладить программу решения задачи: Ориентированный граф размерностью 25 вершин задан матрицей смежности. Выполнить поэтапное разбиение графа на максимальные сильно связные подграфы методом Мальгранжа, начиная с 14 вершины.

Математическая формулировка задания

Имеется ориентированный граф из 25 вершин, представленный в виде матрицы смежности.

В качестве опорной вершины выбирается 14 вершина. Необходимо, отсеивая вершины графа, постепенно разбивать исходный граф на максимальные подграфы методов Мальгранжа.

Реферат 3

Задание 1 4

Постановка задачи 4

Математическая формулировка задания 4

Теоретические выкладки 4

Введенные обозначения 4

Алгоритм решения 5

Результаты 6

Задание 2 8

Постановка задачи 8

Математическая формулировка задания 8

Теоретические выкладки 8

Введенные обозначения 11

Алгоритм решения 12

Результаты 13

Список использованной литературы 15

Приложения 16

Приложение 1. Исходный код программы (задание 1) 16

Приложение 2. Исходный код программы (задание 2) 19

1. Волченская Т.В., Князьков В.С. Компьютерная математика: ч.2. Теория графов: Учебное пособие. - Пенза 2004. - 124 с.

2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике: Учеб. пособие. - Изд. 3-е, перераб. - М.: Физматлит, 2005 - 416 с.

3. Новиков Ф.А. Дискретная математика для программистов. - СПБ.: Питер, 2005. - 304 с.

4. Оре О. Графы и их применение: Пер. с англ. - Изд.3-е стереотипное. - М.: КомКнига, 2006.

5. Яблонский С.В. Введение в дискретную математику. - М.: Высшая школа, 2001. - 384 с.