Jump to content

Удушенный граф

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

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

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

Характеристика

[ редактировать ]

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

Как показывают Сеймур и Уивер (1984) , это единственные возможные строительные блоки ущемленных графов: ущемленные графы — это именно те графы, которые могут быть сформированы как кликовые суммы полных графов и максимальных планарных графов.

См. также

[ редактировать ]
  • Сеймур, Полиция ; Уивер, Р.В. (1984), «Обобщение хордальных графов», Журнал теории графов , 8 (2): 241–251, doi : 10.1002/jgt.3190080206 , MR   0742878 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a407e0a6127449d52d96832bb5fdf016__1657133280
URL1:https://arc.ask3.ru/arc/aa/a4/16/a407e0a6127449d52d96832bb5fdf016.html
Заголовок, (Title) документа по адресу, URL1:
Strangulated graph - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)