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

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

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

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

Опис

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

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). — .