YaChudo

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

Переглядів: 0. Оновлено 09.11.2026.

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

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

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

Опис

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

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

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

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

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

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

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

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

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


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

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

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

Примітки

  1. ↑ а б Kristina Vušković.  // Applicable Analysis and Discrete Mathematics. — 2010. — Т. 4, вип. 2. — С. 219–240. — DOI:10.2298/AADM100812027V.
  2. ↑ Блокові графи іноді помилково називають деревами Хусімі, за маєтком японського фізика Коді Хусімі, проте Хусімі розглядав кактус-графи, в яких будь-яка двозв'язна компонента є циклом.
  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.

Джерело: стаття у Вікіпедії та історія редагувань (автори).