Хордовый граф - Chordal graph

Цикл (черный) с двумя аккордами (зеленый). Что касается этой части, то график хордовый. Однако удаление одного зеленого ребра приведет к нехордальному графу. В самом деле, другой зеленый край с тремя черными краями будет образовывать цикл длиной четыре без хорд.

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

Хордовые графы - это подмножество идеальные графики. Их можно узнать в линейное время, и несколько проблем, которые сложно решить для других классов графов, таких как раскраска графика может быть решена за полиномиальное время, когда вход хордовый. В ширина дерева произвольного графа можно охарактеризовать размером клики в хордовых графах, которые его содержат.

Идеальное исключение и эффективное распознавание

А идеальный порядок исключения в графе - это такой порядок вершин графа, что для каждой вершины v, v и соседи из v что происходит после v в форме заказа клика. Граф является хордовым тогда и только тогда, когда он имеет идеальный порядок исключения.^[3]

Роза, Люкер и Тарджан (1976) (смотрите также Habib et al. 2000 г. ) показывают, что идеальный порядок исключения хордального графа может быть эффективно найден с помощью алгоритма, известного как лексикографический поиск в ширину. Этот алгоритм поддерживает разбиение вершин графа на последовательность множеств; изначально эта последовательность состоит из единого набора со всеми вершинами. Алгоритм многократно выбирает вершину v из самого раннего набора в последовательности, который содержит ранее невыбранные вершины, и разбивает каждый набор S последовательности на два меньших подмножества, первое из которых состоит из соседей v в S а второй состоит из несоседей. Когда этот процесс разделения был выполнен для всех вершин, последовательность наборов будет иметь одну вершину на множество, что является обратным порядку идеального исключения.

Поскольку и этот лексикографический процесс поиска в ширину, и процесс проверки того, является ли упорядочение идеальным упорядочением исключения, могут выполняться за линейное время, можно распознавать хордовые графы за линейное время. В задача сэндвича с графом на хордовых графах NP-полна^[4]тогда как проблема пробного графа на хордовых графах имеет полиномиальную временную сложность.^[5]

Множество всех порядков идеального исключения хордального графа можно смоделировать как основные слова из антиматроид; Chandran et al. (2003) используйте эту связь с антиматроидами как часть алгоритма для эффективного перечисления всех порядков идеального исключения данного хордального графа.

Максимальные клики и раскраска графов

Еще одно применение порядков безупречного исключения - это поиск максимума клика хордального графа за полиномиальное время, в то время как та же проблема для общих графов НП-полный. В более общем смысле, хордовый граф может иметь только линейно много максимальные клики, а нехордовых графов может быть экспоненциально много. Чтобы перечислить все максимальные клики хордового графа, просто найдите идеальный порядок исключения, сформируйте клику для каждой вершины v вместе с соседями v это позже, чем v в порядке идеального исключения и проверьте, является ли каждая из результирующих клик максимальной.

В кликовые графы хордовых графов являются дуально-хордовые графы.^[6]

Наибольшая максимальная клика - это максимальная клика, и, поскольку хордовые графы идеальны, размер этой клики равен хроматическое число хордального графа. Хордовые графы отлично поддается заказу: оптимальную окраску можно получить, применив жадная окраска алгоритм к вершинам в обратном порядке идеального исключения.^[7]

В хроматический полином хордального графа легко вычислить. Найдите идеальный порядок исключения ${ displaystyle v_ {1}, v_ {2}, ldots, v_ {n}.}$ Позволять N_я равно количеству соседей v_я что будет после v_я в таком порядке. Например, N_п = 0. Хроматический полином равен ${ displaystyle (x-N_ {1}) (x-N_ {2}) cdots (x-N_ {n}).}$ (Последний фактор просто Икс, так Икс делит многочлен, как и должно быть.) Ясно, что это вычисление зависит от хордальности.^[8]

Минимальные разделители

В любом графе разделитель вершин - множество вершин, удаление которых оставляет оставшийся граф несвязным; разделитель минимален, если он не имеет собственного подмножества, которое также является разделителем. Согласно теореме Дирак (1961), хордовые графы - это графы, в которых каждый минимальный разделитель является кликой; Дирак использовал эту характеристику, чтобы доказать, что хордовые графы идеально.

Семейство хордовых графов индуктивно можно определить как графы, вершины которых можно разделить на три непустых подмножества А, S, и B, так что А ∪ S и S ∪ B оба образуют хордовые индуцированные подграфы, S является кликой, и нет ребер из А к B. То есть это графы, которые имеют рекурсивное разложение с помощью кликовых разделителей на более мелкие подграфы. По этой причине хордовые графы также иногда называют разложимые графы.^[9]

Графы пересечений поддеревьев

Хордовый граф с восемью вершинами, представленный как граф пересечений восьми поддеревьев дерева с шестью узлами.

Альтернативная характеристика хордовых графов, благодаря Гаврил (1974), включает деревья и их поддеревья.

Из набора поддеревьев дерева можно определить граф поддерева, что является граф пересечений который имеет одну вершину на поддерево и ребро, соединяющее любые два поддерева, которые перекрываются в одном или нескольких узлах дерева. Гаврил показал, что графы поддерева - это в точности хордовые графы.

Представление хордового графа в виде пересечения поддеревьев образует разложение дерева графика, с ширина дерева на единицу меньше размера самой большой клики в графе; древовидное разложение любого графа грамм можно рассматривать таким образом как представление грамм как подграф хордового графа. Древовидная декомпозиция графа также является деревом соединений алгоритм дерева соединений.

Отношение к другим классам графов

Подклассы

Графики интервалов являются графами пересечений поддеревьев графы путей, частный случай деревьев. Следовательно, они являются подсемейством хордовых графов.

Разделить графики являются графами, которые одновременно являются хордовыми и дополняет хордовых графов. Бендер, Ричмонд и Вормальд (1985) показал, что в пределе, когда n стремится к бесконечности, доля расщепляемых хордальных графов с n вершинами приближается к единице.

Птолемеевы графы являются графами, которые одновременно являются хордовыми и дистанционно наследственный.Квазипороговые графики являются подклассом птолемеевых графов, одновременно хордовых и кографы. Блочные графики являются еще одним подклассом птолемеевых графов, в котором каждые две максимальные клики имеют не более одной общей вершины. Особый тип - графики ветряных мельниц, где общая вершина одинакова для каждой пары клик.

Сильно хордовые графы хордовые графы, не содержащие п-солнце (для п ≥ 3) как индуцированный подграф. Здесь п-солнце - это п-вершинный хордовый граф грамм вместе с коллекцией п вершины степени два, примыкающие к ребрам Гамильтонов цикл вграмм.

K-деревья - хордовые графы, в которых все максимальные клики и все максимальные разделители клик имеют одинаковый размер.^[10] Аполлонические сети хордовые максимальные планарные графы, или, что то же самое, плоские 3-деревья.^[10] Максимальный внешнепланарные графы являются подклассом 2-деревьев и, следовательно, также хордовые.

Суперклассы

Хордовые графы являются подклассом хорошо известных идеальные графики. Другие суперклассы хордовых графов включают слабо хордовые графы, графики выигрыша, графы без нечетных дырок, графы без четных дырок, и Графики Мейниеля. Хордовые графы - это в точности графы, не содержащие нечетных и четных отверстий (см. дыры в теории графов).

Каждый хордовый граф является задушенный граф, граф, в котором каждый периферический цикл является треугольником, поскольку периферийные циклы - это частный случай индуцированных циклов. Удушенные графы - это графы, которые могут быть образованы кликовые суммы хордовых графов и максимальных планарных графов. Следовательно, сжатые графы включают максимальные планарные графы.^[11]

Хордовые окончания и ширина дерева

Если грамм - произвольный граф, a хордовое завершение из грамм (или же минимальное заполнение) - хордовый граф, содержащий грамм как подграф. Параметризованная версия минимального заполнения: фиксированный параметр управляемый, и, более того, разрешима за параметризованное субэкспоненциальное время.^[12]^[13] В ширина дерева из грамм на единицу меньше количества вершин в максимальная клика хордового завершения, выбранного для минимизации размера этой клики. k-деревья - это графы, к которым нельзя добавить дополнительные ребра без увеличения их ширины дерева до числа, превышающегоk.Следовательно k-деревья являются собственными хордовыми пополнениями и образуют подкласс хордовых графов. Хордовые дополнения также можно использовать для характеристики нескольких других связанных классов графов.^[14]

Примечания

^ Дирак (1961).
^ Берже (1967).
^ Фулкерсон и Гросс (1965).
^ Бодлендер, Товарищи и Варнов (1992).
^ Берри, Голумбик и Липштейн (2007).
^ Шварцфитер и Борнштейн (1994).
^ Маффрей (2003).
^ Например, Агнарссон (2003) Замечание 2.5 называет этот метод хорошо известным.
^ Питер Бартлетт. «Ненаправленные графические модели: хордовые графы, разлагаемые графы, деревья соединений и факторизации» (PDF).
^ ^а ^б Патил (1986).
^ Сеймур и Уивер (1984).
^ Каплан, Шамир и Тарджан (1999).
^ Фомин и Вилланджер (2013).
^ Парра и Шеффлер (1997).

внешняя ссылка

[dirac-1] Дирак (1961).

[berge-2] Берже (1967).

[FOOTNOTEFulkersonGross1965-3] Фулкерсон и Гросс (1965).

[FOOTNOTEBodlaenderFellowsWarnow1992-4] Бодлендер, Товарищи и Варнов (1992).

[FOOTNOTEBerryGolumbicLipshteyn2007-5] Берри, Голумбик и Липштейн (2007).

[FOOTNOTESzwarcfiterBornstein1994-6] Шварцфитер и Борнштейн (1994).

[FOOTNOTEMaffray2003-7] Маффрей (2003).

[8] Например, Агнарссон (2003) Замечание 2.5 называет этот метод хорошо известным.

[9] Питер Бартлетт. «Ненаправленные графические модели: хордовые графы, разлагаемые графы, деревья соединений и факторизации» (PDF).

[patil86-10] а ^б Патил (1986).

[FOOTNOTESeymourWeaver1984-11] Сеймур и Уивер (1984).

[FOOTNOTEKaplanShamirTarjan1999-12] Каплан, Шамир и Тарджан (1999).

[FOOTNOTEFominVillanger2013-13] Фомин и Вилланджер (2013).

[FOOTNOTEParraScheffler1997-14] Парра и Шеффлер (1997).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]