Граф попарной совместимости

Граф (б), являющийся графами попарной совместимости деревьев (а) и (в)

Графы, не являющиеся графами попарной совместимости.

В теории граф графов $G$ является графом попарной совместимости (ГПК), если существует дерево $T$ и два неотрицательных действительных числа $d_{min}<d_{max}$ такой, что каждый узел $u'$ из $G$ имеет взаимно однозначное сопоставление с листовым узлом $u$ из $T$ такие, что два узла $u'$ и $v'$ соседствуют в $G$ тогда и только тогда, когда расстояние между $u$ и $v$ находятся в интервале $[d_{min},d_{max}]$ . ^[1]

Подклассы PCG включают графы не более семи вершин, циклы , леса , полные графы , интервальные графы и лестничные графы . ^[1] Однако существует граф с восемью вершинами, который, как известно, не является PCG. ^[2]

Связь с филогенетикой

Графы парной совместимости были впервые представлены Полом Кирни, Дж. Яном Манро и Дереком Филлипсом в контексте реконструкции филогении . При выборке из филогенетического дерева задача поиска узлов, расстояние пути которых лежит между заданными длинами $d_{min}<d_{max}$ эквивалентно поиску клики в связанной PCG. ^[3]

Сложность

Вычислительная сложность распознавания графа как PCG по состоянию на 2020 год неизвестна. ^[1] Однако связанная с этим проблема нахождения графа $G$ и выбор неграничных отношений $S$ PCG, содержащий $G$ как подграф и не имеющий ни одного ребра в $S$ известно, что он NP-труден. ^[2]

Задача поиска узлов в дереве, расстояние путей которых лежит между $d_{min}$ и $d_{max}$ известно, что она разрешима за полиномиальное время . Следовательно, если бы дерево можно было восстановить из ГКГ за полиномиальное время, то задача о клике на ГКГ тоже была бы полиномиальной. По состоянию на 2020 год ни одна из этих сложностей неизвестна. ^[1]

Ссылки

^ Jump up to: ^а ^б ^с ^д Рахман, доктор Саидур; Ахмед, Шариф (2020). «Обзор по графам попарной совместимости» . Международный журнал графов и комбинаторики AKCE . 17 (3): 788–795. дои : 10.1016/j.akcej.2019.12.011 . S2CID 225708614 . В эту статью включен текст, доступный по лицензии CC BY 4.0 .
^ Jump up to: ^а ^б Дюроше, Стефан; Мондал, Дебаджьоти; Рахман, доктор Саидур (2015). «На графах, не являющихся ПКГ» . Теоретическая информатика . 571 : 78–87. дои : 10.1016/j.tcs.2015.01.011 . ISSN 0304-3975 . S2CID 17290164 .
^ Кирни, Пол; Манро, Дж. Ян; Филлипс, Дерек (2003), Эффективное создание однородных выборок из филогенетических деревьев , Конспекты лекций по информатике, том. 2812, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 177–189, doi : 10.1007/978-3-540-39763-2_14 , ISBN 978-3-540-20076-5 , получено 13 февраля 2022 г.

[:0-1] Jump up to: ^а ^б ^с ^д Рахман, доктор Саидур; Ахмед, Шариф (2020). «Обзор по графам попарной совместимости» . Международный журнал графов и комбинаторики AKCE . 17 (3): 788–795. дои : 10.1016/j.akcej.2019.12.011 . S2CID 225708614 . В эту статью включен текст, доступный по лицензии CC BY 4.0 .

[:1-2] Jump up to: ^а ^б Дюроше, Стефан; Мондал, Дебаджьоти; Рахман, доктор Саидур (2015). «На графах, не являющихся ПКГ» . Теоретическая информатика . 571 : 78–87. дои : 10.1016/j.tcs.2015.01.011 . ISSN 0304-3975 . S2CID 17290164 .

[3] Кирни, Пол; Манро, Дж. Ян; Филлипс, Дерек (2003), Эффективное создание однородных выборок из филогенетических деревьев , Конспекты лекций по информатике, том. 2812, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 177–189, doi : 10.1007/978-3-540-39763-2_14 , ISBN 978-3-540-20076-5 , получено 13 февраля 2022 г.

[1]

[2]

[3]