Монохромный треугольник - Monochromatic triangle

Перегородка краев полный график K₅ на два подмножества без треугольников

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

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

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

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

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

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

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

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

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

Рекомендации