Ациклична ориентация
Ацикличната ориентацияна неориентиран граф е присвояването на посоки на всяко ребро (ориентация), което не образува никакъв насочен цикъл и следователно такава ориентация превръща графа в насочен ацикличен граф. Всяка графика има ациклична ориентация.
Хроматичното число на всяка графика е равно на минималната дължина на максималния път [en] сред всички ациклични ориентации. Ацикличните ориентации са свързани с оцветяването чрез хроматичен полином, който отчита както ацикличните ориентации, така и оцветяванията. За равнинни графики ацикличните ориентации са двойните графики на напълно циклични ориентации [en] и обратно. Наборът от ациклични ориентации на даден график може да получи структурата на частичен куб, в който две циклични ориентации са съседни, ако се различават в посоката само на един ръб.
Дървовидните ориентации винаги са ациклични и са полидървета [en] . Ацикличните ориентации на пълните графи се наричат транзитивни турнири. Биполярните ориентации са специални случаи на ациклични ориентации, при които има точно един източник и един поглътител. Всеки преходен турнир е двуполюсен.
Съдържание
Всяка графика има ациклична ориентация. Един от начините за създаване на ациклични ориентации е да се подредят върховете и след това да се ориентира всеки ръб от най-ранния връх в списъка до най-късния. Тогава последователността от върхове се превръща в топологично подреждане на резултантния насочен ацикличен граф (DAG) и всяко топологично сортиране на този DAG формира същата ориентация.
Тъй като всеки OAG има топологичен сорт, може да се получи всяка ациклична ориентацияпо посочения начин. Различните върхови последователности обаче могат да доведат до еднакви ациклични ориентации, ако получената OAG има множество топологични сортове. Например, цикъл с четири върха (показан на фигурата) има 24 различни последователности, но само 14 възможни ациклични ориентации.
Теоремата на Gallai-Hasse-Roy-Vitaver гласи, че графиката има ациклична ориентация, в която максималният път [en] има най-много k върха тогава и само ако графиката може да бъде оцветена с най-много k цвята [1] .
Наборът от ациклични ориентации на даден график може да получи частична кубична структура, в която две циклични ориентации са съседни, ако се различават в посоката само на един ръб [5] . От това следва, че ако две различни ациклични ориентации на една и съща графика се различават в посоката на k ръба, е възможно да се трансформира една от ориентациите в другата чрез последователност от k промени в ориентацията на един ръб, така че всяко междинно състояние да е ациклична ориентация.
Всяка ориентация на дърво е ациклична. Насочен ацикличен граф, получен чрез такава ориентация, се нарича полидърво [en] [6] .
Ацикличната ориентация на пълен граф се нарича транзитивен турнир и е еквивалентна на пълно подреждане на върховете на графа. При такава ориентация има точно един източник и един поглътител.
Ациклична ориентация на произволен граф, който има уникален източник и уникален приемник, се нарича биполярна ориентация [7] .
Транзитивната ориентация на граф е ациклична ориентация, която е нейното транзитивно затваряне. Не всяка графика има транзитивна ориентация. Графиките, които имат транзитивна ориентация, саграфики за съпоставимост [8] . Пълните графики са специален случай на сравнимите графики, а транзитивните турнири са специален случай на транзитивните ориентации.