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