Main Content

maxflow

그래프의 최대 흐름(Maximum Flow)

설명

예제

mf = maxflow(G,s,t)는 노드 s와 노드 t 사이의 최대 흐름을 반환합니다. 그래프 G가 비가중 그래프(Unweighted Graph)(즉, G.Edges가 변수 Weight를 포함하지 않음)이면 maxflow가 모든 그래프 간선을 가중치가 1인 것으로 처리합니다.

예제

mf = maxflow(G,s,t,algorithm)은 사용할 최대 흐름 알고리즘(Maximum Flow Algorithm)을 지정합니다. 이 구문은 G가 유방향 그래프인 경우에만 사용할 수 있습니다.

예제

[mf,GF] = maxflow(___)는 위에 열거된 구문에 나와 있는 입력 인수 중 하나를 사용하여 유방향 graph 객체 GF도 반환합니다. GFG에서 0이 아닌 흐름 값을 갖는 간선만 사용하여 형성됩니다.

예제

[mf,GF,cs,ct] = maxflow(___)는 또한 최대 흐름과 연결된 최소 절단(Minimum Cut)을 나타내는 소스 노드 ID와 타깃 노드 ID, 즉 csct도 반환합니다.

예제

모두 축소

가중 그래프(Weighted Graph)를 생성하고 플로팅합니다. 가중치 간선은 흐름 용량을 나타냅니다.

s = [1 1 2 2 3 4 4 4 5 5];
t = [2 3 3 4 5 3 5 6 4 6];
weights = [0.77 0.44 0.67 0.75 0.89 0.90 2 0.76 1 1];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered');

Figure contains an axes object. The axes object contains an object of type graphplot.

노드 1에서 노드 6까지의 최대 흐름을 확인합니다.

mf = maxflow(G,1,6)
mf = 1.2100

그래프를 생성하고 플로팅합니다. 가중치 간선은 흐름 용량을 나타냅니다.

s = [1 1 2 2 3 3 4];
t = [2 3 3 4 4 5 5];
weights = [10 6 15 5 10 3 8];
G = digraph(s,t,weights);
H = plot(G,'EdgeLabel',G.Edges.Weight);

Figure contains an axes object. The axes object contains an object of type graphplot.

노드 1과 노드 5 사이의 최대 흐름 값을 구합니다. 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)을 사용하도록 'augmentpath'를 지정하고 0이 아닌 흐름에 대한 그래프를 반환할 두 개의 출력값을 사용합니다.

[mf,GF] = maxflow(G,1,5,'augmentpath')
mf = 11
GF = 
  digraph with properties:

    Edges: [6x2 table]
    Nodes: [5x0 table]

0이 아닌 흐름에 대한 그래프를 강조 표시하고 레이블을 지정합니다.

H.EdgeLabel = {};
highlight(H,GF,'EdgeColor','r','LineWidth',2);
st = GF.Edges.EndNodes;
labeledge(H,st(:,1),st(:,2),GF.Edges.Weight);

Figure contains an axes object. The axes object contains an object of type graphplot.

가중 그래프(Weighted Graph)를 생성하고 플로팅합니다. 간선 가중치는 흐름 용량을 나타냅니다.

s = [1 1 2 3 3 4 4 5 5];
t = [2 3 3 2 5 5 6 4 6];
weights = [0.77 0.44 0.67 0.69 0.73 2 0.78 1 1];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered')

Figure contains an axes object. The axes object contains an object of type graphplot.

그래프의 최대 흐름(Maximum Flow)과 최소 절단을 구합니다.

[mf,~,cs,ct] = maxflow(G,1,6)
mf = 0.7300
cs = 3×1

     1
     2
     3

ct = 3×1

     4
     5
     6

cs 노드를 소스로 사용하고 ct 노드를 싱크로 사용하여 최소 절단을 플로팅합니다. cs 노드를 빨간색으로 강조 표시하고 ct 노드를 녹색으로 강조 표시합니다. 참고로, 이 두 노드의 집합을 연결하는 간선의 가중치는 최대 흐름과 같습니다.

H = plot(G,'Layout','layered','Sources',cs,'Sinks',ct, ...
    'EdgeLabel',G.Edges.Weight);
highlight(H,cs,'NodeColor','red')
highlight(H,ct,'NodeColor','green')

Figure contains an axes object. The axes object contains an object of type graphplot.

입력 인수

모두 축소

입력 그래프로, graph 객체 또는 digraph 객체로 지정됩니다. 무방향 그래프를 생성하려면 graph를 사용하고 유방향 그래프를 생성하려면 digraph를 사용하십시오.

예: G = graph(1,2)

예: G = digraph([1 2],[2 3])

노드 쌍으로, 소스 노드와 타깃 노드를 나타내는 노드 인덱스 또는 노드 이름의 개별 인수로 지정됩니다. 다음 표에서는 노드 인덱스 또는 노드 이름을 사용하여 노드를 참조하는 몇 가지 방법을 보여줍니다.

예제
스칼라 노드 인덱스1
문자형 벡터 노드 이름'A'
string형 스칼라 노드 이름"A"

예: mf = maxflow(G,'A','B')

예: mf = maxflow(G,1,10)

데이터형: double | char | string

최대 흐름 알고리즘으로, 다음 표의 항목 중 하나로 지정됩니다.

참고

유방향 그래프에만 디폴트가 아닌 algorithm 옵션을 지정할 수 있습니다.

옵션설명
'searchtrees'(디폴트 값)

보이코프-콜모고로프 알고리즘(Boykov-Kolmogorov Algorithm)을 사용합니다. 노드 s와 노드 t에 연결된 두 개의 탐색 트리를 생성하여 최대 흐름을 계산합니다.

'augmentpath'

포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)을 사용합니다. 잔차 유방향 그래프에서 확장되는 경로를 구해 최대 흐름을 반복적으로 계산합니다.

유방향 그래프는 동일한 두 노드 사이에 있는 반대 방향의 다중 간선(Parallel Edge) 중 하나의 가중치가 0인 경우가 아니라면 이러한 간선을 동일한 두 노드 사이에 포함할 수 없습니다. 따라서 그래프가 간선 [i j]를 포함하는 경우 [i j]의 가중치와 [j i]의 가중치 중 하나 또는 이 둘 모두가 0일 때에만 반대 방향의 간선 [j i]를 포함할 수 있습니다.

'pushrelabel'

노드의 과다 흐름(Excess Flow)을 해당 이웃에 밀어넣은(Push) 후 노드에 레이블을 다시 지정하여 최대 흐름을 계산합니다.

유방향 그래프는 동일한 두 노드 사이에 있는 반대 방향의 다중 간선(Parallel Edge) 중 하나의 가중치가 0인 경우가 아니라면 이러한 간선을 동일한 두 노드 사이에 포함할 수 없습니다. 따라서 그래프가 간선 [i j]를 포함하는 경우 [i j]의 가중치와 [j i]의 가중치 중 하나 또는 이 둘 모두가 0일 때에만 반대 방향의 간선 [j i]를 포함할 수 있습니다.

예: mf = maxflow(G,'A','D','augmentpath')

출력 인수

모두 축소

최대 흐름으로, 스칼라로 반환됩니다.

흐름에 대한 유방향 그래프로, digraph 객체로 반환됩니다. GFG와 동일한 노드를 포함하지만, G의 간선 중 0이 아닌 흐름을 갖는 간선만 포함합니다. 동일한 두 노드 사이에 다중 간선이 있는 다중 그래프의 경우, GF는 다중 간선을 통과하는 흐름을 반영하는 하나의 간선을 포함합니다.

최소 절단 소스 노드 ID로, 노드 인덱스 또는 노드 이름으로 반환됩니다.

  • st가 숫자형 노드 인덱스를 지정할 경우 csct도 노드 인덱스를 갖습니다.

  • st가 노드 이름을 지정할 경우 csct도 노드 이름을 갖습니다.

최소 절단 타깃 노드 ID로, 노드 인덱스 또는 노드 이름으로 반환됩니다.

  • st가 숫자형 노드 인덱스를 지정할 경우 csct도 노드 인덱스를 갖습니다.

  • st가 노드 이름을 지정할 경우 csct도 노드 이름을 갖습니다.

세부 정보

모두 축소

최대 흐름(Maximum Flow)

최대 흐름에서 그래프의 간선은 간선 가중치로 표현되는 용량을 갖는 것으로 간주됩니다. 간선의 용량은 해당 간선을 통과할 수 있는 흐름의 양입니다. 따라서, 그래프에서 두 노드 사이의 최대 흐름은 연결되는 간선의 용량을 기반으로 하여 소스 노드 s에서 타깃 노드 t로 전달되는 흐름의 양을 최대화합니다.

최소 절단(Minimum Cut)

최소 절단은 csct를 연결하는 모든 간선의 가중치 합(절단의 가중치)이 최소화되도록 유방향 그래프 노드를 두 개의 집합 csct로 분할합니다. 최소 절단의 가중치는 최대 흐름 값 mf와 동일합니다.

csct의 항목은 각각 노드 s와 노드 t에 연결된 G의 노드를 나타냅니다. csctnumel(cs) + numel(ct) = numnodes(G)를 충족합니다.

확장 기능

스레드 기반 환경
MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

버전 내역

R2015b에 개발됨

참고 항목

|