전역 최소 절단(스토어–바그너) 계산기

그래프의 점들을 비어 있지 않은 두 무리로 가를 때, 두 무리 사이를 지나는 간선 무게의 합이 가장 작아지는 분할입니다. 네트워크가 몇 개의 회선만 끊기면 두 동강 나는지, 그 회선이 어디인지를 보는 문제와 같습니다.

거기서는 s와 t 두 점을 미리 정해 놓고 그 둘을 갈라야 합니다. 여기서는 어디서 갈라도 좋습니다. 모든 (s, t) 짝에 대해 최대 유량을 구해 가장 작은 것을 골라도 되지만 그러면 계산이 많아지고, 스토어–바그너는 그럴 필요가 없습니다.

흐름을 한 번도 계산하지 않습니다. 아무 점에서 시작해 「지금까지 고른 무리와 가장 굵게 이어진 점」을 차례로 고르고(최대 인접 순서), 마지막으로 고른 점 하나만 떼어 내는 절단을 후보로 적어 둔 뒤 마지막 두 점을 합칩니다. 이것을 점이 하나 남을 때까지 되풀이하면 후보 가운데 가장 작은 것이 답입니다.

마지막 두 점을 s, t라 하면 최소 절단은 둘을 가르거나 가르지 않거나 둘 중 하나입니다. 가른다면 「t만 떼어 내는 절단」이 이미 s와 t를 가르는 최소 절단이므로 후보에 들어 있고, 가르지 않는다면 s와 t를 한 점으로 합쳐도 답이 변하지 않습니다. 그래서 합치고 되풀이하면 됩니다.

네트워크가 얼마나 잘 견디는지 재는 데 씁니다. 최소 절단값이 작다는 것은 그만큼의 회선만 끊겨도 통신이 두 동강 난다는 뜻입니다. 이미지 분할, 회로 배치, 군집 나누기에도 같은 문제가 나옵니다.

최소 절단값이 0입니다. 이미 갈라져 있으니 아무것도 끊지 않아도 두 무리로 나뉘기 때문입니다. 이 도구는 그 경우를 따로 알려줍니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력한 그래프는 이 기기에만 남습니다.