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

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

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

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

Опис

Блокові графи — це точно ті графи, в яких для кожних чотирьох вершин ${\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].

Блокові графи є прикладом псевдо- медіанних графів^[ru] — для будь-яких трьох вершин або існує єдина вершина, що лежить на трьох найкоротших шляхах між цими трьома вершинами, або існує єдиний трикутник, ребра якого лежать на цих найкоротших шляхах.[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].

Примітки

1. Kristina Vušković.  // Applicable Analysis and Discrete Mathematics. — 2010. — Т. 4, вип. 2. — С. 219–240. — DOI:10.2298/AADM100812027V.
2. Блокові графи іноді помилково називають деревами Хусімі, за маєтком японського фізика Коді Хусімі^[en], проте Хусімі розглядав кактус-графи, в яких будь-яка двозв'язна компонента є циклом.
3. Frank Harary.  // Canadian Mathematical Bulletin. — 1963. — Т. 6, вип. 1. — С. 1–6. — DOI:10.4153/cmb-1963-001-x.
4. Edward Howorka.  // Journal of Combinatorial Theory, Series B. — 1979. — Вип. 1. — С. 67–74.
5. Brandstädt, Le, Spinrad, 2005; стор. 151, Theorem 10.2.6
6. Hans-Jürgen Bandelt, Henry Martyn Mulder.  // Journal of Combinatorial Theory, Series B. — 1986. — Вип. 2. — С. 182–208.
7. Brandstädt, Le, Spinrad, 2005; стор. 130, Corollary 8.4.2
8. Paul H. Edelman, Robert E. Jamison.  // Geometriae Dedicata. — 1985. — Вип. 3. — С. 247–270.
9. Має місце така ієрархія класів графів:
10. Блоковые графы [Архівовано 21 листопада 2019 у Wayback Machine.], Информационная система о иерархии классов графов
11. Brandstädt, Le, Spinrad, 2005 Стр. 54, Глава 4.5 Boxicity, intersection dimention, and dot product
12. Paul Erdős, Michael Saks, Vera T. Sós.  // Journal of Combinatorial Theory, Series B. — 1986. — Т. 41, вип. 1. — С. 61–79. — DOI:10.1016/0095-8956(86)90028-6.
13. Ф. Харари. Теория графов. — Москва : УРСС, 2003. — ISBN 5-354-00301. Глава 3. Блоки, стор. 41-46

Література

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