플로우 네트워크

Flow network

그래프 이론에서 흐름 네트워크(트랜스포트 네트워크라고도 함)는 각 가장자리가 용량을 가지며 각 가장자리가 흐름을 받는 방향 그래프입니다.에지의 흐름 양은 에지의 용량을 초과할 수 없습니다.운영 연구에서는 방향 그래프를 네트워크, 정점을 노드, 모서리를 호라고 합니다.플로우는 발신 플로우만 있는 소스 또는 착신 플로우만 있는 싱크가 아닌 한 노드로의 흐름량이 노드로부터의 흐름량과 같다는 제한을 충족해야 합니다.네트워크는 컴퓨터 네트워크의 트래픽, 수요에 따른 순환, 파이프 내의 유체, 전기 회로 내의 전류 또는 노드 네트워크를 통해 이동하는 유사한 모든 것을 모델링하기 위해 사용될 수 있습니다.

정의.

네트워크그래프 G = (V, E)이며, 여기서 V는 V × V부분 집합이며, E는 용량 함수라고 불리는 이 아닌 함수 c: V × V {\와 함께 V의 가장자리 집합입니다.일반성의 손실 없이, 만약 (u, v) e E가 또한 (v, u) e E라면, 우리는 E에 (v, u)를 더하고 c(v, u) = 0으로 설정할 수 있기 때문에, (u, u)도 E의 멤버라고 가정할 수 있다.

G 의 2 개의 노드가 구별되어 있는 경우, 송신원싱크 t 가 구별되어 있는 경우, (G, c, s, t) [1]를 플로우 네트워크라고 부릅니다.

플로우

흐름 함수에는 흐름 그래프에서 정의할 수 있는 다양한 개념이 있습니다.플로우 함수는 노드 쌍 간의 유닛의 순플로우를 모델링하여 소스 노드로부터 싱크 노드 t로 전송할 수 있는 유닛의 최대 수를 묻는 질문에 도움이 됩니다.흐름 함수의 가장 단순한 예는 의사 흐름이라고 알려져 있습니다.

의사 흐름은 함수 f : V × V {\이며, 모든 노드 u v에 대해 다음 두 가지 제약 조건을 충족합니다.
  • 스큐 대칭:노드 쌍 u와 v 사이의 단위 순 흐름만 인코딩하십시오(아래 직관 참조). 즉, f(u, v) = -f(v, u)입니다.
  • 용량 제약:아크의 흐름은 그 용량을 초과할 수 없습니다., f(u, v) c c(u, v)입니다.


플로우 네트워크 내의 의사 흐름f를 지정하면 소정의 노드u에 들어가는 순흐름, 즉 u에 들어가는 흐름의 합계를 고려하는 것이 많은 경우 도움이 됩니다.초과 함수f x : V {\ x (u) = δvV f (v, u)로f 정의됩니다.노드 u는 x(u) > 0이면f 활성, x(u) < 0이면 결핍f, x(u) = 0이면f 보존이라고 한다.

이러한 최종 정의는 의사 흐름의 정의를 두 가지로 강화합니다.

프리플로우는 모든 v µ V \{s}에 대해 다음 추가 제약을 충족하는 의사 흐름입니다.
  • 부족하지 않은 흐름:노드 v에 들어가는 순 흐름은 흐름을 "생산"하는 소스를 제외하고 음수가 아닙니다.f, 모든 v v V \{s}에 대해 x(v) 0 0입니다.
실현 가능한 흐름 또는 단순한 흐름은 모든 v µ V \{s, t}에 대해 추가 제약을 충족하는 의사 흐름입니다.
  • 흐름 보존:노드 v에 들어가는 순 흐름은 흐름을 "생산"하는 소스 및 흐름을 "소비"하는 싱크를 제외하고 0입니다.f, 모든 v µ V \{s, t}에 대해 x(v) = 0입니다.


실현 가능한 플로우 f(f)의 값은 플로우네트워크 싱크t로의 순플로우입니다.즉, f = xf (t)이다.

직감

흐름 분석의 맥락에서, 전체적인 의미에서 노드 간에 유닛이 어떻게 전송되는지를 고려하는 데에만 관심이 있습니다.바꿔 말하면 노드 쌍 간에 여러 개의 호를 구분할 필요가 없습니다.

  • 임의의 2개의 노드 u와 v에 각각 용량 5와 3의 아크가 u에서 v로 2개 존재하는 경우 이는 u와 v 사이단일 아크를 8로 고려하는 것과 같습니다. 8개의 유닛을 u에서 v로 전송할 수 있다는 것을 알아야 합니다.
  • 다시 말해, 2개의 노드 uv에서 5개의 유닛에서 v로, 또 다른 3개의 유닛플로우v에서 v로, 즉 2개의 유닛의 플로우가 u에서 v로, 또는 v에서 u로(따라서 부호는 방향을 나타냄) -2개유닛의 순플로우가 u와 v 사이에서 흐른다는 것을 알아야 합니다.네트워크 흐름의 실현 방법이 아니라 흐름의 흐름입니다.

따라서 동일한 노드에서 시작하고 끝나는 여러 개의 호를 허용하지 않는 용량 함수 c: V × V {\이면 흐름 분석에 충분하다.마찬가지로 스큐 대칭을 통해 암묵적으로 u와 v 사이흐름을 파악함으로써 두 정점 사이의 흐름이 단일 숫자(크기를 나타내기 위해)와 기호(방향 나타내기 위해)로 부호화되도록 흐름 함수에 스큐 대칭 제약을 가하는 것으로 충분합니다.이러한 모델의 단순화가 항상 즉각적으로 직관적인 것은 아니지만 흐름을 분석할 때 편리합니다.

캐퍼시티 제약에 의해 네트워크 내의 임의의 아크의 플로우가 그 아크의 캐퍼시티를 넘지 않도록 할 뿐입니다.

흐름 문제에 유용한 개념

잔차

c로 표시f 의사 흐름 f에 대한 아크의 잔존 용량은 아크의 용량과 그 흐름 사이의 차이이다.즉, c(e) = c(e) - f(e)이다f.이를 통해 G = (V, E)의 아크 집합에서 사용 가능한 용량의 을 모델링하는 G (V, Ef)표시f 잔류 네트워크를 구성할 수 있다.보다 형식적으로, 플로우 네트워크 G가 주어졌을 때, 잔류f 네트워크 G는 노드 세트 V, 아크f 세트 E = {e × V × V : cf (e) > 0} 및 용량f 함수 c를 가진다.

개념은 플로우네트워크의 최대 플로우를 계산하는 Ford-Fulkerson 알고리즘에서 사용됩니다.

원래 네트워크에는 u에서 v로의 경로가 없지만 나머지 네트워크에는 u에서 v로의 경로가 있을 수 있습니다.반대 방향의 흐름은 소거되므로 v에서u로의 흐름u에서v로의 흐름증가와 같습니다.

경로 증가

증강 패스는 잔류 네트워크 내의 패스(u1, u2, ..., uk)입니다.여기1 u = sk, u = t 및 cf (uii + 1, u) > 0 입니다.잔존 네트워크f G에 증강 패스가 없는 경우에만 네트워크는 최대 흐름입니다.

여러 소스 및/또는 싱크

복수의 소스를 가지는 네트워크를 모델링 하는 경우,[2] 슈퍼소스가 그래프에 도입되는 경우가 있습니다.이것은 글로벌 소스로 기능하기 위해 무한 용량의 에지를 가진 각 소스에 연결된 정점으로 구성됩니다.싱크에도 유사한 구조를 [3]슈퍼싱크라고 합니다.

흐름과 용량을 나타내는 흐름 네트워크

좌측에는 s, sink t 및 4개의 추가 노드가 라벨이 붙은 플로우네트워크가 표시됩니다.흐름과 용량은 fc로 표시됩니다.네트워크가 스큐 대칭, 용량 제약 및 흐름 보존을 어떻게 지지하는지 주목하십시오.s에서 t로의 흐름의 총량은 5입니다.이것은, 에서 t로의 흐름의 총합이 5인 것을 보면 쉽게 알 수 있습니다.다른 노드에서는 플로우가 표시되지 않거나 사라지지 않는 것을 알고 있습니다.

상기 플로우 네트워크의 잔존 네트워크.잔존 용량을 나타냅니다.

다음에, 소정의 플로우의 잔존 네트워크를 나타냅니다. (d, )\ , ) 등, 원래의 용량이 제로인 일부 엣지에는 양의 잔존 용량이 있는 것에 주의해 주세요.이 흐름은 최대 플로우가 아닙니다. , , , t) { , , ),(s , , , , ) , , d , t ) ( , a , b , , t ) (, ,c , displaystyle s , a , a ,, b , d , d , t 、 displaystyle ) )는, c , t 、 t}경로를 따라 사용 가능한 용량이 있습니다.첫번째 경로의 잔여 용량은(c(s,)− f(s,), c(, c)− f(, c), c(ct)− f(ct)){\displaystyle \min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))})분(5− 3,3− 2,2− 1))분(2,1,1)=1{\displaystyle =\min(5-3,3-2,2-1)=\min(2,1,1)=1}.[표창 필요한]이.오래 된 것 exists는 양의 잔류 용량을 가진 패스를 가지고 있기 때문에 흐름은 최대가 되지 않습니다.일부 경로에 대한 잔류 용량은 해당 경로에 있는 모든 모서리의 최소 잔류 용량입니다.

적용들

네트워크에 맞는 일련의 수도관을 상상해 보십시오.각 파이프는 지름이 일정하기 때문에 일정량의 물만 흐를 수 있습니다.파이프가 만나는 곳이라면, 그 교차점에 들어오는 물의 총량은 나가는 물의 양과 같아야 합니다. 그렇지 않으면 물이 금방 바닥나거나 물이 쌓일 것입니다.우리는 원천인 물 흡입구와 싱크대를 가지고 있다.그러면 물이 원천에서 싱크대로 유입되어 배출구에서 나오는 총 물의 양이 일정하게 유지되도록 하는 하나의 방법이 될 수 있습니다.직관적으로 네트워크의 총 흐름은 출구에서 물이 나오는 속도입니다.

흐름은 교통망을 통한 사람이나 물질 또는 배전 시스템을 통한 전기와 관련될 수 있습니다.이러한 물리 네트워크에서는, 임의의 중간 노드에 착신하는 플로우는, 그 노드로부터 발신되는 플로우와 같게 할 필요가 있습니다.이 보존 제약은 키르히호프의 현행 법칙과 동일합니다.

플로우 네트워크는 생태학에서도 응용할 수 있습니다.플로우 네트워크는 먹이사슬 내의 다른 유기체 간의 영양소와 에너지의 흐름을 고려할 때 자연스럽게 발생합니다.이러한 네트워크와 관련된 수학적 문제는 유동성 또는 트래픽 흐름의 네트워크에서 발생하는 문제와는 상당히 다릅니다.Robert Ulanowicz와 다른 사람들에 의해 개발된 생태계 네트워크 분석 분야는 시간 경과에 따른 이러한 네트워크의 진화를 연구하기 위해 정보 이론과 열역학 개념을 사용합니다.

흐름 문제의 분류

플로우 네트워크를 사용하는 가장 간단하고 일반적인 문제는 최대 흐름이라고 불리는 것을 찾는 것입니다.최대 흐름은 소정의 그래프에서 소스에서 싱크까지 가능한 최대 총 흐름을 제공합니다.최대 흐름 알고리즘을 사용하여 해결할 수 있는 다른 많은 문제가 있습니다.를 들어 초당 매칭, 할당 문제, 전송 문제 등 흐름 네트워크로 적절하게 모델링된 경우입니다.푸시-릴라벨 알고리즘을 사용하면 최대 흐름 문제를 효율적으로 해결할 수 있습니다.max-flow min-cut 정리에서는 최대 네트워크 플로우를 찾는 것은 소스와 싱크를 분리하는 최소 용량의 컷을 찾는 것과 동등합니다.여기서 컷은 소스가 하나의 분할에 있고 싱크가 다른 분할에 있는 정점의 분할입니다.

최대 흐름 문제에 대한 기존 알고리즘
Inventor(들) 연도 시간을
복잡성
(n 노드 포함)
mcs)
다이닉 알고리즘 1969 O(mn2)
에드먼즈-카르프 알고리즘 1972 O(m2n)
MPM(Malhotra, Pramodh-Kumar, Maheshwari)
알고리즘[4]
1978 O(n3)
제임스 B.올린[5] 2013 O(mn)

멀티커뮤니티 플로우 문제에서는, 복수의 송신원과 싱크가 존재해, 특정의 송신원에서 특정의 싱크까지 다양한 「커뮤니티」가 흐릅니다.예를 들어, 다양한 공장에서 생산되어 동일한 운송 네트워크를 통해 다양한 고객에게 배송되는 다양한 상품일 수 있다.

최소 비용 흐름 문제에서는 각 u,v는 소정의 { k 가집니다.또, 엣지를 개입시켜 v) { v)}를 송신하는 ( v f입니다.소스에서 싱크대까지 가능한 한 저렴한 가격에 공급합니다.

순환 문제에서는 상한 ,v )(\( , v)\c 외에 에는 하한((, 가 있습니다.각 가장자리에는 비용도 있습니다.대부분의 경우 순환 문제의 모든 노드에서 흐름 보존이 유지되며 싱크에서 소스로의 접속이 있습니다.이와 같이 흐름은 "( ,) \ , ) (c ( , s ) ( c t , s ). c the the the the the the the the the the the the the 。플로우는 네트워크를 순환하므로 문제의 이름이 됩니다.

게인 또는 일반화된 네트워크를 가진 네트워크에서는 각 에지가 게인을 가지며, 에지가 게인 g를 가지며, x가 꼬리 부분에 에지로 흐르면 헤드에서 gx가 흐른다.

소스 현지화 문제에서 알고리즘은 부분적으로 관측된 네트워크를 통해 정보 확산의 가장 가능성이 높은 소스 노드를 식별하려고 한다.이는 트리의 경우 선형 시간, 임의의 네트워크의 경우 입방 시간 내에 수행될 수 있으며, 휴대전화 사용자의 추적에서 질병 [6]발생 원인 확인에 이르기까지 다양한 응용 프로그램을 갖추고 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ A.V. Goldberg, E. Tardos 및 R.E. Tarjan, 네트워크 흐름 알고리즘, Tech.Stanford University CS Dept, STAN-CS-89-1252 보고서, 1989.
  2. ^ Public Domain이 문서에는 NIST 문서퍼블릭 도메인 자료가 포함되어 있습니다.Black, Paul E. "Supersource". Dictionary of Algorithms and Data Structures.
  3. ^ Public Domain이 문서에는 NIST 문서퍼블릭 도메인 자료가 포함되어 있습니다.
  4. ^ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). "An algorithm for finding maximum flows in networks" (PDF). Information Processing Letters. 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9.
  5. ^ Orlin, James B. (2013-06-01). "Max flows in O(nm) time, or better". Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing. STOC '13. Palo Alto, California, USA: Association for Computing Machinery: 765–774. doi:10.1145/2488608.2488705. hdl:1721.1/88020. ISBN 978-1-4503-2029-0. S2CID 207205207 – via MIT Open Access https://dspace.mit.edu/handle/1721.1/88020. {{cite journal}}:외부 링크 via=(도움말)
  6. ^ Pinto, P.C.; Thiran, P.; Vetterli, M. (2012). "Locating the source of diffusion in large-scale networks" (PDF). Physical Review Letters. 109 (6): 068702. arXiv:1208.2534. Bibcode:2012PhRvL.109f8702P. doi:10.1103/PhysRevLett.109.068702. PMID 23006310. S2CID 14526887.

추가 정보

외부 링크