Блоковий граф

Блоковий граф

Блоковий граф (клікове дерево) — вид неорієнтованого графу, в якому кожна компонента двозв'язності (блок) є клікою.

Блокові графи можна описати графами перетинів блоків довільних неорієнтованих графів.

Опис

Блокові графи — це точно ті графи, в яких для кожних чотирьох вершин $u$, $v$, $x$ і $y$ найбільші дві з трьох відстаней $d(u,v)+d(x,y)$, $d(u,x)+d(v,y)$, $d(u,y)+d(v,x)$ завжди рівні.

Їх можна також описати за допомогою заборонених підграфів, як графів, що не містять алмазів або циклів довжини чотири або більше як породженого підграфу. Тобто, вони є хордальними графами без алмазів. Вони є також графами Птолемея (хордальними дистанційно-успадковуваними графами), в яких будь-які дві вершини на відстані два з'єднані єдиним найкоротшим шляхом, і хордальними графами, в яких будь-які дві кліки мають максимум одну спільну вершину.

Граф $G$ є блоковим тоді і тільки тоді, коли перетин будь-яких двох зв'язних підмножин вершин графу $G$ або порожній, або зв'язний. Таким чином, зв'язні підмножини вершин у зв'язному блоковому графі утворюють опуклу геометрію, і цією властивістю не володіє жоден інший вид графів. Унаслідок цієї властивості в зв'язному блоковому графі будь-яка множина вершин має єдину мінімальну чітку надмножину, замикання множини в опуклій геометрії. Зв'язні блокові графи — це точно ті графи, в яких існує єдиний породжений шлях, що з'єднує будь-які дві пари вершин.

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

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

Будь-яке дерево є блоковим графом. Інший приклад класу блокових графів дають вітряки.

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

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

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

Блокові графи неорієнтованих графів

Блоковий граф для заданого графу $G$ (позначається $B(G)$) — граф перетинів блоків графу $G$: $B(G)$ має вершину для кожної двозв'язної компоненти графу $G$ і дві вершини графу $B(G)$ суміжні, якщо відповідні два блоки поділяють (мають спільний) шарнір (у термінах Харарі — точка зчленування). Якщо $K_{1}$ — граф з однією вершиною, то $B(K_{1})$ за визначенням буде порожнім графом. $B(G)$ завідомо є блоковим — він має одну двозв'язну компоненту для кожної точки зчленування графу $G$ і кожна двозв'язна компонента, утворена таким шляхом, буде клікою. І навпаки, будь-який блоковий граф є графом $B(G)$ для деякого $G$. Якщо $G$ — дерево, то $B(G)$ збігається з реберним графом графу $G$.

Граф $B(B(G))$ має вершину для кожної точки зчленування графу $G$. Дві вершини суміжні в $B(B(G))$, якщо вони належать одному й тому ж блоку в $G$.

Література

• Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Graph classes: a survey. — Philadelphia : SIAM, 2005. — (SIAM monograps on discrete matematics). — ISBN 0-89871-432-X.