네트워크 흐름
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
네트워크 흐름은 유향 그래프로 구성되며, 각 간선에는 용량이 할당되어 있다. 흐름 함수는 노드 쌍 간의 순 흐름을 모델링하며, 소스에서 싱크로 전송할 수 있는 최대 단위를 계산하는 데 사용된다. 주요 개념으로는 용량 제한, 왜곡 대칭성, 흐름 보존 법칙이 있으며, 잔여 네트워크와 증가 경로를 통해 최대 흐름을 계산한다. 네트워크 흐름은 최대 흐름 문제, 이분 매칭, 할당 문제, 교통 문제 등 다양한 문제 해결에 활용되며, 통신 네트워크, 전력망, 다중 상품 흐름 문제 등에도 적용된다.
더 읽어볼만한 페이지
- 운용 과학 - 계획
계획은 목표 달성을 위한 방법과 절차를 결정하는 과정으로, 개인적 목록 작성부터 국가적 자원 사용, 토지 이용 규제 등 다양한 형태로 나타나며, 상위-하향식, 하위-상향식, PDCA 사이클 등의 방법론을 활용하여 명확한 목표 설정, 효율적인 자원 관리, 위험 관리, 유연성을 필요로 한다. - 운용 과학 - 알고리즘 설계
알고리즘 설계는 문제 해결을 위한 효율적인 절차나 방법을 구체화하는 과정으로, 문제 정의부터 문서화까지의 개발 단계를 거치며 분할 정복, 동적 계획법 등의 다양한 설계 기법들이 활용된다. - 그래프 알고리즘 - 페이지랭크
페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다. - 그래프 알고리즘 - 너비 우선 탐색
너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.
네트워크 흐름 |
---|
2. 정의
'''네트워크 흐름'''(Network flow) 또는 '''흐름 네트워크'''(Flow network)는 유향 그래프 (''V'', ''E'')}}로 구성된다. 각 간선에는 음수가 아닌 '''용량''' 함수 가 있으며, 동일한 소스 및 대상 노드를 가진 간선(다중 호)은 없다.[1]
이면 도 의 구성원이라고 가정한다. 만약 이면, 를 ''E''에 추가하고 0}}으로 설정한다.[1]
에서 소스 와 싱크 두 노드를 구분하면, 를 '''흐름 네트워크'''라고 한다.[1]
흐름 네트워크는 실수함수 로 표시되며, 모든 노드 와 에 대해 다음 조건을 만족해야 한다.[3]
용량 제한 | 어떤 변을 흐르는 흐름은 그 용량을 초과할 수 없다. |
---|---|
왜곡 대칭성 | 에서 로의 총 흐름은 에서 로의 총 흐름의 정확히 반대여야 한다. |
흐름 보존 법칙 | (단, 또는 가 아닌 경우). 시작점과 끝점을 제외한 노드에서는 유입되는 흐름과 유출되는 흐름의 합이 0이다. 시작점은 흐름을 생성하고, 끝점은 흐름을 소비한다. |
는 에서 로의 총 흐름을 의미한다. 예를 들어, 에서 로 4단위의 흐름이 있고, 에서 로 3단위의 흐름이 있다면, 및 이 된다.[3]
변의 '''잔여 용량'''은 로 표시된다. '''잔여 네트워크''' 는 사용 가능한 용량으로 구성된 네트워크이다. 원래 네트워크에 에서 로의 변이 없더라도, 잔여 네트워크에는 에서 로의 변이 있을 수 있다. 반대 방향 흐름은 상쇄되므로, 에서 로의 흐름 감소는 에서 로의 흐름 증가를 의미한다. '''증가 경로'''는 잔여 네트워크 내의 경로 (단, , , )이다. 최대 흐름 네트워크는 잔여 네트워크에 증가 경로가 존재하지 않는 경우이다.[3]
2. 1. 흐름(Flow)
흐름 함수는 노드 쌍 간의 단위 순 흐름을 모델링하며, "소스 노드 s에서 싱크 노드 t로 전송할 수 있는 최대 단위 수는 얼마인가?"와 같은 질문에 답할 때 유용하다.[3] 두 노드 간의 흐름량은 한 노드에서 다른 노드로 전송되는 단위의 순량을 나타내는 데 사용된다.[3]유한 유향 그래프 의 각 변 {math|(''u'',''v'') ∈ ''E''}}에 음이 아닌 실수 용량 가 설정되어 있다고 가정한다. 의 경우, 으로 간주한다. 여기서, 두 개의 정점, 시작점 와 끝점 를 구분한다. 흐름 네트워크는 실수함수 로 표시되며, 모든 노드 와 에 대해 다음이 성립한다.[3]
용량 제한 | 어떤 변을 흐르는 흐름은 그 용량을 초과할 수 없다. |
---|---|
왜곡 대칭성 | 에서 로의 총 흐름은 에서 로의 총 흐름의 정확히 반대여야 한다(예시 참조). |
흐름 보존 법칙 | 단 또는 가 아닌 경우. 시작점과 끝점을 제외한 노드에서는 유입되는 흐름과 유출되는 흐름의 합이 0이다. 시작점은 흐름을 생성하고, 끝점은 흐름을 소비한다. |
여기서, 는 에서 로의 흐름의 총합을 의미한다. 그래프가 물리적 네트워크를 나타내고, 에서 로 4단위의 흐름이 있고, 에서 로 3단위의 흐름이 있는 경우, 및 이 된다.[3]
변의 '''잔여 용량'''(residual capacity)은 로 표시되는 양이다. 여기서 '''잔여 네트워크'''(residual network) 가 정의되며, 사용 가능한 용량으로 구성된 네트워크를 의미한다. 원래 네트워크에 에서 로의 변이 없더라도, 잔여 네트워크에는 에서 로의 변이 있는 경우도 있다. 반대 방향의 흐름은 상쇄되므로, 에서 로의 흐름이 감소한다는 것은, 에서 로의 흐름이 증가하는 것을 의미한다. '''증가 경로'''(augmenting path)는 잔여 네트워크 내의 경로 로, 이고 이며, 인 경로를 의미한다. 최대 흐름 네트워크는 잔여 네트워크에 증가 경로가 존재하지 않는 경우를 가리킨다.[3]
'''과잉''' 함수 는 주어진 노드 로 들어가는 순 흐름(즉, 로 들어가는 흐름의 합)을 나타내며 다음과 같이 정의된다.
. 노드 는 이면 '''활성'''이라고 하며(즉, 노드 가 흐름을 소비함), 이면 '''부족'''이라고 하며(즉, 노드 가 흐름을 생성함), 0}}이면 '''보존'''이라고 한다. 흐름 네트워크에서 소스 는 부족하고 싱크 는 활성이다.[3]
의사 흐름, 가능한 흐름 및 사전 흐름은 모두 흐름 함수의 예이다.[3]
- '''의사 흐름'''은 모든 노드 및 에 대해 다음 두 가지 제약 조건을 만족하는 네트워크의 각 간선의 함수 이다.[3]
- '''비대칭성 제약''' : 에서 로의 호의 흐름은 에서 로의 호의 흐름의 부정과 같다. 즉, −''f'' (''v'', ''u'')}}. 흐름의 부호는 흐름의 방향을 나타낸다.
- '''용량 제약''' : 호의 흐름은 용량을 초과할 수 없다. 즉, .
- '''사전 흐름'''은 모든 }에 대해 다음 추가 제약 조건을 만족하는 의사 흐름이다.[3]
- '''부족하지 않은 흐름''' : 노드 로 '들어가는' 순 흐름은 소스를 제외하고 음수가 아니다(소스는 흐름을 "생산"합니다). 즉, for all }.
- '''실현 가능한 흐름''' 또는 그냥 '''흐름'''은 모든 }에 대해 다음 추가 제약 조건을 만족하는 의사 흐름이다.[3]
- '''흐름 보존 제약''' : 소스 와 싱크 를 제외한 네트워크의 모든 노드에 대해 노드로 들어가는 총 순 흐름은 0이다. 즉, 0}} for all }. 즉, 소스 와 싱크 를 제외한 네트워크의 모든 노드에 대해 노드로 들어오는 총 흐름의 합은 나가는 흐름과 같다(즉, , 각 정점 }.
네트워크에 대한 실현 가능한 흐름 의 '''값''' ''f'' }}은 흐름 네트워크의 싱크 로 들어가는 순 흐름이다. 즉, ''f'' ''x''''f'' (''t'')}}. 네트워크의 흐름 값은 또한 소스 의 총 나가는 흐름과 같다. 즉, ''f'' -''x''''f'' (''s'')}}. 또한, 를 이고 인 의 노드 집합으로 정의하면 흐름 값은 A에서 나가는 총 순 흐름과 같다(즉, ''f'' ''f'' out(''A'') - ''f'' in(''A'')}}).[3] 네트워크의 흐름 값은 에서 로의 총 흐름 양이다.[3]
3. 주요 개념
오른쪽 그림은 시작점 , 종점 , 다른 4개의 노드로 구성된 흐름 네트워크이다. 흐름과 용량은 와 같이 표시되어 있다. 이 그림에서 용량 제한, 왜곡 대칭성, 흐름 보존 법칙이 성립한다. 또한, 시작점 에서 종점 로의 총 흐름량이 5라는 것은, 에서 유출되는 흐름량과 에 유입되는 흐름량이 5이고, 다른 노드에서는 흐름의 증감이 없다는 것을 통해 확인할 수 있다.
다음 그림에서는 위 그림의 잔여 네트워크를 나타낸다. 예를 들어, 가지 와 같이 원래 용량이 0이었던 가지에도 잔여 용량이 양수인 것이 존재한다. 이 잔여 네트워크에는 증가 경로 , , 가 존재하므로, 위 그림의 네트워크는 최대 흐름이 아님을 알 수 있다. 예를 들어, 증가 경로 의 잔여 용량은 로 계산할 수 있다. 여기서, 증가 경로 는 원래 네트워크에는 존재하지 않는 경로이지만, 이 경로를 따라 흐름을 보낼 수 있다.
3. 1. 잔여 네트워크(Residual Network)
잔여 네트워크(Residual Network)는 주어진 흐름에 대해 추가적인 흐름을 보낼 수 있는 용량을 나타내는 네트워크이다. 유사 흐름 *f*에 대한 아크 *e*의 잔여 용량 *c**f*는 아크의 용량과 흐름의 차이로, *c**f* (*e*) = *c*(*e*) - *f*(*e*)와 같이 계산된다. 이를 통해 용량 함수 *c**f*를 사용하여 잔여 네트워크 *G**f* (*V*, *E**f*)를 구성할 수 있으며, 이는 *G* = (*V*, *E*)의 아크 집합에서 사용 가능한 용량의 양을 모델링한다.잔여 네트워크의 각 아크 (*u*, *v*)의 용량 함수 *c**f*는 네트워크 내의 현재 흐름 상태를 고려하여 *u*에서 *v*로 전송할 수 있는 흐름의 양을 나타낸다. 예를 들어, 오른쪽 그림에서 가지 (*d*, *c*)와 같이 원래 용량이 0이었던 가지에도 잔여 용량이 양수인 경우가 존재할 수 있다. 이 개념은 포드-풀커슨 알고리즘에서 최대 흐름을 계산하는 데 사용된다.
잔여 네트워크에는 원래 네트워크에 *u*에서 *v*로 가는 경로가 없더라도 *u*에서 *v*로 가는 포화되지 않은 경로(사용 가능한 용량이 있는 경로)가 있을 수 있다. 역방향 흐름은 상쇄되므로 *v*에서 *u*로 흐름을 감소시키는 것은 *u*에서 *v*로 흐름을 증가시키는 것과 같다. 예를 들어, 위쪽 흐름 네트워크의 잔여 네트워크에는 증가 경로 (*s*, *a*, *c*, *t*), (*s*, *a*, *b*, *d*, *t*), (*s*, *a*, *b*, *d*, *c*, *t*)가 존재하므로, 원래 네트워크는 최대 흐름이 아니다. 증가 경로 (*s*, *a*, *c*, *t*)의 잔여 용량은 min{ *c*(*s*, *a*) - *f*(*s*, *a*), *c*(*a*, *c*) - *f*(*a*, *c*), *c*(*c*, *t*) - *f*(*c*, *t*) } = min{ 5 - 3, 3 - 2, 2 - 1 } = min{ 2, 1, 1 } = 1로 계산할 수 있다. 여기서 증가 경로 (*s*, *a*, *b*, *d*, *c*, *t*)는 원래 네트워크에는 존재하지 않는 경로이지만, 이 경로를 따라 흐름을 보낼 수 있다.
3. 2. 증가 경로(Augmenting Path)
증가 경로는 잔여 네트워크에서 와 같은 경로로, ''s''}}, ''t''}}이며, 모든 에 대해 에서 이다.[3] 다시 말해, 증가 경로는 소스에서 싱크로 가는 사용 가능한 흐름 경로이다. 네트워크는 잔여 네트워크 에 증가 경로가 없을 때에만 최대 흐름 상태에 있다.[3]병목은 주어진 증가 경로에 있는 모든 간선의 최소 잔여 용량이다.[3] 흐름 네트워크는 병목 값이 0과 같을 때에만 최대 흐름 상태에 있다. 증가 경로가 존재한다면, 그 병목 가중치는 0보다 클 것이다. 즉, 0보다 큰 병목 값이 있다면, 소스에서 싱크로 가는 증가 경로가 있는 것이다. 하지만, 증가 경로가 있다면 네트워크가 최대 흐름 상태가 아니라는 것을 알고 있으며, 이는 다시 말해 0보다 큰 병목 값이 있다면, 네트워크가 최대 흐름 상태가 아니라는 의미이다.[3]
예를 들어 오른쪽 그림에서 잔여 네트워크에는 증가 경로 , , 가 존재하므로, 위 그림의 네트워크는 최대 흐름이 아님을 알 수 있다.[3] 증가 경로 의 잔여 용량은 로 계산할 수 있다.[3] 여기서, 증가 경로 는 원래 네트워크에는 존재하지 않는 경로이지만, 이 경로를 따라 흐름을 보낼 수 있다.[3]
증가 경로에 대한 "흐름 증가"라는 용어는 이 증가 경로의 각 호의 흐름 를 병목의 용량 와 같도록 업데이트하는 것을 의미한다. 흐름 증가는 병목에 남은 잔여 용량이 없을 때까지 증가 경로를 따라 추가 흐름을 푸시하는 것에 해당한다.
3. 3. 절단(Cut)
4. 최대 흐름-최소 절단 정리(Max-Flow Min-Cut Theorem)
5. 응용
일련의 수도관을 네트워크에 맞추어 상상해 보십시오. 각 파이프는 특정 지름을 가지고 있어 특정 양의 물만 유지할 수 있습니다. 파이프가 만나는 곳에서는 해당 교차점에 들어오는 총 물의 양이 나가는 양과 같아야 합니다. 그렇지 않으면 물이 빨리 떨어지거나 물이 축적될 것입니다. 우리는 원천인 물 입구와 출구, 즉 싱크대가 있습니다. 그러면 흐름은 출구에서 나오는 총 물의 양이 일관되도록 물이 원천에서 싱크대로 가는 한 가지 가능한 방법이 될 것입니다. 직관적으로 네트워크의 총 흐름은 물이 출구에서 나오는 속도입니다.
흐름은 운송 네트워크를 통한 사람 또는 자재와 전력 배전 시스템을 통한 전기에 관련될 수 있습니다. 이러한 모든 물리적 네트워크에서 중간 노드로 들어오는 흐름은 해당 노드에서 나가는 흐름과 같아야 합니다. 이 보존 제약 조건은 키르히호프의 전류 법칙과 동일합니다.
흐름 네트워크는 또한 생태학에서 응용 분야를 찾습니다. 흐름 네트워크는 먹이 사슬에서 서로 다른 유기체 간의 영양분과 에너지의 흐름을 고려할 때 자연스럽게 발생합니다. 이러한 네트워크와 관련된 수학적 문제는 유체 또는 교통 흐름 네트워크에서 발생하는 문제와는 매우 다릅니다. 로버트 울라노위츠 등이 개발한 생태계 네트워크 분석 분야는 이러한 네트워크의 시간 경과에 따른 진화를 연구하기 위해 정보 이론 및 열역학의 개념을 사용합니다.
교통망이나 송전망 등도 플로우 네트워크로 나타낼 수 있다. 이러한 물리 네트워크에서는 중간 노드로 유입되는 플로우와 거기서 유출되는 플로우는 항상 같다.
다중 상품 흐름 문제에서는 여러 소스와 싱크가 있으며, 주어진 소스에서 주어진 싱크로 흐를 다양한 "상품"이 있다. 예를 들어, 여러 공장에서 생산되어 동일한 수송 네트워크를 통해 여러 특정 고객에게 배송될 다양한 상품일 수 있다. 이는 각종 공장에서 다양한 제품이 생산되어, 다양한 고객에게 "같은 교통망"을 통해 전달되는 것과 유사하다.
5. 1. 이분 매칭(Bipartite Matching)
이분 그래프에서 최대 매칭을 찾는 문제는 최대 흐름 문제로 모델링할 수 있다.5. 2. 할당 문제(Assignment Problem)
작업자와 작업, 학생과 학교 등과 같이 최적의 할당을 찾는 문제는 최소 비용 흐름 문제로 모델링할 수 있다.5. 3. 교통 문제(Transportation Problem)
여러 공급지에서 여러 수요지로 상품을 최소 비용으로 운송하는 문제는 흐름 네트워크를 이용하여 해결할 수 있다. 이는 한국의 효율적인 물류 시스템 구축에도 활용될 수 있는 개념이다. 교통망이나 송전망 등도 플로우 네트워크로 나타낼 수 있다. 이러한 물리 네트워크에서는 중간 노드로 유입되는 플로우와 거기서 유출되는 플로우는 항상 같다.5. 4. 통신 네트워크
일련의 수도관을 네트워크에 맞추어 상상해 보십시오. 각 파이프는 특정 지름을 가지고 있어 특정 양의 물만 유지할 수 있습니다. 파이프가 만나는 곳에서는 해당 교차점에 들어오는 총 물의 양이 나가는 양과 같아야 합니다. 그렇지 않으면 물이 빨리 떨어지거나 물이 축적될 것입니다. 우리는 원천인 물 입구와 출구, 즉 싱크대가 있습니다. 그러면 흐름은 출구에서 나오는 총 물의 양이 일관되도록 물이 원천에서 싱크대로 가는 한 가지 가능한 방법이 될 것입니다. 직관적으로 네트워크의 총 흐름은 물이 출구에서 나오는 속도입니다.흐름은 운송 네트워크를 통한 사람 또는 자재와 전력 배전 시스템을 통한 전기에 관련될 수 있습니다. 이러한 모든 물리적 네트워크에서 중간 노드로 들어오는 흐름은 해당 노드에서 나가는 흐름과 같아야 합니다. 이 보존 제약 조건은 키르히호프의 전류 법칙과 동일합니다.
흐름 네트워크는 또한 생태학에서 응용 분야를 찾습니다. 흐름 네트워크는 먹이 사슬에서 서로 다른 유기체 간의 영양분과 에너지의 흐름을 고려할 때 자연스럽게 발생합니다. 이러한 네트워크와 관련된 수학적 문제는 유체 또는 교통 흐름 네트워크에서 발생하는 문제와는 매우 다릅니다. 로버트 울라노위츠 등이 개발한 생태계 네트워크 분석 분야는 이러한 네트워크의 시간 경과에 따른 진화를 연구하기 위해 정보 이론 및 열역학의 개념을 사용합니다.
5. 5. 전력망
일련의 수도관을 네트워크에 맞추어 상상해 보자. 각 파이프는 특정 지름을 가지고 있어 특정 양의 물만 유지할 수 있다. 파이프가 만나는 곳에서는 해당 교차점에 들어오는 총 물의 양이 나가는 양과 같아야 한다. 그렇지 않으면 물이 빨리 떨어지거나 물이 축적될 것이다. 우리는 원천인 물 입구와 출구, 즉 싱크대가 있다. 그러면 흐름은 출구에서 나오는 총 물의 양이 일관되도록 물이 원천에서 싱크대로 가는 한 가지 가능한 방법이 될 것이다. 직관적으로 네트워크의 총 흐름은 물이 출구에서 나오는 속도이다.흐름은 운송 네트워크를 통한 사람 또는 자재와 전력 배전 시스템을 통한 전기에 관련될 수 있다. 이러한 모든 물리적 네트워크에서 중간 노드로 들어오는 흐름은 해당 노드에서 나가는 흐름과 같아야 한다. 이 보존 제약 조건은 키르히호프의 전류 법칙과 동일하다.
교통망이나 송전망 등도 플로우 네트워크로 나타낼 수 있다. 이러한 물리 네트워크에서는 중간 노드로 유입되는 플로우와 거기서 유출되는 플로우는 항상 같다.
5. 6. 다중 상품 흐름 문제(Multi-Commodity Flow Problem)
다중 상품 흐름 문제에서는 여러 소스와 싱크가 있으며, 주어진 소스에서 주어진 싱크로 흐를 다양한 "상품"이 있다. 예를 들어, 여러 공장에서 생산되어 동일한 수송 네트워크를 통해 여러 특정 고객에게 배송될 다양한 상품일 수 있다. 이는 각종 공장에서 다양한 제품이 생산되어, 다양한 고객에게 "같은 교통망"을 통해 전달되는 것과 유사하다.6. 확장된 개념
흐름 네트워크에 대한 가장 단순하고 일반적인 문제로 최대 흐름 문제 즉, 주어진 그래프에 대해 시작점에서 종착점까지 가능한 최대 흐름을 구하는 문제가 있다. 최대 흐름을 구하는 알고리즘을 사용하면 흐름 네트워크로 모델링할 수 있는 다른 문제도 해결할 수 있다. 예를 들어, 2부 매칭, 할당 문제, 교통 문제 등이 있다.
다품종 흐름 문제에서는 시작점과 종착점이 각각 여러 개 있으며, 각각 고유한 품종이 흐름으로 유통된다. 이는 예를 들어 각종 공장에서 다양한 제품이 생산되어, 다양한 고객에게 "같은 교통망"을 통해 전달되는 것과 유사하다.
최소 비용 흐름 문제에서는 각 간선 에 소정의 비용 가 설정되어 있으며, 흐름 를 보내는 데 드는 비용은 로 표시된다. 목적은 소정의 흐름을 시작점에서 종착점으로 최소 비용으로 보내는 것이다.
순환 흐름 문제에서는 간선에 대해 하한 와 상한 이 주어진다. 각 간선에는 비용도 설정되어 있다. 종착점에서 시작점으로의 간선이 추가되어, 모든 노드에서 흐름 보존 법칙이 성립하도록 되어 있는 경우가 많다. 이 경우, 상한과 하한 사이에서 가능한 흐름의 총계를 구한다. 이름 그대로, 이 문제에서는 흐름이 네트워크 상을 순환한다.
이득이 있는 네트워크에서는 각 간선에 이득이 설정되어 있으며, 흐름 x가 이득 g의 간선을 통과하면 최종적으로 흐름이 gx가 된다.
6. 1. 순환 흐름 문제 (Circulation Problem)
순환 흐름 문제에서는 각 간선에 상한 외에 하한 이 주어진다. 각 간선에는 비용도 있다. 종종, 순환 문제에서 흐름 보존은 ''모든'' 노드에 대해 유지되며, 싱크에서 소스로의 연결이 있다. 이러한 방식으로, 와 로 총 흐름을 지시할 수 있다. 흐름은 네트워크를 통해 "순환"하므로 문제의 이름이 붙었다. 이름 그대로, 이 문제에서는 흐름이 네트워크 흐름 상을 순환하는 형태를 띤다.6. 2. 이득이 있는 네트워크 (Generalized Network)
이득이 있는 네트워크에서는 각 간선에 이득이 설정되어 있으며, 흐름 x가 이득 g의 간선을 통과하면 최종적으로 흐름이 gx가 된다.7. 알고리즘
8. 한국 사회에의 시사점
참조
[1]
간행물
Network flow algorithms
Stanford University CS Dept.
1989
[2]
서적
Network flows: theory, algorithms and applications
Prentice Hall
1993
[3]
서적
Algorithm design
https://www.worldcat[...]
Addison-Wesley
2011
[4]
문서
Supersource
supersource
DADS
[5]
문서
Supersink
supersink
DADS
[6]
논문
An algorithm for finding maximum flows in networks
https://eprints.utas[...]
2019-07-11
[7]
서적
Max flows in O(nm) time, or better
Association for Computing Machinery
2013-06-01
[8]
논문
Locating the source of diffusion in large-scale networks
http://www.pedropint[...]
2012-08-14
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com