Нахождение вершин в графе, имеющих наибольшее окружение

Содержание

Содержание

Введение3

1. Граф3

1.1.Основные термины и понятия3

1.2. Расстояние между вершинами, ярусы и диаметр графа.4

1.3. Достижимость и связность в графах5

1.3.1. Определение достижимости вершин5

1.4. Представление графов в компьютере5

1.4.1. Требования к представлению графов5

1.4.2. Матрица смежности6

1.4.3. Матрица инциденций6

1.4.4.Списки смежности7

1.4.5. Массив дуг7

2. Описание рабочего проекта8

2.1. Требования к работе программы8

2.2. Описание блок-схемы алгоритма8

2.3. Программная реализация алгоритма12

2.4. Руководство пользователя14

Заключение16

Литература17

Приложение18

Выдержка из текста

2.1. Требования к работе программы

Требуется создать прикладную программу, реализующую алгоритм поиска в графе вершин, имеющих наибольшее окружение.

Пусть дан граф и число k максимального количества ярусов. Требуется найти вершины в графе, у которых в первых k ярусах находится наибольшее количество вершин.

Созданная программа должна выполнять следующие действия:

Генерирование случайного графа с заданным числом вершин;

Графическое отображение графа и его матрицы смежности;

Вычисление последовательно степени матрицы смежности A2, А3, , Ak и соответствующие им матрицы ограниченных достижимостей R2, R3, , Rk., где k максимальное количество ярусов, задаваемое пользователем.

Вывод матрицы ограниченных достижимостей k го шага.

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

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

1.Кристофидес Н. Теория графов. Алгоритмический подход.

2.Наиболее полное руководство для профессиональной работы в среде Visual Basic 6.0

3.Харари Ф. Теория графов.

4.Новиков Ф.А., Дискретная математика для программистов.

5.Б.Н. Миронов, Лабораторный практикум по теории графов.

6.Наиболее полное руководство для профессиональной работы в среде Visual Basic 6.0.

Похожие записи