1-2강 - Introduction (Graph Problem)

cf> incident, adjacent

• v_1과 v_3는 adjacent
• e_1은 v_1(v_3)와 incident

 

2. Graph Problem 1

1) Minimum Vertex Cover Problem

0> vertex cover = S_VC

• ∀ e ∈ E and ∀ v ∈ S_VC ⊂ V, v is incident to e  (vertex cover : 모든 e와 incident할 수 있는 v들의 조합)

1> 문제

• 크기가 최소인 vertex cover 구하기 (즉, 모든 e와 incident하는 v를 최소한의 개수로 고르는 문제)

2) Maximum Independent Set Problem

0> independent set = S_IND 

• ∀ v_1, v_2 ∈ S_IND ⊂ V, v_1 is not adjacent to v_2  (vertex cover : 고른 v들끼리 adjacent 하지 않는 조합)

1> 문제 

• 크기가 최대인 independnt set 구하기

 

cf> 예제

3) Maximum Clique Problem

0> clique = S_C

• ∀ v_1, v_2 ∈ S_C ⊂ V, v_1 is adjacent to v_2  (vertex cover : 고른 v들끼리 모두 서로 adjacent 조합)

cf> 주의 

v_0 자체만으로도 clique이다. (adjacent의 개념이 vertex 자신에게도 적용할 수 있다.)

 

1> 문제

• 크기가 최대인 clique 구하기

2> 예제 

3. Graph Problem 2

1) Maximum (Cardinality) Biapartite Matching

0> 상황

어떤 회사에 N명의 직원과 M개의 일감이 있다.

각 직원은 일감 중 할 수 있는 일이 있고 없는 일이 있다.

관리자는 가능한 많은 일을 할 수 있도록 직원에게 일감을 맡기고 싶다.

 

1> Abstraction (추상화) (graph formulation)

N명의 직원을 N개의 vertex, M개의 일감을 M개의 vertex로 대응

할 수 있는 일감을 직원 vertex와 일감 vertex간의 edge로 나타낸다.

자연스럽게 직원 N개 vertex 간, 일감 M개 vertex 간에는 edge가 존재하지 않는다.

2> Bipartite graph

이와 같이 2개의 vertex set 내부에서는 edge가 없는 graph를 Bipartite graph라고 한다.

 

 

3> Matching

Vertex를 공유하지 않는 edge 집합

4> 문제

Bipartite graph 내에서 크기가 가장 큰 matching 구하기

 

2) Maximum Weighted Bipartite Matching

0> 상황

어떤 회사에 M 개의 일감이 있다. 일꾼에게는 각각 하나의 일감만 배정할 수 있다.
모집에 응한 N 명의 일꾼들은 각자 할 수 있는 일감들과 이들 각각에 대해 이를 맡을 경우 원하는 임금을 제시하였다.
관리자는 가능한 많은 일감을 최소의 비용으로 일꾼들에게 맡기고 싶다.

 

1> Abstraction (문제)

이전 문제와 비슷하게 bipartite matching 문제로 만든다,

그리고 '원하는 임금'을 (음수 값으로) cost에 부여해서 

이를 통해 최대 비용의 matching을 구한다. (즉, 지불할 임금을 최소화 하는 것이다.)

 

4. Graph Problem 3

1) Stable Matching Problem

0> 상황

남녀 각각 N 명이 참가한 미팅에서

각자 호감 순서대로 상대 이름을 적어 제출하면 이를 바탕으로 커플이 맺어진다.

 

1> Unstable pair

배정 결과에서

M은 그가 배정 받은 자보다 F를 더 선호하고

F는 그녀가 배정 받은 자보다 M 을 더 선호한다.

이 상황을 Unstable pair라고 한다.

 

2> Stable Matching

unstable pair가 없는 matching

 

3> 문제

untable pair가 없는 matching을 찾는 문제 (이러한 matching이 없을 수도 있다.)

 

4> 예시

- 위의 예시는 X는 C보다 B를 더 선호하고 B도 Y보다 X를 더 선호하므로 X와 B는 unstable pair이다.

 

- 위의 예시는 unstable pair가 없으므로 stable matching이다.

 

cf> undirected graph

방향성이 없는 그래프

 

5. Graph Coloring Problem

0) 상황

1> Given undirected Graph G = (V, E)

2> coloring

인접한 두 vertex 간에 서로 다른 label(color)를 배정하는 것이다.

 

1) K-coloring Problem

1> 문제

자연수 K가 주어졌을 때, G의 vertex들을 k 또는 그 이하의 색으로 labeling 할 수 있는지 조사하는 문제

가능한 경우 coloring의 결과를 보여준다.

 

2) Chromatic Number Finding

1> 문제 

G의 vertex들을 coloring 하기 위한 최소 color 수(chromatic number γ)를 구하는 문제 (물론, coloring을 보여주어야 한다.)