순환 문제

순환 문제와 그 변형은 네트워크 흐름 문제의 일반화로서, 에지 흐름의 하한 제한조건이 추가되고, 흐름 보존이 소스 및 싱크에도 요구된다(즉, 특별한 노드가 없다).문제의 변이형에서는 네트워크를 통해 여러 가지 상품이 흘러가고, 그 흐름에는 비용이 든다.

정의

다음을 포함하는$$ 흐름 네트워크 $G{\displaystyle (V}$, ${\displaystyle E}$) ${\displaystyle G(V,E)}:$

${\displaystyle l}$( ${\displaystyle v}$, w${\displaystyle }$) ${\displaystyle l(v,w$ $노드{\displaystyle }$ v ${\displaystyle v}$에서 노드 $w{\displaystyle }$ ${\displaystyle$ w$}(으$)로의 흐름 하한$,$

${\displaystyle u(v}$ ${\displaystyle ,}$ w${\displaystyle }$) ${\displaystyle u(v,w$ 노드 $v{\displaystyle }$ ${\displaystyle v}$에서 노드 $w{\displaystyle }$ ${\displaystyle w$으)로의$$ 흐름 상한,

${\displaystyle c}$( ${\displaystyle v}$, ${\displaystyle w}$) ${\displaystyle c(v,w$ $({\displaystyle v}$ ${\displaystyle ,}$ w${\displaystyle }$) ${\displaystyle (v,w)}$에 대한 흐름 단위 비용

및 제약 조건:

${\displaystyle l}$( ${\displaystyle v}$, ${\displaystyle w}$) ${\displaystyle \le }$ ${\displaystyle f}$( ${\displaystyle v}$, ${\displaystyle w}$) ${\displaystyle \le }$ ${\displaystyle u}$ ${\displaystyle (v}$, w${\displaystyle }$) ${\displaystyle l(v,w)\leq f(v,w)\leq u(v,w$

${\displaystyle \sum _{}}$ ${\displaystyle \underset{}{w}}$ ${\displaystyle \underset{}{\in }}$ ${\displaystyle \underset{}{V}}$ ${\displaystyle \underset{}{}}$(${\displaystyle \mathrm{u}}$, w${\displaystyle }$)${\displaystyle }$= 0 ${\displaystyle \sum _{w\in V}f(u,w)=0}($노드에서 흐름이 나타나거나 사라질 수 없음)

제약을 만족시키는 흐름 과제를 발견하면 주어진 순환 문제에 대한 해결책이 나온다.

문제의 최소 비용 변종에서 최소화

${\displaystyle \sum _{(v,w)\in E}c(v,w)\cdot f(v,w).}$

다품종 순환

다품종 유통 문제에서는 개별 상품의 흐름을 추적할 필요가 있다.

${\displaystyle \,f_{i}(v,w)}$	$v{\displaystyle }$ ${\displaystyle v}$에서 $w{\displaystyle }$ ${\displaystyle w}($으)로의$$ 범용 $i{\displaystyle }$ ${\displaystyle i}$의 흐름$.$
${\displaystyle \,f(v,w)=\sum _{i}f_{i}(v,w)}$	전체 흐름.

또한 상품 흐름마다 하한선이 있다.

${\displaystyle \,l_{i}(v,w)\leq f_{i}(v,w)}$

보존 제약조건은 물품에 대해 개별적으로 유지되어야 한다.

${\displaystyle \\sum _{w\in V}f_{i}(u,w)=0.}$

해결책

순환 문제를 위해 많은 다항 알고리즘이 개발되었다(예: Edmonds-Karp 알고리즘, 1972; Tarjan 1987-1988)타도스는 최초의 강력한 다항식 알고리즘을 발견했다.^[1]

복수의 원자재의 경우 정수흐름의 경우 NP-완전성이 문제다.^[2]분수 흐름의 경우 문제를 선형 프로그램으로 공식화할 수 있기 때문에 다항식 시간에 해결할 수 있다.

관련 문제

아래에는 몇 가지 문제가 주어지며, 위에서 제시한 일반적인 순환설정으로 이를 해결하는 방법이 제시되어 있다.

• 최소 비용 다품종 순환 문제 - 위에 제시된 모든 제약 조건 사용.
• 최소 비용 순환 문제 - 단일 물품 사용
• 멀티 커밋 순환 - 비용 최적화 없이 해결
• 단순 순환 - 하나의 상품만 사용하고 비용은 들지 마십시오.
• Multi-commodity flow - If ${\displaystyle K_{i}(s_{i},t_{i},d_{i})}$ denotes a demand of ${\displaystyle d_{i}}$ for commodity ${\displaystyle i}$ from ${\displaystyle s_{i}}$ to ${\displaystyle t_{i}}$, create an edge ${\displ$$aystyle (t_{i},s_{i})}$ with ${\displaystyle l_{i}(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}$ for all commodities ${\displaystyle i}$. Let ${\displaystyle l_{i}(u,v)=0}$ for all other edges.
• 최소 비용 다중 커밋 흐름 문제 - 위와 같이 비용을 최소화하십시오.
• 최소 비용 흐름 문제 - 위와 같이 1개 상품.
• Maximum flow problem - Set all costs to 0, and add an edge from the sink ${\displaystyle t}$ to the source ${\displaystyle s}$ with ${\displaystyle l(t,s)=0}$, ${\displaystyle u(t,s)=}$∞ and ${\displaystyle c(t,s)=-1}$.
• 최소 비용 최대 흐름 문제 - 먼저 최대 $흐름량{\displaystyle }$ m ${\displaystyle m}$을(를) 찾으십시오$.$$그런{\displaystyle }$ 다음 l${\displaystyle }$( ${\displaystyle t}$, ${\displaystyle s}$)${\displaystyle }$= ${\displaystyle u}$ ${\displaystyle (}$ t${\displaystyle }$, s${\displaystyle }$)${\displaystyle }$= m ${\displaystyle l(t,s)=u(t,s)=m}$ 및 $c$(t, ${\displaystyle s}$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle c(t,s)=0}$으로 해결하십시오$.$
• Single-source shortest path - Let ${\displaystyle l(u,v)=0}$ and ${\displaystyle c(u,v)=1}$ for all edges in the graph, and add an edge ${\displaystyle (t,s)}$ with ${\displaystyle l(t,s)=c(t,s)=1}$ and ${\displaystyle a(t,s)=0}$.
• 올 페어 최단 경로 - 모든 용량을 무제한으로 설정하고 v(${\displaystyle }v{\displaystyle }$- ${\displaystyle 1)/2\mathrm{}}$ ${\displaystyle v(v-1)/$2}$물품$에 대해 각 노드 쌍에 하나씩 흐름 1을 찾으십시오.

참조