Тривіально досконалий граф

Тривіально досконалий граф — це граф із властивістю, що в кожному його породженому підграфі розмір найбільшої (за розміром) незалежної множини дорівнює числу найбільших клік^[1][2]. Тривіально досконалі графи першим вивчав Волк^[3][4], але назву дав Голумбік^[2]. Голумбік писав, що «цю назву вибрано з огляду на тривіальність доведення, що такі графи є досконалими». Тривіально досконалі графи відомі також як графи порівнянності дерев^[3][4], деревовидні графи порівнянності^[5] і квазіпорогові графи^[6].

Побудова тривіально досконалого графу зі вкладених інтервалів і з відношення досяжності в дереві

Еквівалентні описи

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

• Вони є графами порівнянності дерев з теорії порядків^[en]. Тобто, нехай T — частковий порядок, такий, що для будь-якого t ∈ 'T' множина {s ∈ T : S < t} є цілком упорядкованою з відношенням < і T має найменший елемент r. Тоді граф порівнянності порядку T тривіально досконалий і будь-який тривіально досконалий граф можна сформувати таким способом^[7][8].
• Вони є графами, що не містять шляху P₄ або циклу C₄ як породжених підграфів^[7][9][10]
• Вони є графами, в яких кожен зв'язний породжений підграф містить універсальну вершину^[3].
• Вони є графами, які можна подати як інтервальні графи множини вкладених проміжків. Множина проміжків має властивість вкладеності, якщо для будь-яких двох проміжків із множини вони або не перетинаються, або один з них міститься в іншому^[11].
• Вони є графами, які одночасно є хордальними графами і кографами^[12][13]. Це випливає з опису хордальних графів як графів без породжених циклів довжини чотири і більше і кографів як графів без породжених шляхів з чотирма вершинами (P₄).
• Це графи, які водночас є кографами й інтервальними графами^[12][13].
• Вони є графами, які можна утворити, починаючи з графів з однією вершиною, за допомогою двох операцій — незв'язного об'єднання двох менших тривіально досконалих графів і додання нової вершини, суміжної всім вершинам меншого тривіально досконалого графу^[6][14]. Ці операції відповідають утворенню нового лісу незв'язним об'єднанням двох менших лісів і утворенню дерева з'єднанням нового кореня з коренями всіх дерев лісу.
• Вони є графами, в яких для будь-якого ребра uv околи вершин u і v (включно з самими u і v) вкладені — один окіл має бути околом іншого^[13].
• Вони є графами перестановки, визначеними зі сортованих у стеку перестановок^[en][15].
• Вони є графами з властивістю, що в кожному його породженому підграфі число клікового покриття дорівнює числу максимальних клік^[16].
• Вони є графами з властивістю, що в кожному його породженому підграфі клікове число дорівнює псевдочислу Ґранді^[16].
• Вони є графами з властивістю, що хроматичне число кожного його породженого підграфу дорівнює псевдочислу Ґранді^[16].

Пов'язані класи графів

З еквівалентних описів тривіально досконалих графів випливає, що будь-який тривіально досконалий граф є також кографом, хордальним, птолемеєвим, інтервальним і досконалим графом.

Порогові графи — це точно ті графи, які є одночасно тривіально досконалими і є доповненням тривіально досконалих графів (тривіально досконалих кографів)^[17][18].

Вітряки є тривіально досконалими.

Розпізнавання

Чу^[19] описує простий алгоритм лінійного часу для розпізнавання тривіально досконалих графів, заснований на лексикографічному пошуку в ширину. Коли алгоритм LexBFS видаляє вершину v з першої множини в черзі, алгоритм перевіряє, що всі сусіди вершини v, що залишилися, належать тій самій множині. Якщо ні, один із заборонених породжених підграфів можна побудувати з v. Якщо перевірка успішна для всіх v, то граф тривіально досконалий. Алгоритм можна модифікувати для перевірки за лінійний час, чи є граф доповненням тривіально досконалого графу.

Визначення, чи стає граф загального вигляду після видалення k ребер тривіально досконалим графом, є NP-повною задачею^[20], фіксовано-параметрично розв'язною^[21], і її можна розв'язати за час O(2,45^k(m+n))^[22].