СВЯЗЬ ГАМИЛЬТОНОВОСТИ И ПЛОТНОСТИ ОТНОШЕНИЯ СМЕЖНОСТИ ГРАФА

Смирнов Данила Антонович

В процессе рассмотрения пар различных характеристик графов был произведен поиск возможной связи между какой-нибудь одной парой таких характеристик. В результате сформирована гипотеза о панциклических графах, являющаяся основным выводом экспериментов. Расчеты проводились с применением распараллеливания процесса вычисления, все исходные коды написаны на объектно-ориентированном языке C++ и исполнялись под управлением системы Unix-подобной Debian opensource-сообщества. Для того, чтобы расчеты не становились слишком требовательны по времени применены техники динамического программирования для поиска Гамльтонова цикла, однако даже при данной оптимизации генерируемые пакетом Nauty графы рассмотрены только до 12 вершин, так как на большем числе вершин расчеты даже с оптимизациями проводить становится чересчур трудоемко.

Ключевые слова:граф, цикл, панцикличность, динамическое программирование, параллельное программирование