ОмГТУ, АСОиУ, 1-ый курс
Отчет по курсовой работе 33 с. , 8 рис. , 5 табл. , 5
источников.
Ключевые слова: кубичекий граф, эффективный алгоритм генерации кубичеких графов, C#, C++
Объектом исследования в данной работе являются алгоритмы теории графов, применяемые при генерации связных кубических графов.
Цель работы – разработка алгоритма генерации случайных связных кубических графов.
В процессе работы проводился анализ двух алгоритмов генерации связных кубических графов:
1) Алгоритм на основе генерации случайной матрицы смежности графа и последующей проверки этой матрицы на предмет кубичности и связности графа ("примитивный" алгоритм).
2) Алгоритм Яна Годгебауэра из Гентского университета (Бельгия), который строит связный кубический граф на основе полного четырехвершинного графа, применяя к нему специальные преобразования.
В результате был разработан алгоритм генерации случайного связного кубического графа (упрощенная версия алгоритма Яна Годгебауэра) и произведена программная реализация этого алгоритма на языках программирования C# и C++ ("эффективный" алгоритм). Разработка программ производилась в среде программирования MS Visual Studio 2008.
В заключении приведено сравнение разработанных программ реализации эффективного алгоритма генерации на C# и C++ при генерации 100 случайных связных кубических графов с количеством вершин 2000. Сделан вывод об эффективности разработанного алгоритма. Приложения на C# и C++ находятся в одном солюшн, исходный код приложений прилагается
Ключевые слова: кубичекий граф, эффективный алгоритм генерации кубичеких графов, C#, C++
Объектом исследования в данной работе являются алгоритмы теории графов, применяемые при генерации связных кубических графов.
Цель работы – разработка алгоритма генерации случайных связных кубических графов.
В процессе работы проводился анализ двух алгоритмов генерации связных кубических графов:
1) Алгоритм на основе генерации случайной матрицы смежности графа и последующей проверки этой матрицы на предмет кубичности и связности графа ("примитивный" алгоритм).
2) Алгоритм Яна Годгебауэра из Гентского университета (Бельгия), который строит связный кубический граф на основе полного четырехвершинного графа, применяя к нему специальные преобразования.
В результате был разработан алгоритм генерации случайного связного кубического графа (упрощенная версия алгоритма Яна Годгебауэра) и произведена программная реализация этого алгоритма на языках программирования C# и C++ ("эффективный" алгоритм). Разработка программ производилась в среде программирования MS Visual Studio 2008.
В заключении приведено сравнение разработанных программ реализации эффективного алгоритма генерации на C# и C++ при генерации 100 случайных связных кубических графов с количеством вершин 2000. Сделан вывод об эффективности разработанного алгоритма. Приложения на C# и C++ находятся в одном солюшн, исходный код приложений прилагается