Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик . Тривиально совершенные графы первым изучал Волк , но название дал Голумбик . Голумбик писал, что «это название было выбрано ввиду тривиальности доказательства, что такие графы являются совершенными .» Тривиально совершенные графы известны также как графы сравнимости деревьев , древовидные графы сравнимости и квазипороговые графы .

Эквивалентные описания

Тривиально совершенные графы имеют несколько других эквивалентных описаний:

• Они являются графами сравнимости . То есть пусть T — частичный порядок , такой, что для любого t ∈ T множество { s ∈ T : s < t } является вполне упорядоченным с отношением < и T обладает наименьшим элементом r . Тогда граф сравнимости порядка T тривиально совершенен и любой тривиально совершенный граф может быть сформирован таким образом .
• Они являются графами, не содержащими путь P ₄ или цикл C ₄ в качестве порождённых подграфов
• Они являются графами, в которых каждый связный порождённый подграф содержит универсальную вершину .
• Они являются графами, которые можно представить как интервальные графы множества вложенных промежутков . Множество промежутков имеет свойство вложенности, если для любых двух промежутков из множества они либо не пересекаются, либо один из них содержится в другом .
• Они являются графами, которые одновременно являются хордальными графами и кографами . Это следует из описания хордальных графов как графов без порождённых циклов длины четыре и больше и кографов как графов без порождённых путей с четырьмя вершинами ( P ₄ ).
• Они являются графами, одновременно являющимися кографами и интервальными графами .
• Они являются графами, которые могут быть образованы, начиная с графов с одной вершиной, с помощью двух операций — несвязное объединение двух меньших тривиально совершенных графов и добавления новой вершины, смежной всем вершинам меньшего тривиально совершенного графа . Эти операции соответствуют образованию нового леса путём несвязного объединения двух меньших лесов и образованию дерева путём соединения нового корня с корнями всех деревьев леса.
• Они являются графами, в которых для любого ребра uv окрестности вершин u и v (включая сами u и v ) вложены — одна окрестность должна быть окрестностью другой .
• Они являются графами перестановки , определёнными из .
• Они являются графами со свойством, что в каждом его порождённом подграфе число кликового покрытия равно числу максимальных клик .
• Они являются графами со свойством, что в каждом его порождённом подграфе кликовое число равно псевдочислу Гранди .
• Они являются графами со свойством, что хроматическое число каждого его порождённого подграфа равно псевдочислу Гранди .

Связанные классы графов

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

Пороговые графы — это в точности те графы, которые являются одновременно тривиально совершенными и являются дополнением тривиально совершенных графов (тривиально совершенных кографов) .

Мельницы являются тривиально совершенными.

Распознавание

Чу описывает простой алгоритм линейного времени для распознавания тривиально совершенных графов, основанный на лексикографическом поиске в ширину . Когда алгоритм LexBFS удаляет вершину v из первого множества в очереди, алгоритм проверяет, что все оставшиеся соседи вершины v принадлежат тому же множеству. Если нет, один из запрещённых порождённых подграфов может быть построен из v . Если проверка успешна для всех v , то граф тривиально совершенен. Алгоритм можно модифицировать для проверки за линейное время, является ли граф дополнением тривиально совершенного графа.

Определение, получается ли граф общего вида после удаления k рёбер тривиально совершенным графом, является NP-полной задачей , фиксированно-параметрически разрешимой , и она может быть решена за время O(2,45 ^k (m+n) ) .

Примечания

Литература

Ссылки

• ,