멩거의 정리
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
멩거의 정리는 그래프의 연결성에 관한 정리로, 그래프의 연결도가 k일 필요충분조건은 임의의 두 정점 사이를 지나는 서로소인 경로가 k개 이상 존재하는 것이다. 이 정리는 변 연결성, 정점 연결성, 유향 그래프 등 다양한 그래프 유형에 적용되며, 최대 유량 최소 컷 정리, 쾨니그의 정리 등과 밀접한 관련이 있다. 또한, 무한 그래프로 확장될 수 있으며, 에르되시-멩거 추측으로 알려지기도 했다.
더 읽어볼만한 페이지
- 네트워크 이론 - 사회 연결망
사회 연결망 분석은 개인이나 집단 간의 관계를 분석하여 사회적 구조와 행동을 이해하는 학제 간 연구 방법론으로, 다양한 이론적 틀을 활용하여 네트워크 내 위치와 정보 접근의 중요성을 분석하며 여러 분야에서 활용된다. - 네트워크 이론 - 중심성
중심성은 그래프 이론에서 네트워크 내 노드의 중요성을 평가하기 위한 지표로, 차수 중심성, 근접 중심성 등 다양한 종류가 있으며 네트워크 흐름, 워크 구조 등 다양한 특징에 따라 분류된다. - 수학 정리 - 마스터 정리
마스터 정리는 분할 정복 알고리즘의 시간 복잡도 분석 도구로서, 점화식을 세 가지 경우로 나누어 재귀 알고리즘의 효율성을 파악하고, 다양한 정렬 및 일반 알고리즘 분석에 활용되지만, 특정 조건에서는 적용이 제한될 수 있습니다. - 수학 정리 - 베이즈 정리
베이즈 정리는 조건부 확률을 계산하는 방법으로, 사건 A가 일어났을 때 사건 B가 일어날 확률과 사건 B가 일어났을 때 사건 A가 일어날 확률 사이의 관계를 나타내며 사전 확률과 가능도를 이용하여 사후 확률을 계산하고 다양한 분야에서 활용된다. - 추측 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다. - 추측 - 버치-스위너턴다이어 추측
버치-스위너턴다이어 추측은 타원 곡선의 유리점 구조와 L-함수 특성 간의 관계를 추측하는 미해결 문제로, 타원 곡선의 랭크가 L-함수의 s=1에서의 영점 차수와 같다고 주장하며, 클레이 수학 연구소의 밀레니엄 문제 중 하나이다.
| 멩거의 정리 | |
|---|---|
| 멩거의 정리 | |
| 분야 | 그래프 이론 |
| 내용 | |
| 설명 | 그래프의 연결성에 대한 정리 |
| 관련 개념 | 정점 분리 집합 분리 정점 모든 경로 |
| 유형 | 그래프 이론 |
2. 멩거의 정리
멩거의 정리는 그래프의 연결성에 관한 정리로, 어떤 그래프의 연결도가 k일 필요충분조건은 그 그래프에서 임의의 두 정점 사이를 지나는 서로소인 경로가 k개 이상 존재하는 것이다.[3]
정점 집합 ''A, B ⊂ G''(반드시 분리될 필요는 없음)에 대해, ''AB-경로''는 시작 정점이 ''A''에 있고 최종 정점이 ''B''에 있으며 내부 정점이 ''A'' 또는 ''B''에 없는 ''G'' 내의 경로이다. 여기서 ''A ∩ B''에 단일 정점을 가지고 가장자리가 없는 경로를 허용한다. 크기가 ''k''인 ''AB-분리자''는 ''k''개의 정점 집합 ''S''(이는 ''A''와 ''B''와 교차할 수 있음)으로, ''G−S''가 ''AB''-경로를 포함하지 않는다. 크기가 ''k''인 ''AB-연결자''는 ''k''개의 정점 분리된 ''AB''-경로의 합집합이다.
'''정리:''' ''AB''-분리자의 최소 크기는 ''AB''-연결자의 최대 크기와 같다.
다시 말해, ''k''−1개의 정점이 ''A''를 ''B''로부터 분리하지 못한다면, ''A''에서 ''B''까지 ''k''개의 분리된 경로가 존재한다.
멩거의 정리는 무한 그래프에도 성립하며, 이 맥락에서 이 정리는 정점 또는 그래프의 끝점인 임의의 두 요소 사이의 최소 절단에 적용된다. 다음은 론 아하로니와 엘리 버거의 결과로, 원래 폴 에르되시가 제안한 추측이었으며, 증명되기 전에는 '''에르되시-멩거 추측'''으로 알려졌다. 그래프가 유한할 때는 멩거의 정리와 동등하다.
: ''A''와 ''B''를 (가능성이 있는 무한) 유향 그래프 ''G''의 정점 집합이라고 하자. 그러면 서로소인 ''A''-''B'' 경로의 집합 ''P''와 ''P''의 각 경로에서 정확히 하나의 정점으로 구성된 분리 집합이 존재한다.
2. 1. 변 연결성
'''변 연결성''' 버전의 멩거의 정리는 다음과 같다.: 유한한 무방향 그래프 ''G''와 서로 다른 두 개의 꼭짓점 ''x''와 ''y''가 있다고 하자. 그러면 ''x''와 ''y''에 대한 최소 변 절단 집합의 크기 (''x''와 ''y''를 분리하기 위해 제거해야 하는 최소 변의 수)는 ''x''에서 ''y''까지의 최대 개수의 상호 변-분리 경로의 개수와 같다.[3]
그래프 ''G''에 대한 의미는 다음과 같다.
: 그래프가 ''k''-변 연결인 것은 (''k''개 미만의 변을 제거한 후에도 연결된 상태를 유지한다) 모든 꼭짓점 쌍이 그 사이에 ''k''개의 변-분리 경로를 갖는 경우에만 해당한다.
2. 2. 정점 연결성
멩거의 정리에서 정점 연결도는 다음과 같다.: 유한 무향 그래프 ''G''와 인접하지 않은 두 정점 ''x'', ''y''가 주어졌을 때, ''x''와 ''y''에 대한 최소 정점 컷의 크기(''x''와 ''y''를 제거하면 ''x''와 ''y''를 연결 해제하는, ''x''와 ''y''와는 다른 최소 정점 수)는 ''x''에서 ''y''로 가는 내부적으로 서로소인 경로의 최대 개수와 같다.[3]
전체 그래프 ''G''에 대한 결과는 다음과 같다.
: 그래프가 ''k''-정점 연결 그래프(''k''개 이상의 정점을 가지고 있고, ''k''개 미만의 정점을 제거한 후에도 연결되어 있음)이기 위한 필요충분 조건은 모든 정점 쌍 사이에 최소 ''k''개의 내부적으로 서로소인 경로가 있는 것이다.[3]
2. 3. 유향 그래프
이러한 명제는 간선 버전과 정점 버전 모두에서 유향 그래프에서도 참이다(유향 경로를 고려할 때).3. 증명
멩거의 정리는 그래프 연결성에 관한 것으로, 어떤 그래프의 연결도가 k이면 그 그래프에서 임의의 두 정점 사이를 지나는 서로소인 경로가 k개 이상 존재한다는 내용이다.[3]
멩거의 정리는 귀납법, 최대 유량 최소 컷 정리, 쾨니그의 정리 등을 이용하여 증명할 수 있다.
3. 1. 귀납법을 이용한 증명
멩거의 정리는 그래프의 연결성에 관한 것으로, 어떤 그래프의 연결도가 k일 필요충분조건은 그 그래프에서 임의의 두 정점 사이를 지나는 ‘서로소’인 경로가 k개 이상 존재하는 것이다.[3] 귀납법을 이용한 증명에서는 더 일반적인 명제를 고려하며, 퇴화된 경우를 포함하는 정의를 사용한다.
무방향 그래프에 대한 증명은 방향 그래프 또는 다중 그래프에도 변경 없이 적용되며, 이때 '경로'는 방향 경로를 의미한다.
정점 집합 ''A,B ⊂ G''(반드시 분리될 필요는 없음)에 대해, ''AB-경로''는 시작 정점이 ''A''에 있고 최종 정점이 ''B''에 있으며 내부 정점이 ''A'' 또는 ''B''에 없는 ''G'' 내의 경로이다. ''A ∩ B''에 단일 정점을 가지고 가장자리가 없는 경로도 허용한다. 크기가 ''k''인 ''AB-분리자''는 ''k''개의 정점 집합 ''S''(이는 ''A''와 ''B''와 교차할 수 있음)로, ''G−S''가 ''AB''-경로를 포함하지 않는다. 크기가 ''k''인 ''AB-연결자''는 ''k''개의 정점 분리된 ''AB''-경로의 합집합이다.
: '''정리:''' ''AB''-분리자의 최소 크기는 ''AB''-연결자의 최대 크기와 같다.
다시 말해, ''k''−1개의 정점이 ''A''를 ''B''로부터 분리하지 못한다면, ''A''에서 ''B''까지 ''k''개의 분리된 경로가 존재한다. 이 변형은 정점 연결성 명제를 암시한다. 즉, 이전 절의 ''x,y ∈ G''에 대해, 현재 정리를 ''G''−{''x,y''}에 ''A = N(x)'', ''B = N(y)''로 적용한다. 여기서 N(x), N(y)는 ''x,y''의 인접 정점이다. 그러면 ''x''와 ''y''를 분리하는 정점 집합은 ''AB''-분리자와 동일하며, 독립적인 ''xy''-경로 집합에서 끝점을 제거하면 ''AB''-연결자를 얻는다.
''정리의 증명:''[1] ''G''의 가장자리 수를 기준으로 귀납법을 수행한다. 가장자리가 없는 ''G''에 대해, 최소 ''AB''-분리자는 ''A ∩ B''이며, 이는 단일 정점 경로로 구성된 ''AB''-연결자 자체이다.
가장자리 ''e''를 가진 ''G''의 경우, 귀납법에 의해 정리가 ''G−e''에 대해 성립한다고 가정할 수 있다. 만약 ''G−e''가 크기가 ''k''인 최소 ''AB''-분리자를 가지면, ''G−e''에 크기가 ''k''인 ''AB''-연결자가 있고, 따라서 ''G''에도 있다.
그렇지 않으면, ''S''를 크기가 ''k-1''인 ''G−e''의 ''AB''-분리자라고 하자. ''G''의 모든 ''AB''-경로는 ''S''의 정점 또는 가장자리 ''e''를 포함한다. ''S''의 크기는 ''k-1''이어야 한다. 왜냐하면 만약 작다면, ''S''와 ''e''의 어느 한 끝점을 함께 사용하면 ''G''의 더 나은 ''AB''-분리자가 될 것이기 때문이다. ''G−S''에는 ''e''를 통과하는 ''AB''-경로가 있다. 왜냐하면 ''S''만으로는 ''G''의 ''AB''-분리자가 되기에는 너무 작기 때문이다. ''v1''을 이러한 경로에서 ''e''의 앞쪽 정점, ''v2''를 뒤쪽 정점이라고 하자. 그러면 ''v1''은 ''G−S−e''에서 ''A''로부터 도달 가능하지만 ''B''로부터는 도달 불가능하며, ''v2''는 ''B''로부터 도달 가능하지만 ''A''로부터는 도달 불가능하다.
이제 ''S1 = S ∪ {v1}''라고 하고, ''G−e''에서 최소 ''AS1''-분리자 ''T''를 고려하자. ''v2''는 ''G−S1''에서 ''A''로부터 도달 불가능하므로, ''T''는 ''G''에서도 ''AS1''-분리자이다. 그러면 ''T''는 ''G''에서도 ''AB''-분리자이다(모든 ''AB''-경로는 ''S1''과 교차하기 때문). 따라서 크기는 최소 ''k''이다. 귀납법에 의해, ''G−e''는 크기가 ''k''인 ''AS1''-연결자 ''C1''을 포함한다. 그 크기로 인해, 그 경로의 끝점은 정확히 ''S1''이어야 한다.
마찬가지로, ''S2 = S ∪ {v2}''라고 하면, 최소 ''S2B''-분리자의 크기는 ''k''이며, 시작점이 정확히 ''S2''인 경로를 가진 크기가 ''k''인 ''S2B''-연결자 ''C2''가 있다.
또한, ''S1''은 ''G''를 분리하므로, ''C1''의 모든 경로는 ''C2''의 모든 경로와 내부적으로 분리되어 있으며, 경로를 연결하여 ''G''에서 크기가 ''k''인 ''AB''-연결자를 정의할 수 있다(''S''를 통과하는 ''k−1''개의 경로와 ''e=v1v2''를 통과하는 한 개의 경로).
3. 2. 최대 유량 최소 컷 정리를 이용한 증명
멩거의 정리의 방향성 있는 간선 버전은 최대 유량 최소 컷 정리에서 파생된다.[2] 최대 유량 최소 컷 정리의 증명은 종종 최대 유량 알고리즘의 정확성 증명을 이용한다. 또한, (강한) 쌍대성 정리의 특수한 경우이다.[3]유한 유향 그래프 ''G''의 정점 집합을 ''A''와 ''B''라고 할 때, 서로소인 ''AB'' 경로의 집합 ''P''와 ''P''의 각 경로에서 정확히 하나의 정점으로 구성된 ''AB''-분리 집합이 존재한다. 이 버전의 정리는 쾨니그의 정리에서 쉽게 파생된다. 이분 그래프에서 최소 크기의 커버는 최대 크기의 매칭과 같다.
쾨니그의 정리를 적용하기 위해, 원래 유향 그래프 ''D''의 모든 정점 ''v''를 두 개의 정점 ''v' '', ''v''"로 바꾸고, 모든 간선 ''uv''를 간선 ''u'v''"로 바꾼다. ''A'' 또는 ''B''에 속하지 않는 모든 정점 ''v''에 대해 간선 ''v'v''"를 포함한다. 이렇게 만들어진 이분 그래프는 한쪽 면은 정점 ''v' ''로, 다른 쪽 면은 정점 ''v''"로 구성된다.
쾨니그의 정리를 적용하면 동일한 크기의 매칭 ''M''과 커버 ''C''를 얻는다. ''M''의 각 간선의 정확히 하나의 끝점은 ''C''에 있다. ''A''에 있는 모든 ''a''에 대해 모든 정점 ''a''"와 ''B''에 있는 모든 ''b''에 대해 모든 정점 ''b' ''를 ''C''에 추가한다. ''P''를 ''u'v''"가 ''M''에 속하는 ''D''의 간선 ''uv''로 구성된 모든 ''AB'' 경로의 집합이라고 정의한다. 원래 그래프에서 ''Q''가 ''v' ''와 ''v''"가 모두 ''C''에 속하는 모든 정점 ''v''로 구성되도록 한다. ''Q''는 ''AB''-분리 집합이고, 집합 ''P''의 모든 경로는 ''Q''에서 정확히 하나의 정점을 포함하며, ''Q''의 모든 정점은 ''P''의 경로에 놓이게 된다.[2]
3. 3. 쾨니그의 정리를 이용한 증명
쾨니그의 정리를 이용해 멩거의 정리를 증명하는 방법은 다음과 같다. 먼저, 유한 유향 그래프 ''G''의 정점 집합을 ''A''와 ''B'' 두 그룹으로 나눈다. 이때, 서로소인 ''AB'' 경로 집합 ''P''와, ''P''의 각 경로마다 정확히 하나의 정점을 포함하는 ''AB''-분리 집합이 존재함을 보인다.이 증명은 이분 그래프에서 최소 크기의 커버가 최대 크기의 매칭과 같다는 쾨니그의 정리를 이용한다. 증명 과정은 다음과 같다.
1. 주어진 유향 그래프 ''D''의 모든 정점 ''v''를 두 개의 정점 ''v' ''와 ''v
2. 모든 간선 ''uv''를 간선 ''u'v
3. ''A'' 또는 ''B''에 속하지 않는 모든 정점 ''v''에 대해 간선 ''v'v
4. 이렇게 하면 한쪽은 정점 ''v' ''로, 다른 쪽은 정점 ''v
이제 쾨니그의 정리를 적용하여 동일한 크기의 매칭 ''M''과 커버 ''C''를 얻는다. ''M''의 각 간선은 정확히 하나의 끝점만 ''C''에 속한다.
다음으로, ''A''의 모든 원소 ''a''에 대해 모든 정점 ''a
마지막으로, 원래 그래프에서 ''Q''가 ''v' ''와 ''v
4. 무한 그래프로의 확장
멩거의 정리는 무한 그래프에도 성립하며, 이 맥락에서 이 정리는 정점 또는 그래프의 끝점인 임의의 두 요소 사이의 최소 절단에 적용된다.[1] 론 아하로니와 엘리 버거의 결과에 따르면, 원래 폴 에르되시가 제안한 추측으로 증명되기 전에는 '''에르되시-멩거 추측'''으로 알려졌다. 그래프가 유한할 때는 멩거의 정리와 동등하다.
: ''A''와 ''B''를 (가능성이 있는 무한) 유향 그래프 ''G''의 정점 집합이라고 하자. 그러면 서로소인 ''A''-''B'' 경로의 집합 ''P''와 ''P''의 각 경로에서 정확히 하나의 정점으로 구성된 분리 집합이 존재한다.
참조
[1]
논문
Short proof of Menger's theorem
[2]
논문
Menger's theorem for graphs containing no infinite paths
[3]
문서
우리말샘
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com