특정 간선을 제거하는 최소 카디널리티 그래프 파티션
Aug 21 2020
해결하고 싶은 계산 문제가 있습니다. 나는 그것이 이미 문학에서 연구되었는지, 아니면 어떤 이름으로 연구되었는지 확실하지 않습니다. 알고리즘에 대한 문헌이나 제안에 대한 조언을 주시면 감사하겠습니다.
입력 : 연결되고 방향이 지정되지 않은 그래프 G = (V, E) 특정 모서리가 "불량"으로 표시됩니다.
출력 : V의 최소 카디널리티 파티션은 1) 파티션의 모든 유도 된 부분 그래프가 연결되고 2) 유도 된 부분 그래프 중 어느 것도 잘못된 모서리를 포함하지 않습니다.
감사!
답변
1 PålGD Aug 21 2020 at 03:46
모든 가장자리가 잘못된 가장자리 일 때 어떤 일이 발생하는지 살펴보십시오 .
내가 묻는다면 질문은 무엇입니까?
그래프를 빨간색, 녹색, 파란색 등 3 개의 파티션 으로 분할하여 모든 가장자리에 대해 각 가장자리 끝점의 "색상"이 "색채"가되도록 할 수 있습니다.
(인접하지 않은 모든 정점 사이에 "좋은"가장자리를 추가하여 그래프를 완전한 그래프로 만들어 보겠습니다.)