В теории графов , разделе комбинаторной математики, блочный граф или дерево клик [1] — это тип неориентированного графа , в котором каждый двусвязный компонент (блок) является кликой .
Блочные графы иногда ошибочно называют деревьями Хусими (в честь Коди Хусими ) [2] , но это название более точно относится к кактусовым графам , графам, в которых каждый нетривиальный двусвязный компонент является циклом. [3]
Блочные графы можно охарактеризовать как графы пересечений блоков произвольных неориентированных графов. [4]
Блочные графы — это именно те графы, для которых для каждых четырех вершин u , v , x и y два наибольших из трех расстояний d ( u , v ) + d ( x , y ) , d ( u , x ) + d ( v , y ) и d ( u , y ) + d ( v , x ) всегда равны. [2] [5]
Они также имеют характеристику запрещенного графа как графы, которые не имеют ромбовидного графа или цикла из четырех или более вершин в качестве индуцированного подграфа ; то есть, они являются хордовыми графами без ромбов. [5] Они также являются птолемеевыми графами ( хордовыми дистанционно-наследственными графами ), в которых каждые два узла на расстоянии двух друг от друга соединены уникальным кратчайшим путем , [2] и хордовыми графами, в которых каждые две максимальные клики имеют не более одной общей вершины. [2]
Граф G является блочным графом тогда и только тогда, когда пересечение любых двух связных подмножеств вершин графа G пусто или связно. Следовательно, связные подмножества вершин в связном блочном графе образуют выпуклую геометрию , свойство, которое не верно для любых графов, которые не являются блочными графами. [6] Из-за этого свойства в связном блочном графе каждое множество вершин имеет уникальное минимальное связное надмножество, его замыкание в выпуклой геометрии. Связные блочные графы — это в точности графы, в которых существует уникальный индуцированный путь, соединяющий каждую пару вершин. [1]
Блочные графы являются хордовыми , дистанционно-наследственными и геодезическими . Дистанционно-наследственные графы — это графы, в которых любые два индуцированных пути между одними и теми же двумя вершинами имеют одинаковую длину, что ослабляет характеристику блочных графов как имеющих не более одного индуцированного пути между каждыми двумя вершинами. Поскольку и хордовые графы, и дистанционно-наследственные графы являются подклассами совершенных графов , блочные графы являются совершенными.
Каждое дерево , кластерный граф или граф ветряной мельницы является блочным графом.
Каждый блочный граф имеет коробочность не более двух. [7]
Блочные графы являются примерами псевдомедианных графов : для каждых трех вершин либо существует уникальная вершина, которая принадлежит кратчайшим путям между всеми тремя вершинами, либо существует уникальный треугольник, ребра которого лежат на этих трех кратчайших путях. [7]
Линейные графы деревьев — это в точности блочные графы, в которых каждая вершина разреза инцидентна не более чем двум блокам, или, что эквивалентно, блочные графы без клешней . Линейные графы деревьев использовались для поиска графов с заданным числом ребер и вершин, в которых наибольший индуцированный подграф, являющийся деревом, является наименьшим из возможных. [8]
Блочные графы, в которых каждый блок имеет размер не более трех, являются особым типом кактусового графа , треугольным кактусом. Самый большой треугольный кактус в любом графе может быть найден за полиномиальное время с помощью алгоритма для задачи четности матроида . Поскольку треугольные кактусовые графы являются планарными графами , самый большой треугольный кактус может быть использован в качестве приближения к самому большому планарному подграфу, важной подзадаче в планаризации . Как алгоритм приближения , этот метод имеет отношение приближения 4/9, наиболее известное для задачи максимального планарного подграфа. [9]
Если G — любой неориентированный граф, то блочный граф графа G , обозначаемый B ( G ), является графом пересечений блоков графа G : B ( G ) имеет вершину для каждого двусвязного компонента графа G , и две вершины графа B ( G ) являются смежными, если соответствующие два блока встречаются в вершине сочленения. Если K 1 обозначает граф с одной вершиной, то B ( K 1 ) определяется как пустой граф . B ( G ) обязательно является блочным графом: он имеет один двусвязный компонент для каждой вершины сочленения графа G , и каждый двусвязный компонент, образованный таким образом, должен быть кликой. И наоборот, каждый блочный граф является графом B ( G ) для некоторого графа G . [4] Если G — дерево, то B ( G ) совпадает с линейным графом графа G .
Граф B ( B ( G )) имеет одну вершину для каждой вершины сочленения графа G ; две вершины являются смежными в B ( B ( G )), если они принадлежат одному и тому же блоку в графе G . [4]