LR FLow 를 공부해보았다.

[주의] 그냥 끄적거린 글입니다.

 

LR flow 에 대해서 공부를 해보았습니다

 

방법에 대해선 구글에 많으니 생략하고 유의할 점에 대해서 적어보겠습니다.

 

일반적으로 LR Flow에는 demand 값이라고 이 정점을 지나가는 유량에 대한 정보가 있습니다.

 

이 demand 값을 잘 설정해줘야 한다는 것입니다.

 

즉 demand 가 없고 간선의 하한 상한만 존재하는 그래프에선 알아서 잘 circulation 하게 그래프를 만들어줘야 한다는 점입니다. (초기 그래프의 demand 값이 0이 되도 상관 없기 때문입니다 )

 

아니면 정점에 demand 값을 알맞게 배분해주는 방법도 있겠지만 이 경우는 반례가 생길 수도 있고 위험합니다.

 

circulation 하게 그래프를 만드는 방법에 대해서 잘 모르겠긴 하지만 일반적으로 소스 싱크가 있는 그래프에선 싱크 -> 소스로 무한대의 값의 플로우를 흘려주면 됩니다.