Монохроматический треугольник
В теории графов и теоретической информатике — проблема монохроматического треугольника это алгоритмическая задача на графах.цель которого состоит в том, чтобы разбить ребра данного графа на два подграфа без треугольников . Он 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]
Ссылки
[ редактировать ]- ^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5 . A1.1: GT6, стр. 191.
- ^ Арнборг, Стефан; Лагергрен, Йенс; Сиз, Детлеф (1988), «Проблемы, простые для древовидных графов (расширенное резюме)», Автоматы, языки и программирование (Тампере, 1988) , Конспекты лекций по информатике, том. 317, Берлин: Springer, стр. 38–51, номер документа : 10.1007/3-540-19488-6_105 , ISBN. 978-3-540-19488-0 , МР 1023625 .