Ist das ein bekanntes Problem in der Graph-Theorie?

Question

Mein Basis-Problem enthält ein Diagramm, in dem jeder Knoten $ i $ mit einem Gewicht $ C_I $ und das Problem besteht darin, ein minimales (oder maximales) gewichtetes unabhängiges Set mit fester Kardinalität $ P $ zu finden. Dies ist, dass ich ein bekanntes Problem in der Graph-Theorie glaube, das für verschiedene Graphenarten gut untersucht wird.

Jetzt nehme ich an, ich gehe mit einer generalisierten Form des Problems wie folgt um. Das Gewicht jedes Knotens kann $ P $ verschiedene Werte annehmen, dh jeder Knoten ist mit $ P $ Unterschiedliche Gewichte. Ziel ist es erneut, ein minimales (oder maximales) gewichtetes unabhängiges Set mit einem festen Kardinalität $ P $ zu finden, jedoch kann jeder Gewichtstyp nur einmal ausgewählt werden. Wenn der Gewichtstyp $ J $ für den Knoten $ I $ ausgewählt ist, werden wir auswählen Das Gewicht $ c_ {ij} $ , dann können die anderen ausgewählten Knoten nicht ein Gewicht des Typs $ J $ .

Meine Frage ist, dass dies noch ein Graph-Theory-Problem ist? Ist es eine bekannte Verallgemeinerung in den Graph-Theory-Problemen?

jede Hilfe und / oder Referenz wird geschätzt.

Answer 1

wenn $ g= (v, e) $ , mit $ v={v_1, v_2, .. ., v_n \} $ und gewichte $ \ {c_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \} $ ist die angegebene Grafik, dann können wir den Starkes Produkt (ich habe endlich den Namen der Operation gefunden) $ g \ boxtimes K_P $ von $ G $ und $ k_p $ , wobei $ k_p $ das komplette graphine mit $ p $ Scheitelpunkte. Dies ist das Graph mit Scheitelpunkten $ \ {v_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \ } $ und kanten $ \ {v_ {a, b}, v_ {c, d} \} $ wo entweder:

.
1. $ A= C $ ,
2. $ B= D $ oder
3. $ \ {v_a, v_c \} \ in E $ . (Der tatsächliche Zustand des starken Produkts reduziert sich darauf, da in $ k_p $ alle Scheitelpunkte benachbart sind).

wir geben den vertex $ v_ {i, j} $ das Gewicht $ c_ {i, j} $ < / span>, für $ i= 1,2, ..., n $ und $ j= 1,2, ..., p $ .

Das Problem auf $ g $ ist dem Problem minimales (maximal) gewichtetes unabhängiges Set in der gewichteten $ g \ boxtimes k_p $ . Wenn ein Scheitelpunkt $ v_ {i, j} $ des neuen Diagramms gewählt wird, entspricht dies den Optionen von Scheitelpunkten $ v_i $ < / span> des Originalgraphen und mithilfe der $ J $ -tes Gewicht $ c_ {i, j} $ entsprechend.

Der Satz von Kanten von $ g \ boxtimes k_p $ sind genau diejenigen, die die entsprechenden Optionen in $ g $ verhindern Um benachbarte Scheitelpunkte zu verwenden oder Gewichte mit demselben Index wiederzuwickeln:

.
• Bedingung $ 1 $ Definiert die Kanten im starken Produkt, die das Äquivalent der Verwendung von zwei Gewichten von demselben Originalvertex verhindern.
• Bedingung $ 2 $ Verhindert die Verwendung der Gewichte mit demselben Index aus verschiedenen Scheitelpunkten des Originalgraphen.
• Zustand $ 3 $ Verhindert, dass zwei Scheitelpunkte, die Nachbarn in der ursprünglichen Grafik waren, ausgewählt sind.

Beispiel:

wenn $ g $ ist die Grafik



und $ p= 2 $ , dann $ g \ boxtimes k_2 $ wäre die Grafik < / p>



Bilder erstellt mit dieses Werkzeug .