Хордальный граф

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

Эквивалентное определение — если любой цикл без хорд имеет максимум три ребра. Другими словами, хордальный граф — это граф без порождённых циклов длины более чем три.

Хордальные графы являются подмножеством совершенных графов. Они также иногда называются циклически жёсткими графами или триангулированными графами. (Последний термин иногда ошибочно используют для планарной триангуляции. См. максимальные планарные графы.)

Совершенное исключение и эффективное распознавание хордальных графов

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

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

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

Множество всех совершенных порядков исключения хордального графа можно рассматривать как базовые слова антиматроида. Чандран и соавторы использовали эту связь с антиматроидами как часть алгоритма для эффективного перечисления всех совершенных порядков исключения для заданного хордального графа.

Наибольшие клики и раскраска графа

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

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

Минимальные сепараторы

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

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

Пересечение графов поддеревьев

Другая характеристика хордальных графов использует деревья и их поддеревья.

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

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

Связь с другими классами графов

Подклассы

Интервальные графы — это графы пересечений поддеревьев путей, специального случая деревьев. Таким образом, интервальные графы являются подсемейством хордальных графов.

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

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

Строго хордальные графы — это графы, являющиеся хордальными и не содержащие n-солнце (n≥3) в качестве порождённых подграфов.

K-деревья — это хордальные графы, у которых все наибольшие клики и максимальные сепараторы клик имеют один и тот же размер. Сети Аполлона — это хордальные максимальные планарные графы, или, что эквивалентно, планарные 3-деревья. Максимальные внешнепланарные графы — это подкласс 2-деревьев, а потому они тоже хордальны.

Суперклассы

Хордальные графы являются подклассом хорошо известных совершенных графов. Другие суперклассы хордальных графов включают слабые хордальные графы, графы без нечётных дыр, и графы без чётных дыр. Фактически хордальные графы — это в точности графы, одновременно без чётных дыр и без нечётных дыр (см. дыра в теории графов).

Любой хордальный граф является сжатым, то есть графом, у которого любой периферийный цикл является треугольником, поскольку периферийные циклы являются специальным случаем порождённого цикла. Сжатые графы могут быть образованы суммами по кликам хордальных графов и максимальных хордальных графов. Таким образом, сжатые графы включают максимальные планарные графы.

Литература

• Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980..

Ссылки

• [www.graphclasses.org/index.html Information System on Graph Class Inclusions]: [www.graphclasses.org/classes/gc_32.html chordal graph]
• Weisstein, Eric W. [mathworld.wolfram.com/ChordalGraph.html Chordal Graph] (англ.) на сайте Wolfram MathWorld.

Отрывок, характеризующий Хордальный граф

– Но вы un philoSophiee, [философ,] будьте же им вполне, посмотрите на вещи с другой стороны, и вы увидите, что ваш долг, напротив, беречь себя. Предоставьте это другим, которые ни на что более не годны… Вам не велено приезжать назад, и отсюда вас не отпустили; стало быть, вы можете остаться и ехать с нами, куда нас повлечет наша несчастная судьба. Говорят, едут в Ольмюц. А Ольмюц очень милый город. И мы с вами вместе спокойно поедем в моей коляске.
– Перестаньте шутить, Билибин, – сказал Болконский.
– Я говорю вам искренно и дружески. Рассудите. Куда и для чего вы поедете теперь, когда вы можете оставаться здесь? Вас ожидает одно из двух (он собрал кожу над левым виском): или не доедете до армии и мир будет заключен, или поражение и срам со всею кутузовскою армией.
И Билибин распустил кожу, чувствуя, что дилемма его неопровержима.
– Этого я не могу рассудить, – холодно сказал князь Андрей, а подумал: «еду для того, чтобы спасти армию».
– Mon cher, vous etes un heros, [Мой дорогой, вы – герой,] – сказал Билибин.


В ту же ночь, откланявшись военному министру, Болконский ехал в армию, сам не зная, где он найдет ее, и опасаясь по дороге к Кремсу быть перехваченным французами.
В Брюнне всё придворное население укладывалось, и уже отправлялись тяжести в Ольмюц. Около Эцельсдорфа князь Андрей выехал на дорогу, по которой с величайшею поспешностью и в величайшем беспорядке двигалась русская армия. Дорога была так запружена повозками, что невозможно было ехать в экипаже. Взяв у казачьего начальника лошадь и казака, князь Андрей, голодный и усталый, обгоняя обозы, ехал отыскивать главнокомандующего и свою повозку. Самые зловещие слухи о положении армии доходили до него дорогой, и вид беспорядочно бегущей армии подтверждал эти слухи.
«Cette armee russe que l'or de l'Angleterre a transportee, des extremites de l'univers, nous allons lui faire eprouver le meme sort (le sort de l'armee d'Ulm)», [«Эта русская армия, которую английское золото перенесло сюда с конца света, испытает ту же участь (участь ульмской армии)».] вспоминал он слова приказа Бонапарта своей армии перед началом кампании, и слова эти одинаково возбуждали в нем удивление к гениальному герою, чувство оскорбленной гордости и надежду славы. «А ежели ничего не остается, кроме как умереть? думал он. Что же, коли нужно! Я сделаю это не хуже других».
Князь Андрей с презрением смотрел на эти бесконечные, мешавшиеся команды, повозки, парки, артиллерию и опять повозки, повозки и повозки всех возможных видов, обгонявшие одна другую и в три, в четыре ряда запружавшие грязную дорогу. Со всех сторон, назади и впереди, покуда хватал слух, слышались звуки колес, громыхание кузовов, телег и лафетов, лошадиный топот, удары кнутом, крики понуканий, ругательства солдат, денщиков и офицеров. По краям дороги видны были беспрестанно то павшие ободранные и неободранные лошади, то сломанные повозки, у которых, дожидаясь чего то, сидели одинокие солдаты, то отделившиеся от команд солдаты, которые толпами направлялись в соседние деревни или тащили из деревень кур, баранов, сено или мешки, чем то наполненные.
На спусках и подъемах толпы делались гуще, и стоял непрерывный стон криков. Солдаты, утопая по колена в грязи, на руках подхватывали орудия и фуры; бились кнуты, скользили копыта, лопались постромки и надрывались криками груди. Офицеры, заведывавшие движением, то вперед, то назад проезжали между обозами. Голоса их были слабо слышны посреди общего гула, и по лицам их видно было, что они отчаивались в возможности остановить этот беспорядок. «Voila le cher [„Вот дорогое] православное воинство“, подумал Болконский, вспоминая слова Билибина.
Желая спросить у кого нибудь из этих людей, где главнокомандующий, он подъехал к обозу. Прямо против него ехал странный, в одну лошадь, экипаж, видимо, устроенный домашними солдатскими средствами, представлявший середину между телегой, кабриолетом и коляской. В экипаже правил солдат и сидела под кожаным верхом за фартуком женщина, вся обвязанная платками. Князь Андрей подъехал и уже обратился с вопросом к солдату, когда его внимание обратили отчаянные крики женщины, сидевшей в кибиточке. Офицер, заведывавший обозом, бил солдата, сидевшего кучером в этой колясочке, за то, что он хотел объехать других, и плеть попадала по фартуку экипажа. Женщина пронзительно кричала. Увидав князя Андрея, она высунулась из под фартука и, махая худыми руками, выскочившими из под коврового платка, кричала:
– Адъютант! Господин адъютант!… Ради Бога… защитите… Что ж это будет?… Я лекарская жена 7 го егерского… не пускают; мы отстали, своих потеряли…
– В лепешку расшибу, заворачивай! – кричал озлобленный офицер на солдата, – заворачивай назад со шлюхой своею.
– Господин адъютант, защитите. Что ж это? – кричала лекарша.
– Извольте пропустить эту повозку. Разве вы не видите, что это женщина? – сказал князь Андрей, подъезжая к офицеру.
Офицер взглянул на него и, не отвечая, поворотился опять к солдату: – Я те объеду… Назад!…
– Пропустите, я вам говорю, – опять повторил, поджимая губы, князь Андрей.
– А ты кто такой? – вдруг с пьяным бешенством обратился к нему офицер. – Ты кто такой? Ты (он особенно упирал на ты ) начальник, что ль? Здесь я начальник, а не ты. Ты, назад, – повторил он, – в лепешку расшибу.
Это выражение, видимо, понравилось офицеру.
– Важно отбрил адъютантика, – послышался голос сзади.
Князь Андрей видел, что офицер находился в том пьяном припадке беспричинного бешенства, в котором люди не помнят, что говорят. Он видел, что его заступничество за лекарскую жену в кибиточке исполнено того, чего он боялся больше всего в мире, того, что называется ridicule [смешное], но инстинкт его говорил другое. Не успел офицер договорить последних слов, как князь Андрей с изуродованным от бешенства лицом подъехал к нему и поднял нагайку:
– Из воль те про пус тить!
Офицер махнул рукой и торопливо отъехал прочь.
– Всё от этих, от штабных, беспорядок весь, – проворчал он. – Делайте ж, как знаете.
Князь Андрей торопливо, не поднимая глаз, отъехал от лекарской жены, называвшей его спасителем, и, с отвращением вспоминая мельчайшие подробности этой унизи тельной сцены, поскакал дальше к той деревне, где, как ему сказали, находился главнокомандующий.
Въехав в деревню, он слез с лошади и пошел к первому дому с намерением отдохнуть хоть на минуту, съесть что нибудь и привесть в ясность все эти оскорбительные, мучившие его мысли. «Это толпа мерзавцев, а не войско», думал он, подходя к окну первого дома, когда знакомый ему голос назвал его по имени.
Он оглянулся. Из маленького окна высовывалось красивое лицо Несвицкого. Несвицкий, пережевывая что то сочным ртом и махая руками, звал его к себе.
– Болконский, Болконский! Не слышишь, что ли? Иди скорее, – кричал он.
Войдя в дом, князь Андрей увидал Несвицкого и еще другого адъютанта, закусывавших что то. Они поспешно обратились к Болконскому с вопросом, не знает ли он чего нового. На их столь знакомых ему лицах князь Андрей прочел выражение тревоги и беспокойства. Выражение это особенно заметно было на всегда смеющемся лице Несвицкого.
– Где главнокомандующий? – спросил Болконский.
– Здесь, в том доме, – отвечал адъютант.
– Ну, что ж, правда, что мир и капитуляция? – спрашивал Несвицкий.
– Я у вас спрашиваю. Я ничего не знаю, кроме того, что я насилу добрался до вас.
– А у нас, брат, что! Ужас! Винюсь, брат, над Маком смеялись, а самим еще хуже приходится, – сказал Несвицкий. – Да садись же, поешь чего нибудь.
– Теперь, князь, ни повозок, ничего не найдете, и ваш Петр Бог его знает где, – сказал другой адъютант.
– Где ж главная квартира?
– В Цнайме ночуем.
– А я так перевьючил себе всё, что мне нужно, на двух лошадей, – сказал Несвицкий, – и вьюки отличные мне сделали. Хоть через Богемские горы удирать. Плохо, брат. Да что ты, верно нездоров, что так вздрагиваешь? – спросил Несвицкий, заметив, как князя Андрея дернуло, будто от прикосновения к лейденской банке.
– Ничего, – отвечал князь Андрей.
Он вспомнил в эту минуту о недавнем столкновении с лекарскою женой и фурштатским офицером.
– Что главнокомандующий здесь делает? – спросил он.
– Ничего не понимаю, – сказал Несвицкий.
– Я одно понимаю, что всё мерзко, мерзко и мерзко, – сказал князь Андрей и пошел в дом, где стоял главнокомандующий.
Пройдя мимо экипажа Кутузова, верховых замученных лошадей свиты и казаков, громко говоривших между собою, князь Андрей вошел в сени. Сам Кутузов, как сказали князю Андрею, находился в избе с князем Багратионом и Вейротером. Вейротер был австрийский генерал, заменивший убитого Шмита. В сенях маленький Козловский сидел на корточках перед писарем. Писарь на перевернутой кадушке, заворотив обшлага мундира, поспешно писал. Лицо Козловского было измученное – он, видно, тоже не спал ночь. Он взглянул на князя Андрея и даже не кивнул ему головой.
– Вторая линия… Написал? – продолжал он, диктуя писарю, – Киевский гренадерский, Подольский…
– Не поспеешь, ваше высокоблагородие, – отвечал писарь непочтительно и сердито, оглядываясь на Козловского.
Из за двери слышен был в это время оживленно недовольный голос Кутузова, перебиваемый другим, незнакомым голосом. По звуку этих голосов, по невниманию, с которым взглянул на него Козловский, по непочтительности измученного писаря, по тому, что писарь и Козловский сидели так близко от главнокомандующего на полу около кадушки,и по тому, что казаки, державшие лошадей, смеялись громко под окном дома, – по всему этому князь Андрей чувствовал, что должно было случиться что нибудь важное и несчастливое.
Князь Андрей настоятельно обратился к Козловскому с вопросами.
– Сейчас, князь, – сказал Козловский. – Диспозиция Багратиону.
– А капитуляция?
– Никакой нет; сделаны распоряжения к сражению.
Князь Андрей направился к двери, из за которой слышны были голоса. Но в то время, как он хотел отворить дверь, голоса в комнате замолкли, дверь сама отворилась, и Кутузов, с своим орлиным носом на пухлом лице, показался на пороге.
Князь Андрей стоял прямо против Кутузова; но по выражению единственного зрячего глаза главнокомандующего видно было, что мысль и забота так сильно занимали его, что как будто застилали ему зрение. Он прямо смотрел на лицо своего адъютанта и не узнавал его.
– Ну, что, кончил? – обратился он к Козловскому.
– Сию секунду, ваше высокопревосходительство.
Багратион, невысокий, с восточным типом твердого и неподвижного лица, сухой, еще не старый человек, вышел за главнокомандующим.
– Честь имею явиться, – повторил довольно громко князь Андрей, подавая конверт.
– А, из Вены? Хорошо. После, после!
Кутузов вышел с Багратионом на крыльцо.
– Ну, князь, прощай, – сказал он Багратиону. – Христос с тобой. Благословляю тебя на великий подвиг.
Лицо Кутузова неожиданно смягчилось, и слезы показались в его глазах. Он притянул к себе левою рукой Багратиона, а правой, на которой было кольцо, видимо привычным жестом перекрестил его и подставил ему пухлую щеку, вместо которой Багратион поцеловал его в шею.