멩거의 정리
그래프 이론의 수학적 분야인 멩거의 정리에서는 유한 그래프에서 최소 분할 집합의 크기가 정점 쌍 사이에서 발견될 수 있는 최대 분리 경로 수와 동일하다고 한다. 1927년에 카를 멩거(Karl Menger)가 증명한 것으로 그래프의 연결성은 연결 그래프를 특징짓는다. 이것은 최대흐름 최소분할 정리에 의해 일반화되며, 이는 가중 그래프로 선형 프로그램에 대한 강한 쌍대성 정리의 특별한 경우이다.
이러한 멩거의 정리를 무한한 그래프로 확대하여 추측한다면 이것은 에르되시-멩거 추측이라고 한다.
멩거의 정리[편집]
멩거의 정리는 그래프의 연결성에 관한 정리로 어떤 그래프의 연결도가 케이(k)일 필요충분조건은 그 그래프에서 임의의 두 정점 사이를 지나는 ‘서로소’인 경로가 k 개 이상 존재하는 것을 의미한다.[1]