Хордальное завершение
В теории графов , разделе математики, хордальное пополнение данного неориентированного графа G — это хордальный граф на том же множестве вершин, который имеет G в качестве подграфа.Минимальное хордальное завершение — это хордальное завершение, при котором любой граф, образованный удалением ребра, больше не будет хордальным завершением. Минимальное хордальное завершение — это хордальное завершение с наименьшим количеством ребер.
Другой тип хордального завершения, который минимизирует размер максимальной клики в результирующем хордальном графе может использоваться для определения дерева ширины G. , Хордальные дополнения также можно использовать для характеристики некоторых других классов графов, включая графы без AT, без когтей графы без AT и кографы .
Минимальное завершение хорды было одной из двенадцати вычислительных задач, сложность которых была указана как открытая в книге 1979 года « Компьютеры и трудноразрешимость» .Приложения хордального завершения включают моделирование проблемы минимизации заполнения при выполнении исключения Гаусса на разреженных симметричных матрицах и реконструкцию филогенетических деревьев .
Хордальные пополнения графа иногда называют триангуляциями. [1] но этот термин неоднозначен даже в контексте теории графов, поскольку он также может относиться к максимальным планарным графам .
Связанные семейства графов
[ редактировать ]Граф G является графом, свободным от AT , тогда и только тогда, когда все его минимальные хордальные пополнения являются графами интервалов . G является графом без клешней без AT тогда и только тогда, когда все его минимальные хордальные пополнения являются собственными графами интервалов. И G является кографом тогда и только тогда, когда все его минимальные хордальные пополнения являются тривиально совершенными графами . [1]
Граф G имеет древовидную ширину не более k тогда и только тогда, когда G имеет хотя бы одно хордальное завершение, максимальный размер клики которого не превышает k + 1 . Ширина пути не превышает k тогда и только тогда, когда G имеет хотя бы одно хордальное завершение, которое представляет собой граф интервалов с максимальным размером клики не более k + 1 . Его пропускная способность не превышает k тогда и только тогда, когда G имеет хотя бы одно хордальное завершение, которое является правильным графом интервалов с максимальным размером клики не более k + 1 . [2] И он имеет глубину дерева k тогда и только тогда, когда он имеет хотя бы одно хордальное завершение, которое является тривиально совершенным графом с максимальным размером клики не более k . [3]
Приложения
[ редактировать ]Первоначальное применение хордального завершения, описанное в книге «Компьютеры и трудноразрешимость», включает в себя исключение Гаусса для разреженных матриц . В процессе исключения Гаусса желательно минимизировать заполнение коэффициентов матрицы, которые изначально были нулевыми, но позже стали ненулевыми, поскольку необходимость вычисления значений этих коэффициентов замедляет работу алгоритма. Шаблон ненулевых значений в разреженной симметричной матрице может быть описан неориентированным графом (имеющим матрицу в качестве матрицы смежности ); шаблон ненулевых значений в заполненной матрице всегда представляет собой хордальный граф, таким образом любое минимальное хордальное завершение соответствует шаблону заполнения. Если дано хордальное завершение графа, последовательность шагов, в которых необходимо выполнить исключение Гаусса для достижения этого шаблона заполнения, может быть найдена путем вычисления порядка исключения полученного хордального графа. Таким образом, проблему минимального заполнения можно рассматривать как эквивалент проблемы минимального завершения хорды. [4] В этом приложении плоские графы могут возникать при решении двумерных систем конечных элементов; следует из теоремы о плоском сепараторе , что каждый планарный граф с n вершинами имеет хордальное пополнение с не более чем O ( n log n ) ребрами. [5]
Другое приложение исходит из филогении , проблемы реконструкции эволюционных деревьев, например, деревьев организмов, подверженных генетическим мутациям, или деревьев наборов древних рукописей, скопированных друг с другом из-за ошибок переписчиков. Если предположить, что каждая генетическая мутация или ошибка переписчика происходит только один раз, то получится идеальная филогения — дерево, в котором виды или рукописи, имеющие какую-либо конкретную характеристику, всегда образуют связанное поддерево. Как описывает Бунеман (1974) , существование идеальной филогении можно смоделировать как проблему хордального завершения. Рисуется «граф перекрытия» G , в котором вершины представляют собой значения атрибутов (конкретный выбор для некоторых характеристик вида или рукописи), а ребра представляют собой пары значений атрибутов, которые являются общими по крайней мере для одного вида. Вершины графа могут быть раскрашены в соответствии с идентичностью характеристик, из которых происходит каждое значение атрибута, так, чтобы общее количество цветов равнялось количеству характеристик, использованных для получения филогении. Тогда совершенная филогения существует тогда и только тогда, когда G имеет хордальное завершение, сохраняющее раскраску. [6]
Вычислительная сложность
[ редактировать ]она указана как открытая проблема Хотя в книге 1979 года «Компьютеры и трудноразрешимость» , [7] вычислительная сложность проблемы минимального хордального завершения (также называемой проблемой минимального заполнения ) была быстро решена: Яннакакис (1981) показал, что она NP-полна . [8] Если минимальное хордальное пополнение добавляет k ребер в граф G , то можно найти хордальное пополнение, используя не более 8 k 2 добавленные ребра за полиномиальное время. [9] Проблема поиска оптимального набора из k ребер для добавления также может быть решена с помощью управляемого алгоритма с фиксированным параметром , за время, полиномиальное по размеру графа и субэкспоненциальное по k . [10]
Ширина дерева (минимальный размер клики хордального завершения) и связанные с ним параметры, включая ширину пути и глубину дерева, также являются NP-полными для вычисления и (если только P = NP) не могут быть аппроксимированы за полиномиальное время с точностью до постоянного коэффициента их оптимальных значений. ; однако алгоритмы аппроксимации с логарифмическими коэффициентами аппроксимации. для них известны [11]
Проблемы минимального заполнения и ширины дерева могут быть решены за экспоненциальное время . Точнее, для n -вершинного графа время равно O (1,9601 н ) . [12]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Парра, Андреас; Шеффлер, Петра (1997), «Характеристики и алгоритмические применения вложений хордальных графов», 4-й семинар Твенте по графам и комбинаторной оптимизации (Энсхеде, 1995), Дискретная прикладная математика , 79 (1–3): 171–188, doi : 10.1016 /S0166-218X(97)00041-3 , МР 1478250 .
- ^ Каплан, Хаим; Шамир, Рон (1996), «Проблемы ширины пути, пропускной способности и завершения для правильных интервальных графов с небольшими кликами», SIAM Journal on Computing , 25 (3): 540–561, doi : 10.1137/S0097539793258143 , MR 1390027 .
- ^ Эппштейн, Дэвид (15 ноября 2012 г.), Параметры графа и клики в суперграфах .
- ^ Роуз, Дональд Дж. (1972), «Теоретико-графовое исследование численного решения разреженных положительно определенных систем линейных уравнений», Теория графов и вычисления , Academic Press, Нью-Йорк, стр. 183–217, MR 0341833 .
- ^ Чанг, Франция ; Мамфорд, Дэвид (1994), «Хордальные пополнения плоских графов», Журнал комбинаторной теории , серия B, 62 (1): 96–106, doi : 10.1006/jctb.1994.1056 , MR 1290632 .
- ^ Бунеман, Питер (1974), «Характеристика графов жестких цепей», Discrete Mathematics , 9 (3): 205–212, doi : 10.1016/0012-365X(74)90002-8 , MR 0357218 .
- ^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . , [ОТКРЫТЬ4], с. 286; обновление, с. 339.
- ^ Яннакакис, Михалис (1981), «Вычисление минимального заполнения является NP-полным», SIAM Journal on Algebraic and Discrete Methods , 2 (1): 77–79, CiteSeerX 10.1.1.128.192 , doi : 10.1137/0602010 , hdl : 10338.dmlcz/140775 , MR 0604513 .
- ^ Натанзон, Ассаф; Шамир, Рон; Шаран, Родед (2000), «Алгоритм полиномиальной аппроксимации для задачи минимального заполнения», SIAM Journal on Computing , 30 (4): 1067–1079, doi : 10.1137/S0097539798336073 , MR 1786752 .
- ^ Фомин Федор Владимирович; Виллангер, Ингве (2013), «Субэкспоненциальный параметризованный алгоритм для минимального заполнения», SIAM Journal on Computing , 42 (6): 2197–2216, arXiv : 1104.2230 , doi : 10.1137/11085390X , MR 3138120 .
- ^ Бодлендер, Ханс Л .; Гилберт, Джон Р.; Хафштейнссон, Хьялмтир; Клокс, Тон (1995), «Аппроксимация ширины дерева, ширины пути, фронтального размера и кратчайшего дерева исключения», Journal of Algorithms , 18 (2): 238–255, doi : 10.1006/jagm.1995.1009 , MR 1317666 .
- ^ Фомин Федор Владимирович; Крач, Дитер; Тодинка, Иоан (2004), «Точные (экспоненциальные) алгоритмы для ширины дерева и минимального заполнения», Автоматы, языки и программирование: 31-й международный коллоквиум, ICALP 2004, Турку, Финляндия, 12–16 июля 2004 г., Материалы лекций , конспекты лекций в области компьютерных наук, вып. 3142, Springer-Verlag, стр. 568–580, номер документа : 10.1007/978-3-540-27836-8_49 .