В теории графов , разделе комбинаторной математики, блочный граф или дерево клик [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) . ) являются смежными, если соответствующие два блока встречаются в вершине сочленения. Если K1 обозначает граф с одной вершиной, то B ( K1 ) определяется как пустой граф . B ( G ) обязательно является блочным графом: он имеет один двусвязный компонент для каждой вершины сочленения G , и каждый двусвязный компонент, образованный таким образом, должен быть кликой. И наоборот, каждый блочный граф является графом B ( G ) для некоторого графа G. [4] Если G — дерево, то B ( G ) совпадает с линейным графом G.
Граф B ( B ( G )) имеет одну вершину для каждой вершины сочленения G ; две вершины смежны в B ( B ( G )), если они принадлежат одному и тому же блоку в G. [4]