Перечисление графов
-
Основы комбинаторного перечисления графов
- Комбинаторное перечисление графов — это область математики, которая занимается подсчетом неориентированных и ориентированных графов определенных типов.
- Задачи могут быть решены точно или асимптотически.
-
История и классификация задач
- Пионерами в этой области были Джордж Поля, Артур Кейли и Дж. Говард Редфилд.
- Задачи различаются в зависимости от того, помечены ли вершины графа или нет.
- Помеченные задачи обычно проще, чем немаркированные.
-
Важнейшие результаты
- Число помеченных простых неориентированных графов с n вершинами равно 2n(n -1)/2.
- Число помеченных простых ориентированных графов с n вершинами равно 2n (n -1).
- Число Cn связных помеченных n-вершинных графов удовлетворяет рекуррентному соотношению.
- Число помеченных деревьев, свободных от n вершин, равно nn-2.
- Количество немаркированных гусениц с n вершинами равно.
-
Графическая база данных
- Исследовательские группы создали базы данных с возможностью поиска для графиков с определенными свойствами.
- Примером является база данных «Дом графов».
Полный текст статьи: