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

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

Блоковые графы — это в точности те графы, в которых для каждых четырёх вершин ${\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.

Для улучшения этой статьи по математике желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.