これはグラフ理論で既知の問題ですか？

Question

マイ基本的な問題は、各ノード $ i $ が重み $ c_i $ 、そして問題は、固定されたCardinality $ P $ を使用して最小（または最大）加重独立したセットを見つけることです。これは、さまざまな種類のグラフについてよく研究されているグラフ理論では、よく知られている問題を信じる。

今、私が以下のように問題の一般化された形に対処しているとします。各ノードの重みは $ p $ さまざまな値を取ります。各ノードは $ p $ 異なる重み。この目的は、固定されたCardinality="Math-Container"> $ P $ を使用して最小（または最大の）加重独立セットを見つけるために再び、各タイプの重みを1回だけ選択できます。正確には、ノード $ i $ に対して重みタイプ $ j $ が選択されている場合、つまり選択します。重み $ c_ {ij} $ 、その他の選択されたノードはtype $ 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 \ boxtimes k_p $ の $ G $ と $ k_p $ 。 $ k_p $ は $ p $ verticesの完全グラフ。これは頂点 $ \ {v_ {i、j}、i= 1,2、...、n、j= 1,2、...、p \を持つグラフです。 $ とedges $ \ {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 \ boxtimes k_p $ 。新しいグラフの頂点 $ v_ {i、j} $ v_ {i、j} $ が選択されている場合は、vertex $ v_i $ <元のグラフの/スパンと $ j $ $ j $ ~msp class="math-contains"> $ c_ {i、j} $ それに対応します。

$ g \ boxtimes k_p $ のエッジのセットは、 $ g $の対応する選択を防ぐためのものです。 隣接する頂点を使用するか、同じインデックスで重みを再利用するには：

• condition $ 1 $ は、同じ元の頂点から2つの重みを使用するのを防ぐ強力な製品のエッジを定義します。
• condition $ 2 $ オリジナルのグラフのさまざまな頂点から同じインデックスを持つ重みを使用しないようにします。
• condition $ 3 $ 元のグラフ内のネイバーの2つの頂点が選択されていることを防ぎます。

例：

$ g $ の場合は、グラフ

です。



と $ p= 2 $ 、 $ g \ boxtimes k_2 $ はグラフです。 / P>



このツール