Jump to content

Монохроматический треугольник

Разбиение ребер полного графа K 5 на два подмножества без треугольников

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

Постановка задачи

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

Задача монохроматического треугольника принимает на вход n-узловой неориентированный граф G(V,E) с множеством узлов V и множеством ребер E.Выходные данные представляют собой логическое значение, истинное, если множество ребер E группы G можно разделить на два непересекающихся множества E1 и E2, так что оба подграфа G1(V,E1) и G2(V,E2) не содержат треугольников. графики и false в противном случае. Эта задача решения является NP-полной . [1]

Обобщение нескольких цветов

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

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

Связь с теоремой Рамсея

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

По теореме Рэмси для любого конечного числа k цветов существует число n такое, что полные графы из n или более вершин не имеют раскрасок ребер без треугольников в k цветов. Для k = 2 соответствующее значение n равно 6. То есть ответ на задачу об одноцветном треугольнике на полном графе K 6 — нет.

Параметризованная сложность

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

) несложно выразить второго порядка Проблему монохроматического треугольника в монадической логике графов (MSO 2 с помощью логической формулы, которая утверждает существование разделения ребер на два подмножества, такого, что не существует трех взаимно смежных вершин. все ребра которого принадлежат одной и той же стороне разбиения. следует Из теоремы Курселя , что задача монохроматического треугольника разрешима с фиксированным параметром на графах ограниченной ширины дерева . Точнее, существует алгоритм решения задачи, время работы которого равно числу вершин входного графа, умноженному на быстрорастущую, но вычислимую функцию ширины дерева. [2]

  1. ^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN  978-0-7167-1045-5 . A1.1: GT6, стр. 191.
  2. ^ Арнборг, Стефан; Лагергрен, Йенс; Сиз, Детлеф (1988), «Проблемы, простые для древовидных графов (расширенное резюме)», Автоматы, языки и программирование (Тампере, 1988) , Конспекты лекций по информатике, том. 317, Берлин: Springer, стр. 38–51, номер документа : 10.1007/3-540-19488-6_105 , ISBN.  978-3-540-19488-0 , МР   1023625 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 78033c0da75d139e779394cf93a5f66a__1714983780
URL1:https://arc.ask3.ru/arc/aa/78/6a/78033c0da75d139e779394cf93a5f66a.html
Заголовок, (Title) документа по адресу, URL1:
Monochromatic triangle - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)