Orientacja (teoria grafów) - Orientation (graph theory)
W teorii wykres An orientacji o nieukierunkowane wykresu jest przypisanie kierunku na każdej krawędzi, zmieniając początkowy wykresu na skierowanej wykresie .
Wykresy zorientowane
Graf skierowany jest nazywany grafem zorientowanym, jeśli żadna z jego par wierzchołków nie jest połączona dwoma symetrycznymi krawędziami. Wśród grafów skierowanych grafy zorientowane to takie, które nie mają 2 cykli (czyli co najwyżej jeden z ( x , y ) i ( y , x ) może być strzałkami wykresu).
Turnieju jest orientacja całkowitego wykresie . Polytree jest orientacja undirected drzewa . Przypuszczenie Sumnera mówi, że każdy turniej z 2 n − 2 wierzchołkami zawiera każde wielodrzewo z n wierzchołkami.
Liczba grafów zorientowanych nieizomorficznie o n wierzchołkach (dla n = 1, 2, 3, …) wynosi
Turnieje są w korespondencji jeden do jednego z kompletnymi grafami skierowanymi (wykresy, w których między każdą parą różnych wierzchołków znajduje się skierowana krawędź w jednym lub obu kierunkach). Kompletny graf ukierunkowany można przekształcić w graf zorientowany, usuwając co 2 cykle, i odwrotnie, graf zorientowany można przekształcić w kompletny graf skierowany, dodając 2 cykle między każdą parą wierzchołków, które nie są punktami końcowymi krawędzi; te korespondencje są bijektywne . Dlatego ta sama sekwencja liczb rozwiązuje również problem enumeracji grafów dla pełnych dwugrafów. Istnieje wyraźny, ale skomplikowany wzór na liczby w tej sekwencji.
Ograniczone orientacje
Silne ukierunkowanie jest orientacji, która prowadzi do silnie połączony wykresie . Ściśle powiązane orientacje całkowicie cykliczne to orientacje, w których każda krawędź należy do co najmniej jednego prostego cyklu. Zorientowanie się nieukierunkowane wykres G jest całkowicie cykliczny, wtedy i tylko wtedy, gdy to silne ukierunkowanie każdego podłączonego urządzenia z G . Twierdzenie Robbinsa mówi, że graf ma silną orientację wtedy i tylko wtedy, gdy jest połączony 2 krawędziami ; odłączone grafy mogą mieć całkowicie cykliczne orientacje, ale tylko wtedy, gdy nie mają mostków .
Orientacji acykliczny jest orientacji, która skutkuje skierowany acykliczny wykres . Każdy wykres ma orientację acykliczną; wszystkie orientacje acykliczne można uzyskać, umieszczając wierzchołki w sekwencji, a następnie kierując każdą krawędź od wcześniejszego z jej punktów końcowych w sekwencji do późniejszego punktu końcowego. Twierdzenie Gallai-Hasse-Roya-Vitavera stwierdza, że wykres ma acykliczną orientację, w której najdłuższa ścieżka ma co najwyżej k wierzchołków wtedy i tylko wtedy, gdy może być pokolorowana co najwyżej k kolorów. Orientacje acykliczne i orientacje całkowicie cykliczne są powiązane ze sobą przez dualność planarną . Orientacja acykliczna z jednym źródłem i pojedynczym odpływem nazywana jest orientacją bipolarną .
Orientacji przechodni jest orientacji tak, że uzyskany jest skierowany wykres własnej przechodni zamknięcia . Grafy z orientacjami przechodnimi nazywane są grafami porównywalności ; można je zdefiniować z częściowo uporządkowanego zbioru , tworząc dwa sąsiadujące ze sobą elementy, ilekroć są one porównywalne w częściowym porządku. Orientację przechodnią, jeśli istnieje, można znaleźć w czasie liniowym. Jednak sprawdzenie, czy uzyskana orientacja (lub dowolna dana orientacja) jest faktycznie przechodnia, wymaga więcej czasu, ponieważ jest równoważna złożonością mnożeniu macierzy .
Eulera orientacji o nieukierunkowane wykresie to pozycji, w której każdy wierzchołek jest równa stopnia i z stopni. Orientacje Eulera grafów siatkowych pojawiają się w mechanice statystycznej w teorii modeli lodowych .
Orientacja Pfaffian ma tę właściwość, że pewne cykle nawet długości na wykresie mają nieparzystą liczbę krawędzi zorientowanych w każdym z dwóch kierunków całym cyklu. Zawsze istnieją dla grafów planarnych , ale nie dla niektórych innych grafów. Wykorzystywane są w algorytmie FKT do zliczania idealnych dopasowań.