这是图论中的已知问题吗？

Question

我的基本问题包括一个图形，其中每个节点 $ i $ 与权重 $ c_i $ 问题是找到具有固定基数 $ p $ 的最小（或最大）加权独立集。这是我相信图形理论中的一个众所周知的问题，这对于不同类型的图表进行了很好的研究。

现在，假设我正在处理如下问题的普遍形式。每个节点的权重可以占用 $ p $ 不同的值，即每个节点与 $ p $ 不同的权重。目的再次找到最小（或最大）加权独立集，固定基数 $ P $ ，但是，只能选择每种类型的重量。精确地，如果为节点 $ i $ ，则选择权重类型 $ j $ ，即，我们选择权重 $ c_ {ij} $ ，那么另一个选定的节点不能占用 $ j $ 。

我的问题是，这仍然是一个图论问题吗？是图形理论问题的已知概括吗？

任何帮助和/或参考值得赞赏。

Answer 1

如果 $ g=（v，e）$ ，with $ v= {v_1，v_2，.. 。，v_n \} $ 和权重 $ \ {c_ {i，j}，i= 1,2，...，n，j= 1,2， ...，p \} $ 是给定图形，然后我们可以构建 <强>强大的产品 （我终于找到了操作的名称） $ g \ boxtimes 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 \} \在e $ 中。 （强产品的实际条件为此缩短为此，因为在 $ K_P $ 所有顶点都是相邻的）。

我们给顶点 $ v_ {i，j} $ 权重 $ c_ {i，j} $ < / span>，for $ i= 1,2，...，n $ 和 $ j= 1,2， ...，p $ 。

在 $ g $ 上的问题相当于加权最小（最大）加权独立集数学集装箱“> $ g \ boxtimes 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 \ boxtimesk_2 $ 将是图< / p>



用这个工具。