Оглавление
Ориентация (теория графов)
-
Ориентация неориентированного графа
- Присвоение направления каждому ребру превращает неориентированный граф в ориентированный.
- Ориентированный граф не имеет 2-циклов.
-
Турниры и многогранники
- Турнир – это ориентация полного графа.
- Многогранник – это ориентация неориентированного дерева.
- Гипотеза Самнера утверждает, что каждый турнир с 2n – 2 вершинами содержит каждое многогранное дерево с n вершинами.
-
Число неизоморфных ориентированных графов
- Число неизоморфных ориентированных графов с n вершинами равно
- Турниры находятся во взаимно однозначном соответствии с полными ориентированными графами.
- Полный ориентированный граф можно преобразовать в ориентированный, удалив 2 цикла.
- Ориентированный граф можно преобразовать в полный ориентированный, добавив 2 цикла.
-
Ограниченные ориентации
- Сильная ориентация приводит к сильно связному графу.
- Тесно связанные полностью циклические ориентации имеют каждое ребро в простом цикле.
- Теорема Роббинса утверждает, что граф имеет четкую ориентацию, если он соединен двумя ребрами.
- Ациклическая ориентация приводит к ориентированному ациклическому графу.
- Теорема Галлаи–Хассе–Роя–Витавера утверждает, что граф имеет ациклическую ориентацию с k вершинами, если он может быть раскрашен в k цветов.
- Ациклические и полностью циклические ориентации связаны плоской двойственностью.
- Биполярная ориентация имеет один источник и один приемник.
- Транзитивная ориентация приводит к транзитивному замыканию графа.
- Графы с транзитивной ориентацией называются графами сопоставимости.
- Эйлерова ориентация имеет равную внутреннюю и внешнюю степень вершин.
- Ориентация по Пфаффу имеет нечетное число ребер в циклах четной длины.
- Они используются в алгоритме FKT для подсчета идеальных совпадений.