Introduction to graph theory

Theorem 1.1 G가 n개의 vertices를 갖는 multigraph 라고 하면 각 vertex의 degree(vertex에 연결된 edge의 갯수)의 합은 G의 edge 갯수의 2배와 같다.


Corollary 1.2 odd vertices(degree가 홀수인 vertices) 의 갯수는 짝수이다.

• complete graph : graph의 모든 vertices 가 서로 연결되어 있는 graph. Kn 으로 표시. 여기서 n은 order로서 vertices의 수를 의미
• null graph : 그래프 G가 있을때 E(G) =0 인 그래프. 즉 edge가 하나도 없는 그래프. Nn으로 표시. 여기서 n은 vertex 수
• walk : vertex와 edge의 번갈아가면서 나오는 sequence. v0 e0 v1 e1 v2... vn. 이때 길이는 edge의 갯수
• trail : walk 중에 edge가 두개 이상 반복이 안된 walk.
• path : walk 중에 vertex가 두개 이상 반복이 안된 walk. path는 반드시 trail이다. 그러나 역은 반드시 성립하는 것은 아니다.
• distance from x to w : vertex x 에서 vertex w 까지의 최단 path 길이. d(x,w) 로 표현한다.
• closed : vertex u에서 시작해서 vertex v로 끝나는 walk가 있을때 u = v 이면 이는 closed 되어 있다고 한다.
• circuit : closed walk 중에 edge가 반복이 안된 walk.
• cycle : circuit 중에 vertex가 반복이 안된 circuit. Cn 은 n 개의 vertex를 갖는 cycle을 의미
• connected : multigraph G의 모든 vertex가 path로 연결되어 있다면 G는 connected 되었다고 한다.
• isomorphic : 두 그래프 G와 H가 같을때 isomorphic이라 한다. 정확히 이야기 하자면 isomorphism 이라고 불리는 함수 f (그래프 G에서 H로의 mapping(vertex to vertex) 함수로서 그래프 G의 adjacency(두 vertices의 연결)를 유지하게 하는 함수)  가 존재할 때, 두 그래프는 isomorphic 하다라고 한다. isomorphism은 하나 이상이 될 수 있다.
• induced subgraph : H가 G의 induced subgraph 라고 한다면 v(H) 가 v(G)의 subset이고 이 G 안에서 subset 사이에 존재하는 edge가 모두 H에 있음을 의미한다. 

Isomorphism Testing Problem : 두 그래프 G와 H가 isomorphic한가를 판단하는 문제.

--chapter 3--

• bipartite : order(vertex의 갯수)가 최소 2 이상인 그래프 중 vertex가 두 그룹으로 나뉘고 모든 edge가 각 두 그룹의 vertex를 join 하게 할때 이를 bipartite 라고 한다.
• partite sets : bipartite graph에서 두 subgroup(두 vertex set)을 partite set이라 한다.

Theorem 3.1 : 그래프 G는 odd cycle을 포함하지 않을 때(필요충분조건) bipartite 가 된다. 이는 아래 Lemma 3.2를 이용하여 증명할 수 있다.

Lemma 3.2 : odd 길이의 closed walk(시작 vertex와 끝 vertex가 같은 walk)는 항상 odd cycle을 포함한다.

• tree : cycle이 없고 connected 된 graph

Theorem 3.3 : G가 connected graph 라고 할 때, G의 임의의 두 vertex가 unique path에 의해 join 된다면(필요 충분 조건) , G는 tree이다.

Theorem 3.4 : G가 order가 n이고(v(G) = n) size가 m일때(e(G) = m) m = n-1 이면 G는 tree이다.

--chapter 4--

• k-colouring of G : 그래프 G가 있을때 그래프의 각 vertex를 k 개의 색깔로 칠하는 방법. 단 adjacent(연결된 vertex) 한 vertex끼리는 다른색이여야 한다.
• chromatic number of G : k-colouring of G에서 가장 작은 k 값. X(G) 로 표현.

--chapter 6--

• Euler circuit : connected multigraph 인 G가 있을때 G의 모든 edge를 포함하는 circuit.
• Eulerian multigraph : Euler circuit을 갖는 multigraph, 쉽게 이야기 하면 그래프의 모든 edge를 한번씩 통과해서 시작 vertex로 오게 되는 walk를 갖고 있는 graph

Theorem 6.1 G가 connected multigraph 라고 할 때 G의 모든 vertex의 degree가 even 일때(모든 vertex에 연결된 edge의 갯수가 짝수 일때)만 Euler graph이다.

• spanning cycle : order 가 3이상(vertex의 갯수가 3이상)인 그래프 G가 있을 때 모든 vertex를 통과하는 cycle을 spanning cycle 이라 한다. euler circuit과의 차이는 euler circuit는 모든 edge를 포함해야 한다는 것이며 spanning cycle은 모든 vertex를 포함해야 한다는 것이다.
• hamiltonian graph : spanning cycle을 가지고 있는 graph

Rules for constructing Hamiltonian cycles in G

1. degree가 2인 vertex의 모든 edge는 spanning cycle에 포함되어야 한다.

2. spanning cycle을 만드는 도중에 spanning cycle이 아닌 cycle이 형성될 시에는 그 그래프는 Hamiltonian graph가 될 수 없다.

3. spanning cycle을 만드는 도중에 vertex의 2개의 edge가 정해졌다면 그 vertex에 연결된 그 외의 edge는 제거한다.

Theorem 6.3 G가 만약 Hamiltonian graph 라면 V(G)의 non-empty subset S에 의한 c(G-S)는 |S| 보다 작거나 같다. c(G-S) 는 graph G 에서 subset인 S에 포함되는 vertex와 그 vertex에 연결된 edge를 지운 graph 의 component 갯수를 의미. theorem 6.3은 Hamiltonian graph의 필요 조건.

Theorem 6.4 order가 3 이상인 그래프 G가 있을 때, 모든 vertex에 대해 d(v)가 n/2 이상이 되면 이는 Hamiltonian graph 이다.

Theorem 6.5 order가 3 이상인 그래프 G가 있을때 adjacent vertices를 제외한 모든 vertex 페어에 대해서 d(u) + d(v)가 n 보다 크거나 같으면 이는 Hamiltonian graph 이다.

maximum Matching in bipartite graph

cufflinks를 보다보면 이런 말이 나온다. "It does so by reducing the comparative assembly problem to a problem in maximum matching in bipartite graphs".

아.. comparative genome assembly가 무엇이냐. 생소한 표현이다 assembly면 de novo assembly지 뭔 comparative냐. 아.. 근데 문득 드는 생각이.. 혹시 이거 mapping 해서 assembly 하는거니까 그걸 comparative genome assembly 라고 하는거 아니야? 음.. 맞는거 같다. 특히나 이 사이트를 보니까 더욱 확실한거 같다. comparative genome assembly 이거 그냥 mapping assembly를 뜻하는 거다. 근데 찾다 보니 이런 논문도 나오더라. 역시나 이 논문도 CBCB에서 나온거다. 이 논문에 완전 정확하게 comparative genome assembly의 정의를 내린다. AMOS 프로젝트에서 나온 program을 소개하는 논문인데 이건 패스하자. 이게 중요한게 아니다.

그리고 또 bipartite graph는 뭐냐? 이건 쉽게 끝날 문제가 아닌듯 보인다.. 일단은 여기를 보자. 인트로다. 그거 다 봤으면 여기를 보자. 이거 다 보고 정리하겠다. (단순 graph theory에 대한 건 여기를 보자)


The marriage Problem and Matchings
결혼이란 문제로 maximum matching problem을 설명하자면 ..
아래 그림과 같이 각각 n 명(여기서는 6명)의 싱글 남녀가 있다고 할 때 점은 남여 개체를 의미하고 선은 상호간의 관심이 있는 상대를 의미한다. 예를 들어 Ann 이라는 여성은 Adam과 Bob에게 관심이 있다. 이 때 match가 됐다는 것(matching)은 각 개체가 오직 한사람의 상대와 이어짐을 의미 한다. 아래 빨간 선이 matching을 의미 한다(물론 다른 경우의 수도 있다). 특히 이때 모든 개체가 빠짐 없이 matching이 되면 이를 perfect matching이라 한다(아래 그림). 

그러나 일반적인 문제에서는 위와 같이 perfect matching 이 어려운데 이 때 최대의 match를 끌어내는 것이 maximum matching problem이다.


Hall's Theorem
Hall 이란 사람이 perfect matching 이 되기 위한 조건을 정리 했는데 다음과 같다
Hall's Theorem : 두 클래스 X,Y를 갖는 bipartite graph G=(V,E) 가 주어졌을 때 이 G가 perfect matching이 되기 위해서는 클래스 X의 subset인 S에 대해 |Adj(S)| >= |S|를 만족해야 한다. Adj(S) 란건 S에서 부터 연결된 클래스 Y의 개체를 의미. 다르게 이야기 하면 X의 subset S랑 연결 선이 있는 클래스 Y의 사람 수가 최소한 S의 사람수 이상은 되야 된다는 이야기.


그런데 이건 정리지 뭐 이거 자체가 알고리즘이거나 하진 않다.  그래서 여기서 이야기 하길 Dijkstra's algorithm에서 효과적인 알고리즘은 찾는단다. 단계적으로 matching을 개선해서 결국 optimal solution을 찾는다는 건데.. 어쩌라는 거냐. 다음 예를 보자.


아래와 같은 상황이 있다고 하자. 안타깝게도 Dorothy, Evelyn, Carl, Erik은 짝이 없다. 이거 어떻게 해결할거냐. 일단 Dorothy 부터 보자. Dorothy에서 연결될 수 있는 짝이 Bob이고 그렇게 되면 Bob에 연결된 Ann을 Adam에 match 시켜야 하고 다시 또 Adam에 연결되었던 Beth는 Carl과 연결시킨다. 이렇게 함으로써 기존의 match M에서 새로운 match M' (|M'| = |M| +1) 이 생기게 된다.


여기서 중요한건 alternative path (= a-path)가 있었다는 것.  음 이게 뭐냐면.. unmatch vertex 에서 시작해서 unmatch vertex로의 path. 즉 길. 근데 왜 alternative이냐 이 길에서 홀수 번째 edge는 현재 match M에서 사용되지 않고 있는 edge이고 짝수 번째 edge는 M에 사용되는 edge인데 이 짝수 번째 edge 대신 홀수 번째 edge를 match로 여기면 이게 새로운 match M'가 되기 때문이다.

이것에 대한 pseudo code는 다음과 같다.

여기서 핵심은 3번째 라인 a-path를 찾는것. 여기서는 modified Breadth-First-Search를 언급하나 이건 패스.


마지막에 a-path가 없을때까지 improve를 시켰다면 이것이 과연 optimal maximum match 인가를 증명한다. 이건 생략