투테 정리

그래프 이론의 수학적인 학문에서, 윌리엄 토마스 투테의 이름을 딴 투테 정리는 완벽한 일치를 가진 유한한 그래프의 특성화다.홀의 결혼 정리를 초당적 그래프에서 임의적 그래프로 일반화한 것이다.^{[clarification needed]}투테-베르게 공식의 특별한 경우다.

직감

우리의 목표는 완벽한 일치가 없는 모든 그래프를 특징짓는 것이다.완벽한 일치가 없는 그래프의 가장 명백한 사례로 시작합시다: 정점 수가 홀수인 그래프.그러한 그래프에서 어떤 일치도 적어도 하나 이상의 일치하지 않는 꼭지점을 남기므로 완벽할 수는 없다.

약간 더 일반적인 경우는 하나 이상의 성분에 정점 수가 홀수인(정점 수가 짝수인 경우에도)가 있는 연결되지 않은 그래프다.이러한 구성 요소를 홀수 구성 요소라고 부르자.어떤 일치에서, 각 꼭지점은 동일한 구성요소의 정점과만 일치시킬 수 있다.따라서 어떤 짝짓기라도 모든 홀수 성분에 적어도 하나 이상의 일치하지 않는 꼭지점을 남기므로 완벽할 수는 없다.

다음으로, G에서 정점 u와 인접 에지를 제거하면 나머지 그래프( $G$ - $u$ 로 표시됨)에 2개 이상의 홀수 성분이 있도록 정점 u가 있는 그래프 G를 고려하십시오.위와 같이 모든 홀수 구성 요소에서 동일한 구성 요소의 다른 정점과 일치하지 않는 정점 하나 이상을 남긴다.그런 꼭지점은 오직 u와 일치할 수 있을 뿐이다.그러나 일치하지 않는 정점이 두 개 이상 있고, 그 중 하나만 u와 일치시킬 수 있기 때문에, 적어도 다른 정점 하나는 일치하지 않는 상태로 남아 있기 때문에 일치되는 것이 완벽하지는 않다.

$마지막$ 으로, 정점 U의 정점과 정점에 인접한 모든 가장자리를 G에서 제거하면 나머지 그래프( $G$ - $U$ 로 표시된)가 U $이상$ 성분을 가지도록 정점 $U$ 의 세트가 있는 그래프 G를 고려하십시오.위에서 설명한 것처럼, 일치하는 모든 구성 요소는 모든 홀수 구성 요소에서 적어도 하나 이상의 일치하지 않는 정점을 남기며, $U$ 의 정점에만 일치시킬 수 있다. 그러나 $U$ 에는 이 모든 일치하지 않는 정점들에 대한 정점이 충분하지 않기 때문에 일치되는 정점이 완벽하지 않다.

우리는 필요한 조건에 도달했다: 만약 G가 완벽하게 일치한다면, G의 모든 꼭지점 $부분집합$ U에 대해 G - $U$ $그래프$ 에는 $대부분$ 의 U 홀수 성분이 있다.

투테의 정리는 이 조건이 완벽한 매칭의 존재에 필요하면서도 충분하다고 말한다.

투테의 정리

$G =$ ( $V,$ $E)$ 그래프는 $V$ 의 모든 부분 집합 $U$ 에 대해 하위 그래프 $G$ - $U$ 가 최대 $U$ 홀수 구성 요소(정점 수가 홀수인 연결 구성 요소)를 갖는 경우에만 완벽하게 일치한다.^[1]

증명

먼저 조건을 작성한다.

{\displaystyle(*)\qquad \ for all U\subseteq V,\quad idd(G-U)\leq U }

여기서 $odd(X)$ $odd(X)$ ( $odd(X)$ ) $홀수(X)$ 는 X $X$ 에 의해 유도된 서브그래프의 홀수 성분 수를 나타낸다 $odd(X)$ $X$

필요성(필수): 완벽하게 $일치$ 하는 그래프 G를 생각해 보십시오. $U$ 를 $V$ 의 임의의 하위 집합이 되게 하라.U $삭제$ . $G$ - $U$ 에서 $C$ 를 임의의 홀수 구성요소로 한다. $G$ 가 완벽하게 일치했으므로 $C$ 에서 적어도 하나의 꼭지점이 $U$ 의 꼭지점과 일치해야 한다. 따라서, 각 $홀수$ 구성요소는 U에서 정점과 일치해야 $한다$ . U의 각 꼭지점은 (최대 c에서 일치하기 때문에) 하나 이상의 연결된 구성요소와 이 관계에 있을 수 있다.e 완벽한 매칭, $홀수 (G$ - U $)$ ≤ $U$ .^[2]

충분함 (∗): $G$ 를 완벽한 일치가 없는 임의의 그래프가 되게 하라. $우리$ 는 Tutte 위반자, 즉 S < 홀수(G - $S)$ 와 같은 $V$ 의 서브셋 $S$ 를 찾을 것이다 $.$ 우리는 $G$ 가 엣지-최대값이라고 가정할 수 있다. 즉, $G$ + $e$ 는 이미 $G$ 에 존재하지 않는 $모든$ 엣지에 대해 완벽한 일치를 가지고 있다.실제로, 만약 우리가 가장자리 최대 그래프 $G$ 에서 Tutte 비올라레이터 $S$ 를 발견한다면, $G$ - $S$ 의 모든 홀수 구성요소가 적어도 하나 이상일 가능성이 있는 더 많은 구성요소로 분할될 것이기 때문에 S $또한$ $G$ 의 모든 스패닝 서브그래프에서 Tutte 비올라레이터가 된다.

$S$ 를 도 $V$ - $1$ 의 정점 집합으로 정의한다. 먼저 $G$ - $S$ 의 모든 성분이 완전한 그래프인 경우를 고려한다.그렇다면 $S$ 는 투테 바이올레이터가 되어야 하는데, $만약$ 홀수 $(G -$ S) s $S$ 가 있다면, 우리는 모든 홀수 구성 요소로부터 하나의 꼭지점을 $S$ 의 꼭지점과 일치시키고 다른 모든 정점을 페어링함으로써 완벽한 짝을 찾을 수 있기 때문이다( $V$ 가 홀수인 경우가 아니라면, 그러나 $\emptyset$ 은 투테 바이올레이터가 된다).

$이제$ $K$ 가 G - $S$ 와 $x$ 의 구성요소라고 가정하고, $y$ y $K$ 는 $xy$ ∉ $E$ 의 정점이라고 가정한다. $x,$ $a,$ $b$ ∈ $K$ 는 $K$ 에서 가장 짧은 $x,$ y-path의 첫 정점이다.이를 통해 $xa, ab$ $e$ E 및 $xb e$ E가 $보장$ 된다. ∉ $S$ 부터 $ac$ $ac$ E와 $같은$ 정점 c가 존재한다. $G$ 의 에지 최대치로부터 우리는 $G$ + $xb$ 와 $M$ 에서₂ 완벽한 매칭으로 $M$ 을₁ $정의$ 한다.반드시 $xb m 1$ M $및$ ac $m 2$ M을 준수하십시오.

$P$ 는 $C$ 에서 $M$ 에서₁ 가장자리로 시작하고 가장자리가 $M$ 과₁ $M$ 으로₂ 번갈아 나타나는 $G$ 의 최대 경로가 되도록 한다. $어떻게$ P가 끝날 수 있을까? $x,$ $a$ 또는 $b$ 와 같은 '특별한' 정점에 도달하지 않는 한, 우리는 항상 계속할 수 있다: $c$ 는 $ca$ 로 M을 $2$ 매칭하므로 $P$ 의 첫 번째 가장자리는 $M$ 에₂ 있지 않으므로 두 번째 꼭지점은 다른 가장자리로 M을 매칭하고 $2$ 우리는 이러한 방식으로 계속한다.

$v$ 가 $P$ 의 마지막 꼭지점을 나타내도록 하자. $P$ 의 마지막 가장자리가 $M$ 에₁ 있으면 $v$ 는 a여야 $하는데$ , 그렇지 않으면 M에서 $가장자리$ 를₂ 계속 유지할 수 $있기$ 때문이다( $x$ 또는 b까지 도달).이 경우 $C := P$ + $ac$ 를 정의한다. $P$ 의 마지막 에지가 $M$ 에₂ 있는 경우, 유사한 이유로 $v$ $\in$ { $x,$ $b$ }을(를) 분명히 하고 $우리$ 는 $C := P$ + $va$ + ac를 정의한다.

이제 $C$ 는 $G 2$ + ac의 모든 다른 에지와 $M$ 의짝수 $길이$ 의 사이클이다.이제 $M := M 2$ Δ $C$ (여기서 Δ는 대칭 차이)를 정의할 수 있고, $G$ 에서 일치, 즉 모순을 얻을 수 있다.

Tutte-Berge 공식에 대한 동등성

The Tutte–Berge formula says that the size of a maximum matching of a graph $G=(V,E)$ equals $\min _{U\subseteq V}\left( U -\operatorname {odd} (G-U)+ V \right)/2$ . Equivalently, the number of unmatched vertices in a maximum일치는 $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ ( $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ ( $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ - U $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ ) $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ - U $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ ) ${\$ U $\right$ }과 같다 $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$

$이$ 공식은 Tutte의 정리로부터 $따르며$ , G {\displaystyle $G}$ 은(는 $)$ $|V|-2k$ $G^{(k)}$ $|V|-2k$ k $){\$ G $^{(k)}}$ 를 각각 V - $|V|-2k$ ${\displaystyle$ V $-2k}$ 의 새로운 $|V|-2k$ 정점을 추가하여 $G^{(k)}$ 얻은 경우에만 $k$ 크기 $k$ {\ $displaystysty k}$ 와 일치한다는 $G$ 관측과 함께 나타난다. $G$ $G$ 가 완벽하게 일치한다.Since any set $X$ which separates $G^{(k)}$ into more than $X$ components must contain all the new vertices, (*) is satisfied for $G^{(k)}$ if and only if $k\leq \min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right)/2$ $k\leq \min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right)/2$ $k\leq \min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right)/2$ ${\displaystyle k\leq \min _{U\subseteq V}\좌측(U -\operatorname {odd}(G-U)+V \우측)/2$ } $.$

무한 그래프에서

국소적으로 유한한 연결된 무한 그래프(모든 정점에는 유한도가 있음)^[3]의 경우, 투테 조건의 일반화는 유지된다. 이러한 그래프는 유한 부분 집합이 없는 경우에만 완벽한 일치를 가지며, 부분 집합의 크기보다 더 큰 다수의 유한한 홀수 성분을 생성한다.

참고 항목

외부 링크

(유튜브에서) 완벽한 매칭의 존재에 대한 투트의 정리 선일 찬드란.
투트의 정리(Math StackExchange에서)에서 홀의 정리를 추출한다.

메모들

^ 로바스 & 플럼머(1986), 페이지 84, 본디 & 머티(1976), 정리 5.4, 페이지 76.
^ 본디 & 머티(1976), 페이지 76–78.
^ Tutte, W. T. (1950). "The factorization of locally finite graphs". Canadian Journal of Mathematics. 2: 44–49. doi:10.4153/cjm-1950-005-2. MR 0032986.

참조

Bondy, J. A.; Murty, U. S. R. (1976). Graph theory with applications. New York: American Elsevier Pub. Co. ISBN 0-444-19451-7.
Lovász, László; Plummer, M. D. (1986). Matching theory. Amsterdam: North-Holland. ISBN 0-444-87916-1.

[1] 로바스 & 플럼머(1986), 페이지 84, 본디 & 머티(1976), 정리 5.4, 페이지 76.

[bm-proof-2] 본디 & 머티(1976), 페이지 76–78.

[3] Tutte, W. T. (1950). "The factorization of locally finite graphs". Canadian Journal of Mathematics. 2: 44–49. doi:10.4153/cjm-1950-005-2. MR 0032986.

[1]

[2]

[3]

Search