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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Блоковий граф

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

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

Блокові графи — це точно ті графи, в яких для кожних чотирьох вершин , , і найбільші дві з трьох відстаней , , завжди рівні[4][5][6].

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

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

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

[ред. | ред. код]

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

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

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

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

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


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

[ред. | ред. код]

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

Граф має вершину для кожної точки зчленування графу . Дві вершини суміжні в , якщо вони належать одному й тому ж блоку в [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.