Стиснутий граф граф у якому видалення ребер будь якого породженого циклу з довжиною більшою трьох дає незв язний граф То

Стиснутий граф — граф, у якому видалення ребер будь-якого породженого циклу з довжиною, більшою трьох, дає незв'язний граф. Тобто це графи, в яких кожен периферійний цикл є трикутником.

Стиснутий граф, утворений як сума за клікою, що використовується для склеювання максимального планарного графу (жовтого) і двох хордальних графів (червоного і синього). Червоний хордальний граф можна, в свою чергу, розкласти на суми за кліками чотирьох максимальних планарних графів (два ребра і два трикутники).

Приклади

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

Опис

Сума за клікою двох графів утворюється ототожненням двох клік однакового розміру в кожному графі, а потім частина ребер кліки видаляється. Для версії сум за клікою для стиснутих графів крок видалення ребер опускають. Сума за клікою такого типу двох стиснутих графів призводить до іншого стиснутого графу, в якому будь-який довгий породжений цикл у сумі має бути обмеженим однією стороною або іншою (в іншому разі була б хорда між вершинами, яка проходить від однієї сторони суми в іншу), а незв'язні частини на цій стороні, утворені видаленням циклу, мають залишитися несвязними в сумі за клікою. Будь-який хордальний граф можна так розкласти на суму за клікою повних графів, і будь-який максимальний планарний граф можна розкласти на суму за клікою 4-вершинно-зв'язних максимальних планарних графів.

Як показали Сеймур і Вівер, це єдино можливі будівельні блоки для стиснутих графів — стиснуті графи, це точно графи, які можна утворити як суми за клікою повних графів і максимальних планарних графів.

Див. також

Реберно-досконалий граф, у якому будь-який непарний цикл є трикутником

Примітки

Seymour, Weaver, 1984.

Література

Seymour P. D., Weaver R. W. A generalization of chordal graphs // Journal of Graph Theory. — 1984. — Т. 8, вип. 2 (16 червня). — С. 241–251. — DOI:10.1002/jgt.3190080206..

[FOOTNOTESeymour,_Weaver1984-1] Seymour, Weaver, 1984.