20. 그래프의 탐색(10-2)

그래프의 탐색

1. 그래프의 탐색

. 그래프의 가장 기본적인 연산 

. 연결된 간선들을 통하여 그래프의 각 정점들을 모두 한 번씩 방문하는 방법 

. 그래프의 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결됨 

(예) 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부 

(예) 전자회로에서 특정 단자와 다른 단자가 서로 연결되어 있는지 여부 

. 주어진 그래프 G=(v,E)와 정점  v∈V가 주어졌을 경우,  v로부터 도달 가능한 모든 정점들을 방문하는 그래프의 탐색에는 깊이 우선 탐색과 너비 우선 탐색 방법이 있다. 

1) 깊이우선 탐색(Depth  First  Search  : DFS) 

. 탐색과정 

①출발 정점을  v를 방문한다. 

②  v에 인접하고 아직 탐색을 거치지 않은 정점w를 선택한다. 그리고 w를 기준으로 다시 w에 인접하고 아직 탐색을 거치지 않은 정점u을 선택해 나가는 방식으로 탐색을 반복한다. 

③반복 과정 중에 인접한 모든 정점이 이미 탐색을 거친 상태라면 가장 최근에 탐색했던 정점 중에서 아직 탐색되지 않은 정점을 기준으로 다시 깊이 우선 탐색을 시작한다. 

④모든 정점을 방문 후 탐색을 종료한다. 

depth_first_search(v) 

  v를 방문되었다고 표시; 

for  all  u ∈  (v에 인접한 정점)  do 

  if  (u가 아직 방문되지 않았으면)then  depth_first_search(u) 

2) 너비 우선 탐색(breadth  First  Search  :  BFS) 

. 너비우선 탐색은 항상 새로 선택한 정점을 기준으로 인접한 정점을 방문하는 깊이 우선 탐색과는 달리 출발정점을 기준으로 인접한 정점들을 차례로 먼저 모두 방문하는 방식의 탐색방법이다. 

. 탐색과정 

① 출발 정점을  v를 방문한다. 

②  v에 인접하고 아직 탐색하지 않은 정점들 을 모두 탐색한다. 

③  그리고  순서대로  에  인접한  정점들을  같은  방법으로  탐색하게  된다.  이  과정을  더  이상 방문할 정점이 없을 때까지 반복 실행한다. 

④ 모든 정점을 방문 후 탐색을 종료한다.

너비 우선 탐색 알고리즘 

breadth_first_search(v) 

v를 방문되었다고 표시; 

큐 Q에 정점  v를 삽입; 

while  (not  is_empty(Q))  do 

       Q에서 정점 w를 삭제; 

        for  all u ∈  (w에 인접한 정점) do 

                 if  (u가 아직 방문되지 않았으면)  then  { 

                          u를 큐에 삽입; 

                          u를 방문되었다고 표시; 

2. 그래프의 색칠문제

정의1

G=(V,  E)는 다중 간선이 없는 그래프이고,  C={c1,  c2,  c3,…,  cn  }은  n개의 색깔로 구성된 임의의 집합이라고 하자. 

임의의 함수  f  :  V.  C는  “n색깔을 이용한 그래프  G의 채색(또는 그래프G의 색칠문제  coloring problem))’이라고 한다. 모든 정점  v 각각에 대하여,  f(v)는  v의 색깔이다. 

.그래프 색칠문제의 예를 들면 그래프가 연결된 도시들을 표현한다고 하자.

 각 도시는 그 도시에 가장 많이 이륙 또는 착륙하는 항공편을 가진 항공사 이름으로 레이블 될 수 있다. 이 경우 

정점은 도시이고, 색깔은 항공사 이름이 된다. 

. 모든 이웃한 정점  i와  j는 서로 다른 색깔로 채색될 때, 이러한 채색은  ‘적당하다(proper)’라고 한다. 

정의2

그래프  G를  색칠하는데  필요한  최소한의  색의  수를  x(G)로  표현하고  G의  색칠수  (chromatic number) 혹은 채색수 라고 한다. 

. 단순 그래프의 색칠은 각각의 정점을 서로 다른 색으로 색칠함으로써 알 수 있다. 

그러나 대부분의  그래프에서  정점의  수보다  적은  색깔을  사용해도  색칠이  가능하다.  

그렇다면  몇  가지 색으로 모든 경계가 구별되도록 색칠을 할 수 있을까? 

. 그래프 채색의 예  :  (1) 지도채색문제 

. 지도를 채색하는 것은 각 영역(국가, 주, 군, 도, 등)이 경계선을 공유하는 두 영역에 같은 색깔로 채색되는 일이 없도록 색칠 하는것. 

. 지도 채색문제는 지도를 채색하기 위하여 사용되는 최소의 색깔의 가지 수를 찾는 것. 

. 지도 M이 주어지면, 각 영역을 하나의 정점으로 표현하고 경계를 공유하는 영역에 해당하는 정점들을 간선으로 표현함으로써 그래프 GM을 구축. 

. 지도를 색칠하는 문제는 그래프의 색칠문제와 연관시킬 수 있다. 예를 들어  (1)의 지도는  (2)의 그래프와 동형이 되는데, 이것을 쌍대 그래프(dual graph)라고 한다. 

. 지도의 영역을 색칠하는 문제는 쌍대 그래프의 정점들을 색칠하는 문제와 동일하므로 그래프의 인접한 어떤 정점들도 같은 색을 가지지 않도록 해야 한다. 

. Welch-Powell의 알고리즘 

(1)  G의  정점의  차수가  내림차순(descending  order)이  되게  배열한다(이  배열은  차수가  같은정점이 여러 개 있을 수 있으므로 몇 가지 다른 순서가 존재할 수 있다). 

(2) 배열의 첫 번째 정점은 첫 번째 색으로 착색하고 계속해서 배열의 순서대로 이미 착색된 정점과 인접하지 않은 정점을 모두 같은 색으로 착색한다. 

(3) 배열에서 먼저 나타나는 착색되지 않은 정점을 두 번째 색으로 착색하고 계속해서 배열의 순서대로 지금 착색하고 있는 색으로 이미 착색된 정점과 인접하지 않은 정점을 모두 착색한다. 

(4) 계속해서 위의 과정을 그래프의 모든 정점이 착색될 때까지 반복한다. 

. 그래프 채색의 예  :  (2) 세기(counting) 문제 

. 가까이 두면 서로 반응하는 화학 물질들을 분리하여 저장할 필요가 있을 때, 화학물질을 저장하기 위한 실험실 서랍의 최소개수를 계산하는 문제 

.  15가지 음식을 같은 냉장고 안에 여러 칸에 넣으려고 하는 것을 그래프로 표현 하는 경우 

. 먼저  1가지 음식을 하나의 정점(vertex)으로 표현하고, 반드시 분리되어 저장되어야 하는 음식을 간선(edge)으로 연결한다. 그러면  x(G)는  15가지 음식을 저장하는데 최소한 필요한 칸의 수가 된다. 

. 채색다항식(Chromatic  polynomial) 

.  x(G)를 계산하는 문제와 깊이 관련이 있는 문제 중에 집합  C={c1,  c2,  …  ,  cn  }의 색깔을 이용한 그래프 G의 적당한 채색의 가지수는 몇인가 계산하는 문제 

정의3

G가 그래프이고  n≥0은 정수이면,  n이나 더 적은 수의 색을 이용하여 그래프  G를 적당히 채색하는 방법의 수를 채색다항식  (Chromatic  polynomial) 이라고 하고,  PG(n)으로 표기한다.