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

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

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

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

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

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

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

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

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

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

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

• 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.