Хордовый двудольный граф - Chordal bipartite graph - Wikipedia

в математический зона теория графов, а хордовый двудольный граф это двудольный граф 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 (мин (п², (п + м) бревно п)) для графика с п вершины и м края.^[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 г.

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

• Брандштадт, Андреас (1991), «Классы двудольных графов, связанные с хордовыми графами», Дискретная прикладная математика, 32: 51–60, Дои:10.1016 / 0166-218x (91) 90023-п.
• Брандштадт, Андреас; Драган, Федор; Чепой, Виктор; Волошин, Виталий (1998), "Двойные хордовые графы", Журнал SIAM по дискретной математике, 11: 437–455, Дои:10.1137 / s0895480193253415.
• Брандштадт, Андреас; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор, Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-X.
• Драган, Федор; Волошин, Виталий (1996), "Графики инцидентности биациклических гиперграфов", Дискретная прикладная математика, 68: 259–266, Дои:10.1016 / 0166-218x (95) 00070-8.
• Фарбер, М. (1983), "Характеризация сильно хордовых графов", Дискретная математика, 43 (2–3): 173–189, Дои:10.1016 / 0012-365X (83) 90154-1.
• Голумбик, Мартин Чарльз (1980), Алгоритмическая теория графов и совершенные графы, Academic Press, ISBN  0-12-289260-7.
• Хуанг, Цзин (2006), "Характеризация представлений хордовых двудольных графов", Журнал комбинаторной теории, серия B, 96 (5): 673–683, Дои:10.1016 / j.jctb.2006.01.001.
• Лу, Чин Лунг; Тан, Чуан И (2002), «Взвешенное эффективное доминирование на некоторых совершенных графах», Дискретная прикладная математика, 117: 163–182, Дои:10.1016 / s0166-218x (01) 00184-6.
• Любив, А. (1987), "Дважды лексические упорядочения матриц", SIAM Журнал по вычислениям, 16 (5): 854–879, Дои:10.1137/0216057.
• Мюллер, Хайко (1996), "Схемы Гамильтона в хордовых двудольных графах", Дискретная математика, 156: 291–298, Дои:10.1016 / 0012-365x (95) 00057-4.
• Мюллер, Хайко; Брандштадт, Андреас (1987), "NP-полнота дерева Штейнера и доминирующего множества для хордовых двудольных графов", Теоретическая информатика, 53: 257–265, Дои:10.1016/0304-3975(87)90067-3.
• Paige, R .; Тарьян, Р.Э. (1987), "Три алгоритма уточнения раздела", SIAM Журнал по вычислениям, 16 (6): 973–989, Дои:10.1137/0216062.
• Спинрад, Джереми (1993), "Двойное лексическое упорядочение плотных матриц 0–1", Письма об обработке информации, 45 (2): 229–235, Дои:10.1016 / 0020-0190 (93) 90209-П.
• Спинрад, Джереми (2003), Эффективные графические представления, Монографии Института Филдса, Американское математическое общество, ISBN  0-8218-2815-0.