멩거 정리

Menger's theorem

그래프 이론의 수학적 규율에서, Menger의 정리는 유한 그래프에서, 최소 절단 세트의 크기가 정점 쌍 사이에서 찾을 수 있는 최대 분리 경로 수와 동일하다고 말한다. 1927년 칼 멩거에 의해 증명된, 그것은 그래프의 연결성을 특징으로 한다. 최대 흐름 최소 절삭 정리(max-flow min-cut organization)에 의해 일반화되는데, 가중치, 에지 버전이며, 다시 선형 프로그램에 대한 강한 이중성 정리(duality organization)의 특수한 경우다.

에지 연결

멩거의 정리의 가장자리 연결성 버전은 다음과 같다.

G는 유한한 방향의 그래프와 x와 y의 뚜렷한 두 정점이 되게 하라. 그런 다음 x와 y에 대한 최소 에지 절단 크기(제거로 x와 y가 분리되는 최소 에지 수)는 x에서 y까지 쌍으로 구성된 에지 독립 경로의 최대 수와 동일하다.
모든 쌍으로 확장: 모든 꼭지점 쌍 사이에 k 에지 분리 경로가 있는 경우에만 그래프가 k-엣지 연결됨(k 에지 미만을 제거한 후에도 연결됨)

정점 연결

멩거의 정점에 대한 연결성 진술은 다음과 같다.

G를 한정된 비방향 그래프와 x와 y의 비인접 정점 두 개로 한다. 그런 다음 x와 y에 대해 절단된 최소 꼭지점 크기(제거가 x와 y로 분리되는 x와 y와 구별되는 정점 수)는 x에서 y까지의 쌍방향 내부 정점 분리 경로의 최대 수와 동일하다.
모든 쌍으로 확장: 그래프는 k-vertex 연결된다(k 정점 이상이며, 정점 이하를 제거한 후에도 연결 상태를 유지함). 정점 쌍 사이에 적어도 k개의 내부 정점 분리 경로가 있는 경우에만 그래프가 연결된다.

(가장자리 및 꼭지점 버전 모두에서) 이러한 모든 문장은 지시된 그래프에서 참으로 유지된다(지시된 경로를 고려할 때).

단증

대부분의 직접적인 증거들은 그것을 유도함으로써 증명할 수 있도록 더 일반적인 진술을 고려한다. 일부 퇴폐사례가 포함된 정의를 이용하는 것도 편리하다. 다음 비방향 그래프에 대한 증거는 지시된 그래프 또는 다중 그래프에 대해 변경 없이 작동한다. 단, 우리가 지시된 경로를 평균한 경로로 이동한다면 말이다.

정점 A,B ⊂ G(필수적으로 분리된 것은 아님)의 경우, AB 경로는 시작 정점이 A에 있고, 최종 정점이 B에 있고, 내부 정점이 A 또는 B에 없는 경로다. 우리는 A b B에 하나의 꼭지점이 있고 가장자리가 0인 경로를 허용한다. 크기 k의 AB-분리기는 G-S가 AB 경로를 포함하지 않도록 k 정점(A와 B를 교차할 수 있음)의 집합 S이다. k 크기의 AB 커넥터는 k 꼭지점 분리형 AB 경로의 결합이다.

정리: AB-분리기의 최소 크기는 AB-커넥터의 최대 크기와 동일하다.

즉, k-1 정점이 없으면 A와 B 사이의 K 분리 경로가 존재하는 것이다. 이 변형은 위의 꼭지점 연결성 문을 암시한다. 이전 절의 x,y g G에 대해서는 현재 정리를 A = N(x), B = N(y)로, x,y의 인접 정점인 G-{x,y}에 적용한다. 그러면 x와 y를 분리하는 정점 집합은 AB-분리기와 같은 것이며, 독립된 xy-path 집합에서 끝 정점을 제거하면 AB-커넥터가 된다.

정리 증명:[1] G 단위의 가장자리 수에 대한 유도. 에지가 없는 G의 경우 최소 AB-분리기는 A ∩ B이며, 그 자체가 단일 버텍스 경로로 구성된 AB-커넥터다.

엣지 e를 가진 G에 대해, 우리는 유도를 통해 Organis가 G-e를 위해 보유한다고 가정할 수 있다. G-e에 k 크기의 최소 AB 분리기가 있는 경우, G-e에 k 크기의 AB 커넥터가 있고, 따라서 G에 k 크기의 AB 커넥터가 있다.

증거에 대한 삽화.

그렇지 않으면, G의 모든 AB 경로에 S 또는 에지 e의 꼭지점이 포함되도록 S를 K보다 작은 크기의 G-e의 AB-분리기로 한다. S의 크기는 k-1이어야 하는데, 만약 그것이 더 작았다면, e의 양쪽 끝점과 함께 S가 G의 더 나은 AB-분리기가 될 것이기 때문이다. G-S에는 AB-path to e가 있는데, S만 해도 G의 AB-분리기가 되기에는 너무 작기 때문이다. v는1 그보다 먼저, v는 그러한2 경로에서 e의 나중 꼭지점이 되도록 하자. 그러면 V는1 A에서 도달할 수 있지만 G-S-e에서는 B에서 도달할 수 없고, V는2 B에서 도달할 수 있지만 A에서 도달할 수 없다.

이제 S1 = S ∪ {v1}을(를) 두고 G-e에서 최소 AS 분리자1 T를 고려한다. G-S의1 경우 A로부터 v에2 도달할 수 없기 때문에, T는 G의 AS 분리기도1 하다. 그러면 T도 G(모든 AB 경로가 S와1 교차하기 때문에)의 AB-분리기가 된다. 그러므로 그것은 적어도 k의 크기를 가지고 있다. 유도에 의해 G-e는 크기 k의 AS-커넥터1 C를1 포함한다. 크기 때문에, 그 안에 있는 경로의 끝점은 정확히1 S여야 한다.

마찬가지로 S2 = S ∪ {v2}, 최소 SB-분리기는2 k 크기를 가지며, 시작점이2 정확히 S인 경로를2 가진 k 크기의2 SB-커넥터 C가 있다.

나아가 S가1 G를 분리하기 때문에 C의1 모든 경로가 C의2 모든 경로에서 내부적으로 분리되며, 우리는 경로(S를 통과하는 k-1 경로와 e=vv를12 통과하는 하나의 경로)를 연결함으로써 G의 크기 k의 AB-커넥터를 정의할 수 있다. Q.E.D.

기타 교정쇄

정리의 지시된 에지 버전은 쉽게 다른 버전을 암시한다. 방향 그래프 정점 버전을 유추하려면 각 정점 v를 정점 v1(v2)로 분할하면 충분하며, 모든 입력 에지가 v로1 가고, 모든 송신 에지가2 v에서 v로 가고, 추가1 에지가 v에서 v로2 된다. 정리의 지시된 버전은 즉시 비방향 버전을 암시한다. 즉, 비방향 그래프의 각 가장자리를 한 쌍의 지시된 가장자리(디건)로 교체하기에 충분하다.

지시된 에지 버전은 가중 변종인 최대 흐름 최소 절삭 정리로부터 따르게 된다. 그것의 증거는 종종 최대 흐름 알고리즘에 대한 정확성 증명이다. 선형 프로그램을 위한 여전히 더 일반적(강력한) 이중성 정리의 특수한 경우이기도 하다.

유한 digraps의 경우 위의 공식과 동등한 공식은 다음과 같다.

A와 B를 유한한 digraph G의 정점 집합으로 한다. 그 다음, 분리된 AB 경로의 패밀리 P와 P의 각 경로에서 정확히 하나의 꼭지점으로 구성된 AB 분리 세트가 존재한다.

이 버전에서 정리는 쾨니히의 정리로부터 꽤 쉽게 따른다: 초당적 그래프에서 표지의 최소 크기는 일치의 최대 크기와 같다.

이 작업은 다음과 같이 수행된다: 원래 diggraph D의 모든 꼭지점을 v' , v'로 두 개의 꼭지점 v' , v'로 교체하고, 모든 가장자리 uv''로 교체한다.' 이로 인해 한쪽은 정점 v' 로 구성되고 다른 한쪽은 정점 v'로 구성된 초당적 그래프가 생성된다.

쾨니히의 정리를 적용하면 일치하는 M과 같은 크기의 커버 C를 얻는다. 특히 M의 각 가장자리의 끝점은 정확히 C에 있다. A의 경우 C에 모든 정점 a'를 추가하고 B의 경우 모든 정점 b' 를 추가한다. P는 'u'v'가 M에 속하도록 D의 엣지 uv로 구성된 모든 AB 경로의 집합이 되도록 한다. 원래 그래프의 Q는 v'와 v'가 모두 C에 속하도록 모든 정점 v로 구성된다. Q는 AB 분리 집합이고, 패밀리 P의 모든 경로에는 Q로부터 정확히 하나의 꼭지점이 있으며, Q의 모든 꼭지점은 원하는 대로 P로부터의 경로에 놓여 있음을 확인하는 것은 간단하다.[2]

무한 그래프

Menger의 정리는 무한 그래프를 유지하며, 그러한 맥락에서 그래프의 정점이나 끝인 두 원소 사이의 최소 절단에 적용된다(Halin 1974). 론 아하로니와 엘리 버거의 다음 결과는 원래 폴 에르드스가 제안한 추측이었고, 증명되기 전에는 에르드-멘거 추측으로 알려져 있었다. 그래프가 유한할 때 멩거의 정리와 맞먹는다.

A와 B를 (아마도 무한정) digraph G의 정점 집합으로 한다. 그 다음, 분리 A-B 경로의 패밀리 P와 P의 각 경로에서 정확히 하나의 꼭지점으로 구성된 분리 세트가 존재한다.

참고 항목

참조

  1. ^ F. 괴링(Göring), 멩거의 정리, 이산수학 219(2000) 295-296).
  2. ^ Aharoni, Ron (1983). "Menger's Theorem for Graphs Containing no Infinite Paths". European Journal of Combinatorics. 4 (3): 201–4. doi:10.1016/S0195-6698(83)80012-2.

추가 읽기

외부 링크