WikiDer > Хордовый двудольный граф - Википедия
в математический зона теория графов, а хордовый двудольный граф это двудольный граф 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]
Примечания
- ^ Голумбик (1980), п. 261, Brandstädt, Le & Spinrad (1999), Определение 3.4.1, с. 43.
- ^ Фарбер (1983); Brandstädt, Le & Spinrad (1999), Теорема 3.4.1, с. 43.
- ^ Brandstädt (1991)
- ^ Brandstädt, Le & Spinrad (1999), Следствие 8.3.2, с. 129.
- ^ Драган и Волошин (1996)
- ^ Brandstädt, Le & Spinrad (1999), Теоремы 8.2.5, 8.2.6, с. 126–127.
- ^ Хуан (2006)
- ^ Фарбер (1983)
- ^ Любив (1987); Пейдж и Тарджан (1987); Спинрад (1993); Спинрад (2003).
- ^ Мюллер (1996)
- ^ Мюллер и Брандштедт (1987)
- ^ Лу и Тан (2002)
- ^ Спинрад (2003).
- ^ Хордовые двудольные графы, Информационная система по классам графов и их включениям, получено 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.