Хордовый двудольный граф - Википедия - Chordal bipartite graph

в математический зона теория графов, а хордовый двудольный граф это двудольный граф B = (Икс,Y,E), в котором каждый цикл длиной не менее 6 дюймов B имеет аккорд, то есть ребро, соединяющее две вершины, находящиеся на расстоянии> 1 друг от друга в цикле.[1]Лучшим названием было бы слабо хордовый и двудольный, поскольку хордовые двудольные графы, как правило, не являются хордовый как показывает индуцированный цикл длины 4.

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

Хордовые двудольные графы имеют различные характеристики в терминах идеальные порядки исключения, гиперграфы и матрицы. Они тесно связаны с сильно хордовые графы. По определению, хордовые двудольные графы имеют запрещенная характеристика подграфа как графы, не содержащие индуцированный цикл длиной 3 или длиной не менее 5 (так называемые отверстия) в качестве индуцированный подграф. Таким образом, график грамм хордально двудольный тогда и только тогда, когда грамм является без треугольников и без дыр. В Голумбик (1980) упоминаются две другие характеристики: B хордально двудольным тогда и только тогда, когда каждый минимальный разделитель ребер индуцирует полный двудольный подграф в B тогда и только тогда, когда каждый индуцированный подграф является полностью исключительным двудольным.

Мартин Фарбер показал: граф является сильно хордовым тогда и только тогда, когда двудольный граф инцидентности его кликового гиперграфа хордально двудольный. [2]

Аналогичная характеризация имеет место для замкнутого соседнего гиперграфа: граф является сильно хордовым тогда и только тогда, когда двудольный граф инцидентности его замкнутого окрестностного гиперграфа хордально двудольный.[3]

Еще один результат, найденный Элиасом Дальхаусом: двудольный граф B = (Икс,Y,E) хордально двудольна тогда и только тогда, когда разделенный график в результате создания Икс клика сильно хордовая.[4]

Двудольный граф B = (Икс,Y,E) хордально двудольный тогда и только тогда, когда каждый индуцированный подграф B имеет максимум Иксупорядочение соседства и максимальное упорядочение Y-соседства.[5]

Различные результаты описывают связь между хордовыми двудольными графами и полностью сбалансированными соседними гиперграфами двудольных графов.[6]

Характеристика хордовых двудольных графов в терминах графов пересечений, связанных с гиперграфами, дается в.[7]

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

Признание

Хордовые двудольные графы можно распознать во времени O (мин (п2, (п + м) бревно п)) для графика с п вершины и м края.[9]

Сложность проблем

Различные проблемы, такие как гамильтонов цикл,[10] Дерево Штейнера [11] и эффективное господство [12] остаются NP-полными на хордовых двудольных графах.

Различные другие проблемы, которые могут быть эффективно решены для двудольных графов, могут быть решены более эффективно для хордовых двудольных графов, как обсуждается в [13]

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

Каждый хордовый двудольный граф является модульный граф. Хордовые двудольные графы включают полные двудольные графы и двудольный дистанционно-наследственные графы.[14]

Примечания

  1. ^ Голумбик (1980), п. 261, Brandstädt, Le & Spinrad (1999), Определение 3.4.1, с. 43.
  2. ^ Фарбер (1983); Brandstädt, Le & Spinrad (1999), Теорема 3.4.1, с. 43.
  3. ^ Brandstädt (1991)
  4. ^ Brandstädt, Le & Spinrad (1999), Следствие 8.3.2, с. 129.
  5. ^ Драган и Волошин (1996)
  6. ^ Brandstädt, Le & Spinrad (1999), Теоремы 8.2.5, 8.2.6, с. 126–127.
  7. ^ Хуан (2006)
  8. ^ Фарбер (1983)
  9. ^ Любив (1987); Пейдж и Тарджан (1987); Спинрад (1993); Спинрад (2003).
  10. ^ Мюллер (1996)
  11. ^ Мюллер и Брандштедт (1987)
  12. ^ Лу и Тан (2002)
  13. ^ Спинрад (2003).
  14. ^ Хордовые двудольные графы, Информационная система по классам графов и их включениям, получено 30 сентября 2016 г.

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