Ориентация (теория графов)

Оглавление1 Ориентация (теория графов)1.1 Ориентация неориентированного графа1.2 Турниры и многогранники1.3 Число неизоморфных ориентированных графов1.4 Ограниченные ориентации1.5 Полный текст статьи:2 Ориентация […]

Ориентация (теория графов)

  • Ориентация неориентированного графа

    • Присвоение направления каждому ребру превращает неориентированный граф в ориентированный.  
    • Ориентированный граф не имеет 2-циклов.  
  • Турниры и многогранники

    • Турнир – это ориентация полного графа.  
    • Многогранник – это ориентация неориентированного дерева.  
    • Гипотеза Самнера утверждает, что каждый турнир с 2n – 2 вершинами содержит каждое многогранное дерево с n вершинами.  
  • Число неизоморфных ориентированных графов

    • Число неизоморфных ориентированных графов с n вершинами равно  
    • Турниры находятся во взаимно однозначном соответствии с полными ориентированными графами.  
    • Полный ориентированный граф можно преобразовать в ориентированный, удалив 2 цикла.  
    • Ориентированный граф можно преобразовать в полный ориентированный, добавив 2 цикла.  
  • Ограниченные ориентации

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

Полный текст статьи:

Ориентация (теория графов)

Оставьте комментарий

Прокрутить вверх