에르되시-멩거 추측
에르되시-멩거 추측(Erdős–Menger conjecture)은 멩거의 정리가 무한 그래프를 유지하며, 그 맥락에서 그래프의 정점 또는 끝인 두 요소 사이의 최소 절단치에 적용된다.[1] 다음의 론 아하로니(Ron Aharoni)와 엘리 버거(Eli Berger)의 결과는 원래 에르되시 팔이 제안한 추측이었고, 증명되기 전에 에르되시-멩거 추측으로 알려졌다. 이것은 그래프가 유한할 때 멩거의 정리와 같다.
A와 B는 임의의 (무한한) 유향그래프(Digraph) G에서 정점 집합이다. 그런 다음 분할된 A-B 경로의 패밀리 P와 각 정점으로부터 정확히 하나의 P-A와P-B 경로를 구성하는 순서쌍이 존재한다.
같이 보기[편집]
참고[편집]
- ↑ Halin, R. (1974). "A note on Menger's theorem for infinite locally finite graphs". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 40: 111. doi:10.1007/BF02993589