Hall's Marriage Theorem, Isomorphism of Graph

Hall's Marriage Theorem

그래프가 Hall's condition에 있다는 것은 Matching 이 있다는 것을 얘기한다.(if and only if)

If there is Matching there is Hall's Condition satisfied

If Hall's Condition is satisfied, There is a matching.

매칭한다는 것이 보장되면 Correspondence 한 Super Graph.

=> Matching 한 것이 Hall's Condition을 만족한다는 것이 정리

 

 

Induction Basis

V1 Perfect Matching이 Induction basis에 들어간다.

(단독 지원을 하면 당연히 어느 곳이든 들어갈 수 있다라고 생각하면 됨)

 

Induction Step

A라는 집합이 V1의 subset이라고 하면 N(A) 보다 작다라는 것을 가정한다.

또한 A라는 집합이 N(A)와 같은 두 가지의 경우가 있음에 저명하다.

(N(A) : Neighbor of A)

 

Case1

: V1에 있는 애들을 V2에 모두 취업시키는 시스템이라고 생각

A라는 집합이 V1의 진부분집합이라고 하자.

그럼 A < N(A)를 만족하는 집합 A를 어떻게 설정해야 하는가?

a(알파) 라는 점을 생각하고 알파라는 점과 매칭되는 V2의 b(베타)점이라고 생각을 해보자

그러면 V1에는 a를 제외한 V1' 이 생기고 V2에는 b를 제외한 V2'가 생긴다.

=> |V1'| = |V1| - 1 이라는 것이 만족한다.

 

Case2

: |A| = |N(A)| 의 경우에 대해서 다루고자 함

Hall's condition을 위반하는 것은 생각하지 않아도 됨이 저명하다. (A| > |N(A)|)

A의 크기와 동일한 N(A)가 존재한다고 가정하자.

이런 경우 A와 N(A)의 매칭은 A의 Complement와 N(A)의 Complement의 매칭을 구해서

Union을 하면 Biatal Graph를 구할 수 있다.

 

그러나 Inductive Hypothesis에 의해서 성립함을 항상 주장할 수 있는가??

Complement 한 것의 Subset을 하나 잡고 그것의 Hall's Condition의 Inductive hypothesis함을 구한다면

역으로 올라와서 전체가 성립함을 주장할 수 있지 않을까

 

AUA' 와 N(AUA')의 관계를 살펴보자

AUA'는 당연히 V1의 Subgraph이므로 직관적으로 | AUA' | <= | N(AUA') |  함을 보일 수 있다.

또한 |A| + |A'| <= | N(A) U { N(A') - N(A) } | <= | N(A) | + | N(A') - N(A) | 이므로 

| A' | <= | N(A') - N(A) | 임을 추론할 수 있고 Induction이 Satisfy 할 수 있다고 할 수 있다.

 

 

Isomorphism of Graph

모양이 다른 Graph의 구조를 재배지 Rearrange 해서 동일한 모양으로 만들 수 있는 것을 Isomorphism 이라고 한다.

Vertice v1 v2 그리고 Vertice w1 w2가 있으며 

f: v1 -> w1으로 보내는 함수가 있다고 가정하자 그러면 (f(v1),f(v2))로 갈 수 있다고 할 수 있다.

(v1, w1) iff (f(v1),f(v2))

One to one correspondence의 개수는 vertice가 n개라고 했을 때 Isomorphism한지 Check 하기 위해서

N! 의 경우의 수가 나오는 지 확인하면 된다.