Блочный график - Block graph

Не путать с блок-схема или же гистограмма.
Блочный граф

В теория графов, раздел комбинаторной математики, блочный граф или же кликовое дерево[1] это тип неориентированный граф в котором каждый двусвязный компонент (блок) - это клика.

Блочные графы иногда ошибочно называют деревьями Хусими (после Коди Хусими ),[2] но это имя более правильно относится к кактус графики, графы, в которых каждая нетривиальная двусвязная компонента является циклом.[3]

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

Характеристика

Блочные графы - это именно те графы, для которых для каждых четырех вершин ты, v, Икс, и у, два наибольших из трех расстояний d(ты,v) + d(Икс,у),d(ты,Икс) + d(v,у),и d(ты,у) + d(v,Икс) всегда равны.[2][5]

У них также есть характеристика запрещенного графа как графики, не имеющие ромбовидный график или цикл из четырех или более вершин как индуцированный подграф; то есть это хордовые графы без ромбов.[5] Они также Птолемеевы графы (хордовый дистанционно-наследственные графы ), в котором каждые два узла на расстоянии два друг от друга соединены уникальным кратчайший путь,[2] и хордовые графы, в которых каждые две максимальные клики имеют не более одной общей вершины.[2]

График грамм является блочным графом тогда и только тогда, когда пересечение каждых двух связаны подмножества вершин грамм пуст или подключен. Следовательно, связные подмножества вершин связного блочного графа образуют выпуклая геометрия, свойство, которое неверно для любых графов, не являющихся блочными.[6] Благодаря этому свойству в связном блочном графе каждый набор вершин имеет уникальное минимальное связное надмножество, его замыкание в выпуклой геометрии. Связные блочные графы - это именно те графы, в которых есть единственное индуцированный путь соединяя каждую пару вершин.[1]

Связанные классы графов

Блок-графики хордовый, дистанционно-наследственный, и геодезический. Дистанционно-наследственные графы - это графы, в которых каждые два индуцированных пути между одними и теми же двумя вершинами имеют одинаковую длину, что является ослаблением характеристики блочных графов как имеющих не более одного индуцированного пути между каждыми двумя вершинами. Поскольку и хордовые графы, и графы с дистанционной наследственностью являются подклассами идеальные графики, блочные графы идеальны.

Каждый дерево, кластерный граф, или же график ветряка является блочным графом.

Каждый блочный граф имеет коробочка максимум два.[7]

Блочные графы являются примерами псевдо-медианные графики: для каждых трех вершин либо существует единственная вершина, которая принадлежит кратчайшим путям между всеми тремя вершинами, либо существует единственный треугольник, ребра которого лежат на этих трех кратчайших путях.[7]

В линейные графики деревьев - это в точности блочные графы, в которых каждая разрезанная вершина инцидентна не более чем двум блокам, или, что эквивалентно, без когтей блочные графы. Линейные графы деревьев использовались для поиска графов с заданным числом ребер и вершин, в которых наибольший индуцированный подграф, являющийся деревом, был как можно меньше.[8]

Блочные графы, в которых размер каждого блока не превышает трех, являются особым типом кактус граф, треугольный кактус. Самый большой треугольный кактус в любом графе можно найти в полиномиальное время используя алгоритм для проблема четности матроидов. Поскольку треугольные графы кактусов планарные графы, самый большой треугольный кактус можно использовать в качестве приближения к самому большому плоскому подграфу, что является важной подзадачей в планаризация. Как алгоритм аппроксимации, этот метод имеет коэффициент аппроксимации 4/9, наиболее известная проблема максимального плоского подграфа.[9]

Блочные графы неориентированных графов

Если грамм любой неориентированный граф, блочный граф грамм, обозначенный B(грамм), это граф пересечений блоков грамм: B(грамм) имеет вершину для каждой двусвязной компоненты грамм, и две вершины B(грамм) смежны, если соответствующие два блока пересекаются в вершине сочленения. Если K1 обозначает граф с одной вершиной, то B(K1) определяется как пустой график. B(грамм) обязательно является блочным графом: у него есть одна двусвязная компонента для каждой вершины сочленения грамм, и каждый образованный таким образом двусвязный компонент должен быть кликой. И наоборот, каждый блочный граф - это граф B(грамм) для некоторого графа грамм.[4] Если грамм это дерево, тогда B(грамм) совпадает с линейный график из грамм.

График B(B(грамм)) имеет по одной вершине для каждой вершины сочленения грамм; две вершины смежны в B(B(грамм)), если они принадлежат одному блоку в грамм.[4]

Рекомендации

  1. ^ а б Вушкович, Кристина (2010), «Графики без четных отверстий: обзор» (PDF), Применимый анализ и дискретная математика, 4 (2): 219–240, Дои:10.2298 / AADM100812027V.
  2. ^ а б c d Ховорка, Эдвард (1979), "О метрических свойствах некоторых графов клик", Журнал комбинаторной теории, серия B, 27 (1): 67–74, Дои:10.1016/0095-8956(79)90069-8.
  3. ^ См., Например, МИСТЕР0659742, обзор Роберта Э. Джеймисона в 1983 году другой статьи, в которой блочные графы называются деревьями Хусими; Джеймисон связывает ошибку с ошибкой в ​​книге Мехди Бехзад и Гэри Чартранд.
  4. ^ а б c Харари, Фрэнк (1963), "Характеристика блочных графов", Канадский математический бюллетень, 6 (1): 1–6, Дои:10.4153 / cmb-1963-001-x, HDL:10338.dmlcz / 101399.
  5. ^ а б Бандельт, Ханс-Юрген; Малдер, Генри Мартин (1986), "Дистанционно-наследственные графы", Журнал комбинаторной теории, серия B, 41 (2): 182–208, Дои:10.1016/0095-8956(86)90043-2.
  6. ^ Эдельман, Пол Х .; Джеймисон, Роберт Э. (1985), "Теория выпуклых геометрий", Geometriae Dedicata, 19 (3): 247–270, Дои:10.1007 / BF00149365, S2CID  123491343.
  7. ^ а б Блочные графики, Информационная система о включениях классов графов.
  8. ^ Эрдеш, Пол; Сакс, Михаил; Сос, Вера Т. (1986), «Максимальные индуцированные деревья в графах» (PDF), Журнал комбинаторной теории, серия B, 41 (1): 61–79, Дои:10.1016/0095-8956(86)90028-6.
  9. ^ Кэлинеску, Груя; Фернандес, Кристина Джи; Финклер, Ульрих; Карлофф, Ховард (2002), "Алгоритм лучшего приближения для поиска плоских подграфов", Журнал алгоритмов, 2, 27 (2): 269–302, Дои:10.1006 / jagm.1997.0920, S2CID  8329680