Это известная проблема в теории графа?

Question

Моя основная проблема включает в себя график, в котором каждый узел $ i $ связан с весом $ c_i $ , И проблема состоит в том, чтобы найти минимальный (или максимальный) взвешенный независимый набор с фиксированной кардинальностью $ p $ . Это я считаю, что известная проблема в теории графика, которая хорошо изучена для разных типов графиков.

Теперь, предположим, что я имею дело с обобщенной формой проблемы, как и следующие. Вес каждого узла может принимать $ p $ Разные значения, то есть каждый узел связан с $ P $ Разные веса. Целью снова находит минимальный (или максимальный) взвешенный независимый набор с фиксированной кардинальностью $ P $ , однако, каждый тип веса может быть выбран только один раз. Именно, если тип веса $ j $ выбран для узла $ i $ , то есть выбираем Вес $ c_ {ij} $ , то другие выбранные узлы не могут занимать вес типа $ j $ .

Мой вопрос в том, это все еще проблема теории графика? Это известное обобщение в проблемах теории графика?

Любая помощь и / или ссылка ценится.

Answer 1

Если $ g= (v, e) $ , с $ v={v_1, v_2, .. , v_n \} $ и веса $ \ {c_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \} $ - это заданный график, то мы можем построить Сильный продукт (я наконец нашел имя операции) $ g \ bigimes k_p $ $ k_p $ , где $ k_p $ - это полный график с $ p $ вершины. Это график с вершинами $ \ {v_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \ } $ и ребра $ \ {v_ {a, b}, v_ {c, d} \} $ где либо:

1. $ a= c $ ,
2. $ b= d $ или
3. $ \ {v_a, v_c \} \ in $ . (Фактическое состояние сильного продукта уменьшается к этому, поскольку в $ K_P $ Все вершины соседствуют).

Мы даем вершину $ v_ {i, j} $ Вес $ C_ {i, j} $ < / span>, для $ i= 1,2, ..., n $ и $ j= 1,2, ..., p $ .

Проблема на $ G $ эквивалентна проблеме Минимальный (максимальный) взвешенный независимый набор в взвешенном $ g \ bigies k_p $ . Если выбран вершина $ v_ {i, j} $ нового графа, соответствует выбору вершины $ v_i $ < / span> оригинального графа и с использованием $ j $ -th вес $ C_ {i, j} $ Соответствует этому.

Набор краев $ g \ boxtimes k_p $ именно те, которые предотвращают соответствующий вариант в $ G $ Использовать соседние вершины или повторное использование весов с тем же индексом:

.
• Условие $ 1 $ Определяет края в сильном продукте, который предотвращает эквивалент с использованием двух весов из того же оригинальной вершины.
• Условие $ 2 $ предотвращает использование весов с тем же индексом из разных вершин исходного графика.
• Условие 3 $ $ Предотвращает, чтобы два вершина, которые были соседками в исходном графике, выбраны.

<Сильный> Пример:

Если $ g $ - график



и $ p= 2 $ , то $ g \ byctimes k_2 $ будет графиком / P >.



Изображения, созданные с Этот инструмент .