РЕКУРЕНТНІ СПІВВІДНОШЕННЯ ДЛЯ ЧИСЛА НЕІЗОМОРФНИХ (n,m)-ГРАФІВ

Анотація

Задача перерахування графів та підрахунку їх числа включає задачі перерахування та підрахунку числа помічених і числа непомічених графів. Друга з них вважається більш складною. Виділяють також задачі перерахування графів спеціального виду. Наприклад, помічених звичайних неорієнтованих графів, помічених звичайних орієнтованих графів, помічених зв’язних неорієнтованих графів, помічених дерев, непомічених гусениць та інших. Класичним результатом щодо перерахування графів вважають теорему Редфілда-Пойї, яка випливає з леми Бернсайда. Граф G з n вершинами та m ребрами називають n,m -графом. Два n,m -графа називаються ізоморфними, якщо існує бієкція між множинами вершин, яка зберігає їх суміжність. Ця стаття присвячена задачі підрахунку числа T n,m неізоморфних звичайних n,m -графів з використанням поняття вектора степенів графа. Вектор степенів графа є його неповним інваріантом відносноі изоморфізмів. Послідовності чисел T n,m для n ≤ 20 можна знайти в Online енциклопедії цілочислових послідовностей під номером A008406. У цій статті досліджено властивості вказаної таблиці, одна з яких демонструє залежність між кількостями всіх попарно неізоморфних графів з m ребрами та кількостями вершин, що відрізняються на один. Показано, що коли в сукупності всіх попарно неізоморфних n,m -графів присутній граф з вектором степенів (1,1,…,1), то n = 2m . Отримано рекурентні співвідношення, що дозволили знайти деякі не наведені в таблиці кількості неізоморфних графів з n вершинами та m ребрами при n > 20 . Для доведення рекурентних співвідношень введено поняття редукції вектора степенів графа (Р-перетворення). За допомогою Р-перетворення досліджено зв’язок між наборами попарно неізоморфних графів з однаковими кількостями ребер та різними кількостями вершин. Для підтвердження отриманих результатів була використана відома формула Харарі для знаходження числа неізоморфних звичайних графів.