maxflow
그래프의 최대 흐름(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
그래프를 생성하고 플로팅합니다. 가중치 간선은 흐름 용량을 나타냅니다.
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: [6×2 table]
Nodes: [5×0 table]
0이 아닌 흐름에 대한 그래프를 강조 표시하고 레이블을 지정합니다.
H.EdgeLabel = {};
highlight(H,GF,'EdgeColor','r','LineWidth',2);
st = GF.Edges.EndNodes;
labeledge(H,st(:,1),st(:,2),GF.Edges.Weight);
가중 그래프(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')
입력 인수
출력 인수
세부 정보
확장 기능
버전 내역
R2015b에 개발됨
