Самодополнительный граф — это граф, изоморфный своему дополнению. Простейшие нетривиальные самодополнительные графы — это путь, состоящий из 4 вершин и цикл из 5 вершин.
Примеры
Любой граф Пэли является самодополнительным[1]. Например, 3 × 3 ладейный граф (граф Пэли девятого порядка) тоже самодополнителен ввиду симметрии, сохраняющей центральную вершину на месте, но обменивающей роли средних точек по четырём краям и углов решётки[2]. Все сильно регулярные самодополнительные графы с менее чем 37 вершинами являются графами Пэли. Однако существуют строго регулярные графы с 37, 41 и 49 вершинами, не являющиеся графами Пэли[3].
Граф Радо является бесконечным самодополнительным графом.
Свойства
Самодополнительный граф с n вершинами имеет в точности половину числа рёбер полного графа, т. е. n(n − 1)/4 рёбер, и (если вершин больше одной) его диаметр должен быть либо 2, либо 3[1]. Поскольку n(n −1) должен делиться на 4, n должен быть сравнимым с 0 или 1 по модулю 4. Например, граф с 6 вершинами не может быть самодополнительным.
Вычислительная сложность
Задача проверки, являются ли два самодополнительных графа изоморфными и проверка, является ли заданный граф самодополнительным, эквивалентны по времени выполнения[en] общей задаче проверки изоморфизма графов[en][4].
Примечания
- 1 2 Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. — 1962. — Т. 9. — С. 270—288.
- ↑ S. Shpectorov. Complementary l1-graphs // Discrete Mathematics. — 1998. — Т. 192, вып. 1-3. — С. 323—331. — DOI:10.1016/S0012-365X(98)0007X-1.
- ↑ I. G. Rosenberg. Theory and practice of combinatorics. — 1982. — Т. 60. — С. 223—238.
- ↑ Marlene J. Colbourn, Charles J. Colbourn. Graph isomorphism and self-complementary graphs // SIGACT News. — 1978. — Т. 10, вып. 1. — С. 25—29. — DOI:10.1145/1008605.1008608.
Ссылки
- Weisstein, Eric W. Self-Complementary Graph (англ.) на сайте Wolfram MathWorld.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .