|
СЕМИНАРЫ |
Петербургский семинар по теории представлений и динамическим системам
|
|||
|
Перечисление помеченных и непомеченных гамильтоновых циклов в полных k-дольных графах Е. С. Краско, И. Н. Лабутин, А. В. Омельченко Санкт-Петербургский академический университет — научно-образовательный центр нанотехнологий РАН (Академический университет) |
|||
Аннотация: Задача перечисления гамильтоновых циклов в тех или иных семействах графов является одной из наиболее сложных задач перечислительной комбинаторики. Помимо некоторых тривиальных примеров (таких, например, как гамильтоновы циклы в полных графах), в литературе практически отсутствуют содержательные результаты, связанные с получением точного количества гамильтоновых циклов в графах. В силу очевидной сложности подобного рода задач усилия специалистов в теории графов сконцентрированы в основном на получении верхних или нижних оценок. Еще меньше результатов имеется в области перечисления непомеченных гамильтоновых циклов. Представленная работа посвящена перечислению помеченных и непомеченных гамильтоновых циклов в полных k-дольных графах |