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

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

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

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

Описание

Блоковые графы — это в точности те графы, в которых для каждых четырёх вершин $u$, $v$, $x$ и $y$ наибольшие два из трёх расстояний $d(u,v)+d(x,y)$, $d(u,x)+d(v,y)$, $d(u,y)+d(v,x)$ всегда равны.

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

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

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

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

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

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

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

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

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

Блоковый граф для заданного графа $G$ (обозначается $B(G)$) — граф пересечений блоков графа $G$: $B(G)$ имеет вершину для каждой двусвязной компоненты графа $G$ и две вершины графа $B(G)$ смежны, если соответствующие два блока разделяют (имеют общий) шарнир (в терминах Харари — точка сочленения). Если $K_{1}$ — граф с одной вершиной, то $B(K_{1})$ по определению будет пустым графом. $B(G)$ заведомо является блочным — он имеет одну двусвязную компоненту для каждой точки сочленения графа $G$ и каждая двусвязная компонента, образованная таким путём, будет кликой. Обратно, любой блоковый граф является графом $B(G)$ для некоторого $G$. Если $G$ — дерево, то $B(G)$ совпадает с рёберным графом графа $G$.

Граф $B(B(G))$ имеет вершину для каждой точки сочленения графа $G$. Две вершины смежны в $B(B(G))$, если они принадлежат одному и тому же блоку в $G$.

Литература

• 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.