Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с блок-схемой или гистограммой .
Блочный граф

В теории графов , ветвь комбинаторной математики, блочный граф или дерево клик [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]

Ссылки [ править ]

  1. ^ Б Vušković, Кристина (2010), "Even-неповрежденные графики: Обзор" (PDF) , Применимый анализ и дискретная математика , 4 (2): 219-240, DOI : 10,2298 / AADM100812027V.
  2. ^ Б с д Howorka, Эдвард (1979), "О метрических свойствах некоторых графов клики", Журнал комбинаторной теории, Series B , 27 (1): 67-74, DOI : 10.1016 / 0095-8956 (79) 90069 -8.
  3. ^ См., Например, MR 0659742 , обзор Роберта Э. Джеймисона в 1983 году другой статьи, в которой блочные графы называются деревьями Хусими; Джеймисон объясняет ошибку ошибкой в ​​книге Мехди Бехзада и Гэри Чартранда .
  4. ^ a b c Харари, Франк (1963), «Характеристика блочных графов», Canadian Mathematical Bulletin , 6 (1): 1–6, doi : 10.4153 / cmb-1963-001-x , hdl : 10338.dmlcz / 101399.
  5. ^ a b Бандельт, Ганс-Юрген; Малдер, Генри Мартин (1986), "Дистанционно-наследственная графы", Журнал комбинаторной теории, серии B , 41 (2): 182-208, DOI : 10,1016 / 0095-8956 (86) 90043-2.
  6. ^ Эдельман, Пол Х .; Джемисон, Роберт Е. (1985), "Теория выпуклых геометрий", Geometriae Dedicata , 19 (3): 247-270, DOI : 10.1007 / BF00149365 , S2CID 123491343 .
  7. ^ a b Блочные графы , Информационная система по включению классов графов.
  8. ^ Erdős, Пол ; Сакс, Майкл ; Сос, Вера Т. (1986), «Максимальные индуцированные деревья в графах» (PDF) , Журнал комбинаторной теории, серия B , 41 (1): 61–79, DOI : 10.1016 / 0095-8956 (86) 90028-6 .
  9. ^ Calinescu, Gruia; Фернандес, Кристина Дж. Финклер, Ульрих; Карлофф, Говард (2002), "A Better Аппроксимация Алгоритм нахождения плоских подграфов", журнал алгоритмов , 2, 27 (2): 269-302, DOI : 10,1006 / jagm.1997.0920 , S2CID 8329680