Купить Генератор случайных связных кубических графов

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

Кубический граф – это регулярный граф степени 3, то есть граф, в котором каждой вершине инцидентно ровно 3 ребра. В работе будет решаться задача генерации некоторого произвольного множества случайных связных кубических графов при следующих ограничениях на алгоритм генерации:
1) Фиксированное число вершин графа, задаваемое пользователем.
2) Фиксированная мощность множества генерируемых графов, задаваемая пользователем.
3) Отсутствие соблюдения какого-либо закона распределения вероятностей при генерации множества случайных графов.
4) Отсутствие каких-либо требований, связанных с изоморфизмом генерируемых графов.
5) Отсутствие каких-либо требований, связанных с локальными свойствами генерируемых графов.
При этих ограничениях, вообще говоря, сложная, проблема генерации связных кубических графов может быть решена эффективно и просто на основе алгоритма, предложенного Яном Годгебауэром из Гентского университета (Бельгия) [5]. Оригинальный алгоритм Годгебауэра решает более сложную задачу – генерацию всех связных кубических графов. В его основе лежит несколько простых операций преобразования минимального связного кубического графа – полного четырехвершинного графа. Только эти операции и будут использоваться в настоящей работе при генерации случайных связных кубических графов. Остальная часть алгоритма использоваться не будет.
Для демонстрации рассматриваемого в данной работе эффективного алгоритма, его реализация осуществляется на двух языках: C# и С++.