버텍스 집합 사이의 흐름

Question

버텍스 집합과 관련하여 흐름의 의미가 무엇인지 혼란 스럽습니다.

말 : f(s,V), s는 소스이고 V는 정점 세트입니다. 평균/v 이상의 합은 s와 함께 V에 속한다.

그러나 f(X,Y) 여기서 X와 Y는 모두 세트입니다. 그게 무슨 뜻 이죠? 각 쌍 사이에 합계가 있습니까?

이 문맥에서 왜 f(X,X)=0, X은 {a,b}입니다.

Answer 1

여러 소스/싱크의 경우 흐름 정의는 단일 소스/싱크의 경우와 유사합니다.

각 소스의 유입 흐름은 0이어야합니다. 각 싱크에는 0 개의 보내는 흐름이 있어야합니다. 다른 모든 노드는 동일한 송수신 흐름을 가져야합니다. 흥미롭게도, 다수의 소스/싱크 노드의 경우의 흐름은 단일 소스 - 단일 싱크 경우로 감소 될 수있다.

우리가 그래프 G, X로 표시 소스 노드의 세트 및 Y로 표시 싱크 노드의 집합을 가정 해 봅시다.

우리는 새로운 그래프를 만들 것이며, 그 다음 연결와 S 및 t로 표시된 두 개의 추가 노드를 갖는 것을 제외 G 거의 동일 G ' :

S

• 는 X 각 노드를 향해 발신 에지를 갖는다. 이 가장자리를 무한대의 용량으로 설정하십시오.

• t는 X 각 노드로부터 수신되는 에지를 갖는다. 또한이 가장자리를 무한대의 용량으로 설정하십시오.

그 다음, 소스는 싱크 X는 G '에서 어떠한 흐름 을 Y 세트로부터 어떤 흐름 간의 직접적인 일대일 G가 소스 을 싱크대 t에 연결합니다.

그리고, 추론, G 'X에서도 G에 최대 유량 값을 나타내는 S 을 t에서 에 Y의 최대 유량 등.