Астероидный тройной свободный граф ⇐ Васина Википедия

[wiki_en]

В теории графов «граф без астероидных троек» или «граф без AT» — это граф, который не содержит «тройки астероидов».

==Определение==
'''астероидная тройка''' — это независимый набор (теория графов)|независимый набор из трех вершин {x, y, z, такой, что каждая пара соединена путем, который обходит окрестность (теория графов)|окрестность третьей вершины. Более формально, в графе G три вершины x, y и z образуют тройку астероидов, если:
* x, y и z попарно несмежны
* Существует путь x,y, который обходит N(z) (окрестность z)
* Существует путь x,z, который позволяет избежать N(y)
* Существует путь y,z, который позволяет избежать N(x)

Граф является свободным от AT, если он не содержит троек астероидов.

==Связь с другими классами графов==
Графы без AT представляют собой общее обобщение нескольких важных классов графов:
* Интервальные графики — это именно те графики, которые одновременно являются хордальными | хордальными и не содержат AT.
* Графы перестановок не содержат AT.
* Трапециевидные графики не содержат AT.
* Графики сосопоставимости не содержат AT.

Иерархия классов: \text{interval} \subset \text{permutation} \subset \text{trapezoid} \subset \text{cocomparability} \subset \text{AT-free}.

==Структурные свойства==
===Характеристики===
Графы без AT можно охарактеризовать несколькими способами:
* Через минимальные триангуляции: граф G является свободным от AT тогда и только тогда, когда каждое минимальное хордальное завершение|триангуляция T(G) графа G (т. е. каждое минимальное хордальное завершение) является графом интервалов. Кроме того, граф без когтей | граф без когтей без AT характеризуется тем свойством, что все его минимальные хордальные завершения являются собственными интервальными графами.
* Через несвязанные вершины: граф G свободен от AT тогда и только тогда, когда для каждой вершины x из G ни один компонент, не являющийся окрестностью x, не содержит вершин, не связанных с x.
* Через доминирующие пары и свойство позвоночника.

===Доминирующие пары===
Каждый связный граф без AT содержит доминирующую пару, пару вершин (u,v), такую, что каждый соединяющий их путь является доминирующим множеством в графе.
Более того, какая-то доминирующая пара достигает Расстояние (теория графов)|диаметр графа. Каждый связный граф, свободный от AT, имеет путь-mccds (связное доминирующее множество минимальной мощности, индуцирующее путь). В графах без AT диаметром не менее 4 вершины, которые могут находиться в доминирующих парах, ограничены двумя непересекающимися множествами X и Y, где (x,y) является доминирующей парой тогда и только тогда, когда x \in X и y \in Y.

===Свойство Spine===
Граф G является свободным от AT тогда и только тогда, когда каждый связный индуцированный подграф H удовлетворяет свойству позвоночника: для каждой несмежной доминирующей пары (\alpha,\beta) в H существует сосед \alpha' графа \alpha такой, что (\alpha',\beta) — доминирующая пара в компоненте H-{\alpha, содержащем \beta.

===Разложение===
Графы без AT допускают схему декомпозиции через покерные доминирующие пары. Вершина v является подходящей, если добавление висячей вершины, смежной с v, сохраняет свойство отсутствия AT. Каждый связный граф, свободный от AT, содержит доминантную пару, и сжатие определенных классов эквивалентности вершин (на основе их свойств доминирования) дает другой граф, свободный от AT, с доминантной парой, свободной от AT. Этот процесс можно повторять до тех пор, пока граф не сократится до одной вершины.

==Алгоритмические аспекты==
* '''Распознавание''': графы без AT могут быть распознаны за время O(n^3) для графа с n-вершинами.
* '''Ширина пути равна ширине дерева''': для графов без AT ширина пути равна ширине дерева.
* '''Совершенные графы''': сильная теорема об идеальных графах справедлива для графов без AT, поскольку они являются подклассом идеальных графов.

==Приложения==
Линейная структура, очевидная в графах без AT и их подклассах, привела к созданию эффективных алгоритмов для решения различных задач на этих графах, использующих их доминирующую парную структуру и другие свойства.

==См. также==
* Интервальный график
* Хордальный граф
* Хордальное завершение
* График сопоставимости
* Идеальный график

Семейства графов
Идеальные графики

Подробнее: https://en.wikipedia.org/wiki/Asteroida ... free_graph