Блок-граф
В теории графов — раздел комбинаторной математики, блочный граф или дерево клики. [1] — это тип неориентированного графа , в котором каждая двусвязная компонента (блок) является кликой .
Блочные графы иногда ошибочно называют деревьями Хусими (в честь Коди Хусими ), [2] но это название более точно относится к графам-кактусам , графам, в которых каждый нетривиальный компонент двусвязности является циклом. [3]
Блочные графы можно охарактеризовать как графы пересечений блоков произвольных неориентированных графов. [4]
Характеристика
[ редактировать ]Блочные графы — это именно те графы, для которых для каждых четырех вершин u , v , x и y наибольшие два из трех расстояний d ( u , v ) + d ( x , y ) , d ( ты , Икс ) + 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 . обозначает граф с одной вершиной, то K1 ) определяется B как пустой граф ( B ( G ) обязательно является блочным графом: он имеет один двусвязный компонент для каждой вершины сочленения G , и каждый двусвязный компонент, образованный таким образом, должен быть кликой. наоборот, каждый блочный граф является графом B ( G ) для некоторого графа G. И [4] Если G — дерево, то B ( G совпадает с линейным графиком дерева G. )
Граф B ( B ( G )) имеет одну вершину для каждой вершины сочленения G ; две вершины смежны в B ( B ( G если они принадлежат одному и тому же блоку в G. )) , [4]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Вушкович, Кристина (2010), «Графы без четных дырок: обзор» (PDF) , Applicable Analysis and Discrete Mathematics , 4 (2): 219–240, doi : 10.2298/AADM100812027V .
- ^ Jump up to: Перейти обратно: а б с д Ховорка, Эдвард (1979), «О метрических свойствах некоторых графов клик», Журнал комбинаторной теории , серия B , 27 (1): 67–74, doi : 10.1016/0095-8956(79)90069-8 .
- ^ См., например, MR. 0659742 , обзор Роберта Э. Джеймисона 1983 года на другую статью, в которой блочные графы называются деревьями Хусими; Джеймисон приписывает ошибку ошибке в книге Мехди Бехзада и Гэри Чартранда .
- ^ Jump up to: Перейти обратно: а б с Харари, Фрэнк (1963), «Характеристика блок-графов», Canadian Mathematical Bulletin , 6 (1): 1–6, doi : 10.4153/cmb-1963-001-x , hdl : 10338.dmlcz/101399 .
- ^ Jump up to: Перейти обратно: а б Бандельт, Ханс-Юрген; Малдер, Генри Мартин (1986), «Дистанционно-наследственные графы», Журнал комбинаторной теории , серия B , 41 (2): 182–208, doi : 10.1016/0095-8956(86)90043-2 .
- ^ Эдельман, Пол Х.; Джеймисон, Роберт Э. (1985), «Теория выпуклой геометрии», Geometriae Dedicata , 19 (3): 247–270, doi : 10.1007/BF00149365 , S2CID 123491343 .
- ^ Jump up to: Перейти обратно: а б Блочные графы , Информационная система по включению классов графов.
- ^ Эрдеш, Пол ; Сакс, Майкл ; Сос, Вера Т. (1986), «Максимально индуцированные деревья в графах» (PDF) , Журнал комбинаторной теории , серия B , 41 (1): 61–79, doi : 10.1016/0095-8956(86)90028-6 .
- ^ Кэлинеску, Груя; Фернандес, Кристина Г .; Финклер, Ульрих; Карлофф, Ховард (2002), «Алгоритм лучшего приближения для поиска плоских подграфов», Journal of Algorithms , 2, 27 (2): 269–302, doi : 10.1006/jagm.1997.0920 , S2CID 8329680