에드먼즈 알고리즘

그래프 및 트리쉬 알고리즘
α–β A* B* 역추적 빔 벨먼-포드 베스트 퍼스트 양방향 보르슈프카 분기 & 바운드 BFS 대영 박물관 D* DFS 디크스트라 에드먼즈 플로이드-워셜 프린지 검색 힐클림빙 IDA* 반복적 심화 존슨 점프 포인트 크루스칼 사전 BFS LPA* 프라이머리 SMA*
목록
그래프 알고리즘 검색 알고리즘 그래프 알고리즘 목록
관련 항목
동적 프로그래밍 그래프 통과 나무횡단 검색 게임 그래프 컬러링
v t

그래프 이론에서, 에드몬드의 알고리즘 또는 Chu-Liu/Edmonds의 알고리즘은 최소 중량의 스패닝 적분(최적 분지라고도 함)을 찾기 위한 알고리즘이다.그것은 최소 스패닝 트리 문제의 지시된 아날로그다.이 알고리즘은 처음에는 융진추와 쩡훙류(1965)가 독자적으로 제안했고, 다음에는 잭 에드먼즈(1967)가 제안했다.

알고리즘.

설명

The algorithm takes as input a directed graph ${\displaystyle D=\langle V,E\rangle }$ where ${\displaystyle V}$ is the set of nodes and ${\displaystyle E}$ is the set of directed edges, a distinguished vertex ${\displaystyle r\in V}$ called the root, and a real-valued weight ${\displaysty$$le w(e)}$ for each edge ${\displaystyle e\in E}$. It returns a spanning arborescence ${\displaystyle A}$ rooted at ${\displaystyle r}$ of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, ${\displaystyle w(A)=\sum _{e\in A}{w(e)}}$.

알고리즘은 재귀적 설명을 가지고 있다.let $f{\displaystyle }$( ${\displaystyle D}$, ${\displaystyle r}$, ${\displaystyle w}$) ${\displaystyle f(D,r,w)}$은 최소 중량의 $r$ ${\displaystyle r}$에 뿌리를 둔 스패닝 아르보렌스를 반환하는 함수를 나타낸다$$.우리는 우선 대상이 $r{\displaystyle }$ ${\displaystyle r}$인 $E{\displaystyle }$ ${\displaystyle E}$에서 모든 에지를 제거한다$.$ 우리는 또한 이 평행 에지의 무게의 최소와 동일한 무게의 단일 에지로 평행 에지 세트(동일한 방향의 정점 쌍 사이의 에지)를 교체할 수 있다.

이제 루트가 아닌$$ 각 노드 $v{\displaystyle }$ ${\displaystyle v}$에 대해 가장 낮은 중량의 $v$ ${\displaystyle v}$에 들어오는 가장자리를 찾으십시오(임의적으로 타이가 끊어진 경우).Denote the source of this edge by ${\displaystyle \pi (v)}$. If the set of edges ${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}$ does not contain any cycles, then ${\displaystyle f(D,r,w)=P}$.

그렇지 않으면 $P{\displaystyle }$ ${\displaystyle P}$에 적어도 하나의 사이클이 포함되어$$ 있다.Arbitrarily choose one of these cycles and call it ${\displaystyle C}$. We now define a new weighted directed graph ${\displaystyle D^{\prime }=\langle V^{\prime },E^{\prime }\rangle }$ in which the cycle ${\displaystyle C}$ is "contracted" into one node as follows:

$V{\displaystyle {}^{}}$ $′{\$의 $노드$는 C ${\displaystyle C$}에$$ $없는{\displaystyle }$ V$${\$displaystyle V}$의 노드일$$ 뿐 ${\displaystyle {아니라}_{}}$ V$${\$displaystyle v_{C}}$로 표시된 새 노드일 것이다$.$

• If ${\displaystyle (u,v)}$ is an edge in ${\displaystyle E}$ with ${\displaystyle u\notin C}$ and ${\displaystyle v\in C}$ (an edge coming into the cycle), then include in ${\displaystyle E^{\prime }}$ a new edge ${\displaystyle e=(u,v_{C})}$, and define ${\displaystyle w^{}}$${\displaystyle {\mathrm{\prime }}^{}}$( e${\displaystyle }$)${\displaystyle }$= w${\displaystyle }$( ${\displaystyle u}$, v${\displaystyle }$)${\displaystyle }$- ${\displaystyle w}$( ${\displaystyle \pi }$(${\displaystyle v}$)${\displaystyle }$, v${\displaystyle }$) ${\displaystyle$ w$^{\prime }(e)=w(u,v)-w(\pi (v),v$
• If ${\displaystyle (u,v)}$ is an edge in ${\displaystyle E}$ with ${\displaystyle u\in C}$ and ${\displaystyle v\notin C}$ (an edge going away from the cycle), then include in ${\displaystyle E^{\prime }}$ a new edge ${\displaystyle e=(v_{C},v)}$, and define $$${\displaystyle w^{}}$ ${\displaystyle {\prime \mathrm{}}^{}}$( ${\displaystyle e}$)${\displaystyle }$= w (${\displaystyle u}$, v${\displaystyle }$) ${\displaystyle w^{\premy }(e)=w(u,v)}$.
• If ${\displaystyle (u,v)}$ is an edge in ${\displaystyle E}$ with ${\displaystyle u\notin C}$ and ${\displaystyle v\notin C}$ (an edge unrelated to the cycle), then include in ${\displaystyle E^{\prime }}$ a new edge ${\displaystyle e=(u,v)}$, and define ${\displaystyle w^{\mathrm{\prime }}(}$${\displaystyle e}$)${\displaystyle }$= ${\displaystyle w}$ (${\displaystyle u}$, ${\displaystyle v}$) ${\displaystyle w^{\premy }(e)=w(u,v$

$′{\$ $\}\}$의 각 에지에 대해 $우리$는 E$$ ${\displaystyle E}$의 에지가 어느 에지와 일치하는지 기억한다.

Now find a minimum spanning arborescence ${\displaystyle A^{\prime }}$ of ${\displaystyle D^{\prime }}$ using a call to ${\displaystyle f(D^{\prime },r,w^{\prime })}$. Since ${\displaystyle A^{\prime }}$ is a spanning arborescence, each vertex has exactly one incoming edge.Let ${\displaystyle (u,v_{C})}$ be the unique incoming edge to ${\displaystyle v_{C}}$ in ${\displaystyle A^{\prime }}$. This edge corresponds to an edge ${\displaystyle (u,v)\in E}$ with ${\displaystyle v\in C}$. Remove the edge ${\displaystyle$$C{\displaystyle }$ ${\displaystyle C}$에서 $(\pi (v),v)}$이(가) 사이클을 중단함$.$$C{\displaystyle }$ ${\displaystyle C}$에 남아 있는 각 가장자리를 표시하십시오$.$ $A{\displaystyle {}^{}}$ ${\displaystyle {\prime \mathrm{}}^{}}$ ${\$}에 해당하는 가장자리를 $E{\displaystyle }$ ${\displaystyle$ $E$$}$에 표시하십시오$.$ $이제{\displaystyle }$ f(${\displaystyle D}$, ${\displaystyle r}$, w )${\displaysty$ f$(D,r,w)$를 표시$$ 에지 집합으로 정의하여 최소 스패턴을 구성한다.

Observe that ${\displaystyle f(D,r,w)}$ is defined in terms of ${\displaystyle f(D^{\prime },r,w^{\prime })}$, with ${\displaystyle D^{\prime }}$ having strictly fewer vertices than ${\displaystyle D}$. Finding ${\displaystyle f(D,r,w)}$ for a single-vertex 그래프는 사소한 것이므로($D{\displaystyle }$ ${\displaystyle D}$ 그 자체일$$ 뿐), 재귀 알고리즘은 종료를 보장한다.

러닝타임

이 알고리즘의 실행 $시간$은 O${\displaystyle }$( ${\displaystyle E}$ V${\displaystyle }$) ${\displaystyle$ O$(EV)}$이다$.$ 로버트 타르잔으로 인한 알고리즘의 구현 속도가 희소성 그래프의 $경우$ O${\displaystyle }$( E ${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle V}$) ${\$$displaystyle O$$E\log V)},$ 밀도 그래프의 $경우$ O $(V^{2}).$이것은 비방향 최소 스패닝 트리에 대한 Prim의 알고리즘만큼 빠르다.1986년 가보우, 갈릴, 스펜서, 타르잔은 가동 $시간{\displaystyle }$ O${\displaystyle }$(${\displaystyle E}$+ V ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ V$){\displaystyle$ O $(E+V\log V)}$을(를) 사용하여 더 빠른 구현을 실현했다$.$

참조

• Chu, Y. J.; Liu, T. H. (1965), "On the Shortest Arborescence of a Directed Graph", Science Sinica, 14: 1396–1400
• Edmonds, J. (1967), "Optimum Branchings", Journal of Research of the National Bureau of Standards Section B, 71B (4): 233–240, doi:10.6028/jres.071b.032
• Tarjan, R. E. (1977), "Finding Optimum Branchings", Networks, 7: 25–35, doi:10.1002/net.3230070103
• Camerini, P.M.; Fratta, L.; Maffioli, F. (1979), "A note on finding optimum branchings", Networks, 9 (4): 309–312, doi:10.1002/net.3230090403
• Gibbons, Alan (1985), Algorithmic Graph Theory, Cambridge University press, ISBN 0-521-28881-9
• Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986), "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs", Combinatorica, 6 (2): 109–122, doi:10.1007/bf02579168, S2CID 35618095

외부 링크

• Edmonds의 알고리즘(edmonds-alg ) – C++로 작성되고 MIT 라이선스에 따라 라이센스가 부여된 Edmonds의 알고리즘의 구현.이 출처는 촘촘한 그래프를 위해 타르잔의 구현을 이용하고 있다.
• 네트워크X는 BSD에 따라 배포된 파이톤 라이브러리로서 에드몬드의 알고리즘을 구현하고 있다.