Содержание
Содержание
Введение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.
С этим материалом также изучают
... : [сайт]. - [Б.м. ; б.г.]. - URL: http://lib.chdu.edu.ua/pdf/posibnuku/189/51.pdf 15. Стиль руководства и эффективность работы организации // Компетентность. – 2012. – № 2 ; То же [Электронный ресурс]. – URL: ...
... понятия3 1.2. Расстояние между вершинами, ярусы и диаметр графа.4 1.3. Достижимость и связность в графах5 1.3.1. Определение достижимости вершин5 1.4. Представление графов в компьютере5 1.4.1. ...
... ГРАФЫ. 6 Представление графа в памяти компьютера 6 Достижимость 7 КРАТЧАЙШИЕ ПУТИ. 8 Алгоритм Дейкстры 8 Алгоритм Флойда (кратчайшие пути между всеми парами вершин). ...
... транзитивности для заданного отношения.Созданная программа должна выполнять следующие действия:Генерирование случайного графа с заданным числом вершин;Графическое отображение графа и его матрицы смежности;Проверка выполнения свойства транзитивности ...
... графы», «Неориентированные графы», «связной граф», «связность графа», «вершины графа», «эйлеровый граф», матрица смежности, «Задача коммивояжера», матрица ... заключается практическое значение работы. Структурными разделами работы являются: введение, две ...
... работы программы на примере 11 Список использованных источников 13 Выдержка из текста Граф задаётся множеством точек или вершин ... алгоритм, создадим программу на языке C++, которая будет получать орграф в виде списка смежности с дополнительным ...
... 4. Текст программы 5. Результат работы программы 6. Заключение 7. Список источников информации Выдержка из текста Графом называется набор точек (эти точки называются вершинами), некоторые ...
... компиляции и сохраняется в течение всей работы программы. В языках программирования (Pascal, C, др.) ... графов, совокупность непустого множества вершин и наборов пар вершин (связей между вершинами). Объекты представляются как вершины, или узлы графа, ...
Разбираем решение задачи о связности графа на XLisp для студентов. Статья содержит теорию, пошаговый алгоритм DFS и готовый код с комментариями для контрольной.