그래프 이론에서 알려진 문제가 있습니까?

Question

내 기본 문제는 각 노드 $ i $ 이 무게 $ C_I $ 그리고 문제는 고정 된 카디널리티 $ P $ 과 함께 최소 (또는 최대) 가중치 집합을 찾는 것입니다. 이것은 다른 유형의 그래프에 대해 잘 연구 된 그래프 이론에서 잘 알려진 문제를 믿습니다.

이제는 다음과 같은 문제의 일반화 된 형태를 다루고 있다고 가정합니다. 각 노드의 무게는 $ p $ 다른 값을 가져갈 수 있습니다. 즉, 각 노드는 $ P $ 무게. 목표는 고정 카디널리티 $ P $ 과 함께 최소 (또는 최대) 가중치 독립적 인 세트를 다시 찾을 수 있지만, 각 유형의 체중은 한 번만 선택할 수 있습니다. 정확하게, $ i $ , 즉 우리는 선택하는 노드 $ j $ 이 선택되면, $ C_ {ij} $ 다른 선택된 노드는 $ 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 $ 정점을 가진 그래프 완전한 . 이것은 $ \ {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 \} \ \ . (강력한 제품의 실제 상태는 $ K_P $ 이후로 이래로이므로 모든 정점이 인접합니다.

우리는 vertex $ 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} $ 은 정점 $ V_i $ < / span> 원본 그래프의 / $ j $ -th 무게 $ c_ {i, j} $ 해당.

$ g \ boxtimes k_p $ 의 세트는 $ g $의 선택 사항을 방지하는 것입니다. 인접한 꼭지점을 사용하거나 동일한 색인으로 가중치를 재사용하려면

• 조건 $ 1 $ 은 동일한 원래의 정점에서 2 개의 무게를 사용하는 것과 동일한 것을 방지하는 강력한 제품의 가장자리를 정의합니다.
• 조건 $ 2 $ 은 원본 그래프의 다른 정점에서 동일한 인덱스로 무게를 사용하는 것을 방지합니다.
• 조건 $ 3 $ 원래 그래프의 이웃이있는 두 개의 정점이 선택됩니다.

예 :

$ g $ 은 그래프

입니다

>>

및 $ p= 2 $ , $ g \ boxtimes k_2 $ 은 그래프가 될 것입니다 / P>

>>

이 도구 .