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

Краткая выдержка из текста работы (Аннотация)

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

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

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

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

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

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

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

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

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

Содержание работы

Содержание

Введение 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

Использованная литература

1. Кристофидес Н. Теория графов. Алгоритмический подход.
2. Наиболее полное руководство для профессиональной работы в среде Visual Basic 6.0
3. Харари Ф. Теория графов.
4. Новиков Ф.А., Дискретная математика для программистов.
5. Б.Н. Миронов, Лабораторный практикум по теории графов.
6. Наиболее полное руководство для профессиональной работы в среде Visual Basic 6.0.

Другие похожие работы

• Курсовая - Курсовой проект по компьютерной подготовке
• Курсовая - Объектно-ориентированное программирование
• Дипломная - Разработка программы автоматизированной классификации информационных сообщений СМИ по заданным тематикам
• Учебник - Объектно-ориентированное программирование на языке С++
• Контрольная - Моделирование поисковых алгоритмов (поиск в ширину)
• Контрольная - 5 программ на VBA
• Контрольная - Программирование на языке высокого уровня (ПЯВУ)
• Контрольная - Система массового обслуживания
• Контрольная - Игра пятнашки (15) - С
• Курсовая - Разработать программное обеспечение для работы со строками