Est-ce un problème connu dans la théorie des graphes?

Question

Mon problème de base comprend un graphique où chaque nœud $ i $ est associé à un poids $ c_i $ , et le problème est de trouver un ensemble minimum (ou maximum) indépendant pondéré avec une cardinalité fixe $ p $ . C'est ce que je crois un problème bien connu dans la théorie des graphes qui est bien étudiée pour différents types de graphiques.

Maintenant, supposons que je traite de la forme généralisée du problème comme suit. Le poids de chaque nœud peut prendre $ p $ différentes valeurs, c'est-à-dire que chaque nœud est associé à $ p $ poids différents. L'objectif est à nouveau de trouver un ensemble minimum (ou maximum) indépendant pondéré avec une cardinalité fixe $ p $ , cependant, chaque type de poids peut être sélectionné une seule fois. Précisément, si le type de poids $ j $ est sélectionné pour le nœud $ i $ , c'est-à-dire que nous sélectionnons Le poids $ c_ {ij} $ , alors les autres nœuds sélectionnés ne peuvent pas prendre de poids de type $ j $ .

Ma question est que cela, est-ce que cela reste un problème de théorie des graphes? Est-ce une généralisation connue dans les problèmes de théorie des graphes?

Toute aide et / ou référence est appréciée.

Answer 1

si $ g= (v, e) $ , avec $ v={v_1, v_2, .. ., v_n \} $ et poids $ \ {c_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \} $ est le graphique donné, alors nous pouvons construire le produit fort (j'ai enfin trouvé le nom de l'opération) $ g \ bextimes k_p $ de $ G $ et $ k_p $ , où $ k_p $ est le Graphique complet avec $ P $ sommets. Ceci est le graphique avec des sommets $ \ {v_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \ } $ et bords $ \ {v_ {a, b}, v_ {c, d} \} $ où:

1. $ A= C $ ,
2. $ b= d $ ou
3. $ \ {v_a, v_c \} \ in e $ . (La condition réelle du produit solide réduit à cela depuis dans $ k_p $ tous les sommets sont adjacents).

Nous donnons le sommet $ v_ {i, j} $ le poids $ c_ {i, j} $ < / span>, pour $ i= 1,2, ..., n $ et $ j= 1,2, ..., p $ .

Le problème sur $ g $ est équivalent au problème Set indépendant pondéré minimum (maximum) dans la catégorie $ g \ bextimes k_p $ . Si un sommet $ v_ {i, j} $ du nouveau graphique est choisi, ceci correspond à choisir Vertex $ v_i $ < / Span> du graphique d'origine et à l'aide de $ J $ -TH Poids $ C_ {I, J} $ correspondant à celui-ci.

L'ensemble des bords de $ g \ bextimes k_p $ sont exactement ceux qui empêchent les choix correspondants dans $ g $ Pour utiliser des sommets adjacents ou réutiliser des poids avec le même index:

• condition $ 1 $ définit les bords dans le produit solide qui empêche l'équivalent d'utiliser deux poids du même sommet original.
• condition $ 2 $ empêche d'utiliser les poids avec le même index de différents sommets du graphique d'origine.
• condition $ 3 $ empêche que deux sommets qui étaient des voisins dans le graphique d'origine sont sélectionnés.

exemple:

si $ g $ est le graphique



et $ p= 2 $ , puis $ g \ bextimes k_2 $ serait le graphique / p>



images créées avec Cet outil .