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

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

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

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

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

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

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

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

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

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

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

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