1
정확히 노드 - 분리 된 경로에 대한 설명이 필요합니까? 그리고 두 노드 간의 노드 - 분리 경로의 최대 수를 정하는 방법 유향 그래프의 소스와 싱크 (t). 누구든지 그래픽으로 설명 할 수 있습니까?노드 분리 경로 란 무엇입니까?
A
답변
3
경로는 정점 순서 : s, v_1, .., v_m, t입니다. 유효한 i 및 j에 대해 인 경우 s, v_1, .., v_m, t 및 s, u_1, ..., u_k, t의 두 경로를 노드 분리 (node-disjoint)라고합니다.
이 문제는 소스와 대상을 제외한 각 정점을 두 개로 분할하고 첫 번째 복사본에서 두 번째 복사본으로 가장자리를 추가하고 모든 에지를 리디렉션하여 최대 엣지 - 분리 경로 수를 찾는 것으로 줄일 수 있습니다 이 정점에서 첫 번째 복사본으로 끝나고 두 번째 복사본에서 모든 나가는 모서리로 끝납니다. 그 후,이 그래프의 최대 흐름이 답입니다 (모든 에지는 단위 용량을 가져야합니다).
+0
난 두 정확히 각 꼭지점을 분할의 의미를 이해하지 못했?. –
+0
@praveenkumarbeedanal 그것은 각 정점 대신에 정점의 쌍 (근원과 표적을 제외하고)이있는 곳에 새로운 그래프를 작성하는 것을 의미하며 가장자리는 내 대답에 설명 된대로 추가됩니다. – kraskevich
+0
괜찮습니다. –
도움이 될 수 있습니다. https://www.quora.com/How-can-I-approach-the-problem-Intergalactic-Map-IM-on-SPOJ-using-Max-Flow/answer/Raziman-TV 여기에 –