Программа формирования матрицы

Аннотация. 2

Содержание. 3

1. Теоретическая часть. 4

2. Программная часть. 6

3. Анализ временной и ёмкостной сложности. 12

4. Заключение. 14

5. Список используемой литературы. 15

6. Решение контрольных примеров. 16

7. Исходный код программы. 34

Графом называется пара (X,U), где X – конечное множество вершин, а U – набор неупорядоченных и упорядоченных пар вершин. Обозначим граф G=(X,U). Неупорядоченная пара вершин называется ребром, упорядоченная – дугой. Граф, содержащий только ребра, называется неориентированным, только дуги – ориентированным, или орграфом.

Если вершины v и u соединены ребром e, то говорят, что они смежны между собой, а ребро e инцидентно каждой из них. Количество ребер графа, инцидентных вершине v называется степенью данной вершины. Для ориентированного графа выделяют входящую степень, равную количеству входящих ребер и исходящую степень, равную количеству исходящих ребер, а степенью вершины в таком случае называют сумму ее входящей и исходящей степени. Вершины, имеющие степень 0, называют изолированными.

Во время выполнения курсовой работы был разработан алгоритм, решающий поставленную задачу. По составленному алгоритму была написана программа, позволяющая:

• Вводить список окрестностей ориентированного графа из файла;

• Выводить на экран или в файл список окрестностей и степени исхода всех вершин;

• Находить вершину с наибольшей степенью исхода;

• Удалять вершины, смежные с вершиной, имеющей наибольшую степень исхода;

• Составлять матрицу смежности и выводить её на экран или в файл.

«C/C++ программирование на языке высокого уровня» Т. А. Павловская.

«Полный справочник по С++, 4-е издание» Герберт Шилдт

«Теория графов» В. В. Белов, У. М. Воробьёв.