Построение матрицы смежности для графа гиперкуба четвертого порядка. Теория графов: основные понятия и определения

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

высшего профессионального образования

«Сибирский государственный аэрокосмический университет

имени академика М.Ф. Решетнева»

Курсовая работа

«Построение матрицы смежности для графа гиперкуба четвертого порядка»

Выполнила: студентка

гр. МИМ 14-01

Проверил:

г. Красноярск 2014г

Оглавление

Введение. 3

1 Граф гиперкуб и матрица смежности. 4

1.1 Теория графов: основные понятия и определения. 4

1.2 Граф гиперкуб. 4

1.3 Способы представления графов. 11

1.4 Матрица смежности. 11

2.Программа. 13

2.1Текст программы.. 13

2.2 Блок-схема программы.. 14

2.3 Результаты тестирования программы.. 15

Заключение. 16

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

Введение

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

Целью курсовой работы является разработка программы, осуществляющей вычисление матрицы смежности для графа гиперкуба с заданной точностью.

Задачи:

1.  Теоретически объяснить принцип вычисления матрицы смежности.

2.  Составить программу определения матрицы смежности.

3.  Протестировать программу.

4.  Сделать выводы по проделанной работе.

Работа состоит из двух частей. В первой части рассматривается, что такое граф гиперкуб и матрица смежности. Во второй части рассматривается код программы и ее работоспособность.

1 Граф гиперкуб и матрица смежности

1.1 Теория графов: основные понятия и определения

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

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

Точки иначе называют вершинами (узлы графа), отрезки – ребрами