È un problema conosciuto nella teoria del grafico?

Question

Il mio problema di base include un grafico in cui ogni nodo $ i $ è associato a un peso $ c_i $ , e il problema è trovare un set indipendente minimo (o massimo) ponderato con una cardinalità fissa $ P $ . Questo è credo che un problema ben noto nella teoria del grafico che è ben studiato per diversi tipi di grafici.

Ora, supponiamo che abbia a che fare con una forma generalizzata del problema come segue. Il peso di ciascun nodo può prendere $ p $ valori diversi, che ciascun nodo è associato a $ P $ pesi diversi. L'obiettivo è di nuovo per trovare un set indipendente minimo (o massimo) con una cardinalità fissa $ P $ , tuttavia, ogni tipo di peso può essere selezionato solo una volta. Precisamente, se il tipo di peso $ j $ è selezionato per il nodo $ I $ , cioè, selezioniamo il peso $ c_ {ij} $ , quindi gli altri nodi selezionati non possono prendere un peso di tipo $ J $ .

La mia domanda è che, è ancora un problema di teoria del grafico? È una generalizzazione nota nei problemi della teoria del grafico?

Qualsiasi aiuto e / o riferimento è apprezzato.

Answer 1

Se $ G= (v, e) $ , con $ v={v_1, v_2, .. ., v_n \} $ e pesi $ \ {c_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \} $ è il grafico dato, quindi possiamo costruire il Prodotto forte (ho finalmente trovato il nome dell'operazione) $ G \ boxtimes k_p $ di $ G $ e $ k_p $ , dove $ k_p $ è il Completa grafico con $ p $ vertici. Questo è il grafico con i vertici $ \ {v_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \ } $ e bordi $ \ {v_ {a, b}, v_ {c, d}} $ dove:

.
1. $ a= c $ ,
2. $ B= D $ o
3. $ \ {v_a, v_c \} \ in e $ . (La condizione effettiva del prodotto forte riduce a questo da poiché in $ K_P $ Tutti i vertici sono adiacenti).

Diamo il vertice $ v_ {i, j} $ il peso $ c_ {i, j} $ < / span>, per $ i= 1,2, ..., n $ e $ j= 1,2, ..., P $ .

Il problema su $ G $ equivale al problema minimo (massimo) Set indipendente minimo (massimo) nella Ponderata $ G \ Boxtimes k_p $ . Se un vertice $ v_ {i, j} $ del nuovo grafico è scelto corrisponde a scegliere vertice $ v_i $ < / span> del grafico originale e utilizzando la $ j $ -hise peso $ c_ {i, j} $ corrispondente ad esso.

Il set di bordi di $ g \ boxtimes k_p $ sono esattamente quelli che impediscono le scelte corrispondenti in $ G $ per utilizzare i vertici adiacenti o riutilizzare i pesi con lo stesso indice:

.
• Condizione $ 1 $ Definisce i bordi nel prodotto forte che impedisce l'equivalente dell'utilizzo di due pesi dallo stesso vertice originale.
• Condizione $ 2 $ impedisce di utilizzare i pesi con lo stesso indice da diversi vertici del grafico originale.
• condizione $ 3 $ impedisce che sono selezionati due vertici che i vicini nel grafico originale sono selezionati.

Esempio:

Se $ G $ è il grafico



e $ p= 2 $ , quindi $ g \ boxtimes k_2 $ sarebbe il grafico < / P >.



Immagini create con Questo strumento .