maxflow
그래프의 최대 흐름(Maximum Flow)
구문
설명
예제
그래프의 최대 흐름(Maximum Flow)
가중 그래프(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');
노드 1에서 노드 6까지의 최대 흐름을 확인합니다.
mf = maxflow(G,1,6)
mf = 1.2100
지정된 알고리즘을 사용한 최대 흐름(Maximum Flow)
그래프를 생성하고 플로팅합니다. 가중치 간선은 흐름 용량을 나타냅니다.
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);
노드 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);
최소 절단(Minimum Cut) 계산
가중 그래프(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')
그래프의 최대 흐름(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')
입력 인수
s,t
— 노드 쌍(개별 인수)
노드 인덱스 | 노드 이름
노드 쌍으로, 소스 노드와 타깃 노드를 나타내는 노드 인덱스 또는 노드 이름의 개별 인수로 지정됩니다. 다음 표에서는 노드 인덱스 또는 노드 이름을 사용하여 노드를 참조하는 몇 가지 방법을 보여줍니다.
값 | 예제 |
---|---|
스칼라 노드 인덱스 | 1 |
문자형 벡터 노드 이름 | 'A' |
string형 스칼라 노드 이름 | "A" |
예: mf = maxflow(G,'A','B')
예: mf = maxflow(G,1,10)
데이터형: double
| char
| string
algorithm
— 최대 흐름 알고리즘(Maximum Flow Algorithm)
'searchtrees'
(디폴트 값) | 'augmentpath'
| 'pushrelabel'
최대 흐름 알고리즘으로, 다음 표의 항목 중 하나로 지정됩니다.
참고
유방향 그래프에만 디폴트가 아닌 algorithm
옵션을 지정할 수 있습니다.
옵션 | 설명 |
---|---|
'searchtrees' (디폴트 값) | 보이코프-콜모고로프 알고리즘(Boykov-Kolmogorov Algorithm)을 사용합니다. 노드 |
'augmentpath' | 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)을 사용합니다. 잔차 유방향 그래프에서 확장되는 경로를 구해 최대 흐름을 반복적으로 계산합니다. 유방향 그래프는 동일한 두 노드 사이에 있는 반대 방향의 다중 간선(Parallel Edge) 중 하나의 가중치가 0인 경우가 아니라면 이러한 간선을 동일한 두 노드 사이에 포함할 수 없습니다. 따라서 그래프가 간선 |
'pushrelabel' | 노드의 과다 흐름(Excess Flow)을 해당 이웃에 밀어넣은(Push) 후 노드에 레이블을 다시 지정하여 최대 흐름을 계산합니다. 유방향 그래프는 동일한 두 노드 사이에 있는 반대 방향의 다중 간선(Parallel Edge) 중 하나의 가중치가 0인 경우가 아니라면 이러한 간선을 동일한 두 노드 사이에 포함할 수 없습니다. 따라서 그래프가 간선 |
예: mf = maxflow(G,'A','D','augmentpath')
출력 인수
mf
— 최대 흐름(Maximum Flow)
스칼라
최대 흐름으로, 스칼라로 반환됩니다.
GF
— 흐름에 대한 유방향 그래프
digraph
객체
흐름에 대한 유방향 그래프로, digraph
객체로 반환됩니다. GF
는 G
와 동일한 노드를 포함하지만, G
의 간선 중 0이 아닌 흐름을 갖는 간선만 포함합니다. 동일한 두 노드 사이에 다중 간선이 있는 다중 그래프의 경우, GF
는 다중 간선을 통과하는 흐름을 반영하는 하나의 간선을 포함합니다.
cs
— 최소 절단(Minimum Cut) 소스 노드 ID
노드 인덱스 | 노드 이름
최소 절단 소스 노드 ID로, 노드 인덱스 또는 노드 이름으로 반환됩니다.
s
와t
가 숫자형 노드 인덱스를 지정할 경우cs
와ct
도 노드 인덱스를 갖습니다.s
와t
가 노드 이름을 지정할 경우cs
와ct
도 노드 이름을 갖습니다.
ct
— 최소 절단 타깃 노드 ID
스칼라 | 벡터 | 문자형 벡터 | 문자형 벡터로 구성된 셀형 배열
최소 절단 타깃 노드 ID로, 노드 인덱스 또는 노드 이름으로 반환됩니다.
s
와t
가 숫자형 노드 인덱스를 지정할 경우cs
와ct
도 노드 인덱스를 갖습니다.s
와t
가 노드 이름을 지정할 경우cs
와ct
도 노드 이름을 갖습니다.
세부 정보
최대 흐름(Maximum Flow)
최대 흐름에서 그래프의 간선은 간선 가중치로 표현되는 용량을 갖는 것으로 간주됩니다. 간선의 용량은 해당 간선을 통과할 수 있는 흐름의 양입니다. 따라서, 그래프에서 두 노드 사이의 최대 흐름은 연결되는 간선의 용량을 기반으로 하여 소스 노드 s
에서 타깃 노드 t
로 전달되는 흐름의 양을 최대화합니다.
최소 절단(Minimum Cut)
최소 절단은 cs
와 ct
를 연결하는 모든 간선의 가중치 합(절단의 가중치)이 최소화되도록 유방향 그래프 노드를 두 개의 집합 cs
와 ct
로 분할합니다. 최소 절단의 가중치는 최대 흐름 값 mf
와 동일합니다.
cs
와 ct
의 항목은 각각 노드 s
와 노드 t
에 연결된 G
의 노드를 나타냅니다. cs
와 ct
는 numel(cs) + numel(ct) = numnodes(G)
를 충족합니다.
확장 기능
스레드 기반 환경
MATLAB®의 backgroundPool
을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool
을 사용해 코드 실행 속도를 높일 수 있습니다.
버전 내역
R2015b에 개발됨
MATLAB 명령
다음 MATLAB 명령에 해당하는 링크를 클릭했습니다.
명령을 실행하려면 MATLAB 명령 창에 입력하십시오. 웹 브라우저는 MATLAB 명령을 지원하지 않습니다.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)