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

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

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

Блоковые графы можно описать графами пересечений блоков произвольных неориентированных графов[3].

Описание

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

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

Граф является блоковым тогда и только тогда, когда пересечение любых двух связных подмножеств вершин графа либо пусто, либо связно. Таким образом, связные подмножества вершин в связном блоковом графе образуют выпуклую геометрию, и этим свойством не обладает никакой другой вид графов[8]. По причине этого свойства в связном блоковом графе любое множество вершин имеет единственное минимальное связное надмножество, замыкание множества в выпуклой геометрии. Связные блоковые графы — это в точности те графы, в которых существует единственный порождённый путь, соединяющий любые две пары вершин[1].

Связанные классы графов

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

Любое дерево является блоковым графом. Другой пример класса блоковых графов дают мельницы.

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

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

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

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

Блоковый граф для заданного графа (обозначается ) — граф пересечений блоков графа : имеет вершину для каждой двусвязной компоненты графа и две вершины графа смежны, если соответствующие два блока разделяют (имеют общий) шарнир (в терминах Харари — точка сочленения)[13]. Если — граф с одной вершиной, то по определению будет пустым графом. заведомо является блочным — он имеет одну двусвязную компоненту для каждой точки сочленения графа и каждая двусвязная компонента, образованная таким путём, будет кликой. Обратно, любой блоковый граф является графом для некоторого [3]. Если  — дерево, то совпадает с рёберным графом графа .

Граф имеет вершину для каждой точки сочленения графа . Две вершины смежны в , если они принадлежат одному и тому же блоку в [3].

Примечания

  1. Kristina Vušković. Even-hole-free graphs: A survey // Applicable Analysis and Discrete Mathematics. — 2010. Т. 4, вып. 2. С. 219–240. doi:10.2298/AADM100812027V.
  2. Блоковые графы иногда ошибочно называют деревьями Хусими, по имении японского физика Коди Хусими), однако Хусими рассматривал Кактус (теория графов) — графы, в которых любая двусвязная компонента является циклом.
  3. Frank Harary. A characterization of block-graphs // Canadian Mathematical Bulletin. — 1963. Т. 6, вып. 1. С. 1–6. doi:10.4153/cmb-1963-001-x.
  4. Edward Howorka. On metric properties of certain clique graphs // Journal of Combinatorial Theory, Series B. — 1979. Т. 27, вып. 1. С. 67–74. doi:10.1016/0095-8956(79)90069-8.
  5. Brandstädt, Le, Spinrad, 2005; стр. 151, Theorem 10.2.6
  6. Hans-Jürgen Bandelt, Henry Martyn Mulder. Distance-hereditary graphs // Journal of Combinatorial Theory, Series B. — 1986. Т. 41, вып. 2. С. 182–208. doi:10.1016/0095-8956(86)90043-2.
  7. Brandstädt, Le, Spinrad, 2005; стр. 130, Corollary 8.4.2
  8. Paul H. Edelman, Robert E. Jamison. The theory of convex geometries // Geometriae Dedicata. — 1985. Т. 19, вып. 3. С. 247–270. doi:10.1007/BF00149365.
  9. Имеет место следующая иерархия классов графов:
    Блоковые Птолемея строго хордальные хордальные
    Brandstädt, Le, Spinrad, 2005 Стр. 126, Глава 8.2 Further acyclicity types; clique and neighborhood hypergraphs
  10. Блоковые графы, Информационная система о иерархии классов графов
  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. Maximum induced trees in graphs // 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 monographs on discrete mathematics). — ISBN 0-89871-432-X.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.