그래프 이론 (1)

 그래프란?

정점(Vertex)과, 두 정점을 잇는 간선(Edge)의 집합.

간선에 의해 이어진 두 정점은 서로 인접(Adjacent)하다고 한다.

[그림 01]  일반적인 그래프

 그래프의 방향성

간선에 화살표 표시가 있다면,  해당 방향으로만 움직일 수 있다.

• 그래프의 방향성

간선에 화살표 없음 :  무향 그래프,  양방통행.

간선에 화살표 있음 :  유향 그래프,  일방통행.

[그림 02]  무방향성 그래프

[그림 03]  방향성 그래프

위의 방향성 그래프에서는 3에서 5로 갈 수 없다.

간선에 방향성이 부여되었기 때문.

 정점의 차수

무향 그래프에서 정점에 연결된 간선의 수를 차수(Degree)라고 한다.

유향 그래프에서는 더욱 세부적으로 구분한다.

• 입력 차수 (in-degree)   : 해당 정점으로 들어오는 간선의 수.
• 출력 차수 (out-degree) : 해당 정점에서 나가는 간선의 수.

 가중 그래프

엣지에 가중치가 부여된 형태.

해당 간선을 사용하기 위한 비용이라고 생각하자.

[그림 04]  가중 그래프

1에서 4로 이동하기 위해서는 390(= 250+140)만큼의 비용이 필요하다.

 보행 (Walk)

정점과 간선이 교대로 나타나는 시퀀스.

단, 시퀀스에서 인접한 정점과 간선은 서로 인접해야 하며,
시퀀스의 처음과 끝은 정점이어야 한다.

두 정점 사이를 잇는 간선이 유일한 경우,

시퀀스에서 간선이 생략될 수 있다.

[그림 05]  무향 그래프

정점 1에서 4로 이동하기 위한 보행은 {1, 3, 4}로 정의된다.

임의의 두 정점 사이의 간선은 유일하므로, 엣지는 생략되었다.

보행의 종류

• 보행 (Walk)
  정점과 간선이 교태로 나타나는 시퀀스.
  단, 시퀀스의 처음과 끝은 정점이어야 하며, 서로 달라야 한다.
  
  

• 경로 (Path)
  정점이 중복되지 않는 보행.
  
  

• 트레일 (Trail)
  간선이 중복되지 않는 보행.
  
  

• 닫힌 보행 (Closed-Walk)
  시작과 끝이 같은 보행.  {3, 5, 4, 3}
  닫힌 트레일은 투어(Tour).
  닫힌 경로는 싸이클(Cycle)이라고 한다.

  
  [그림 06]  닫힌 경로,  싸이클

보행의 특성 정리

	first = last	정점 중복을 허용	간선 중복을 허용
보행	×	○	○
트레일	×	○	×
경로	×	×	×
닫힌 보행	○	○	○
닫힌 트레일	○	○	×
닫힌 경로 (사이클)	○	×	×

정점이 겹칠 수 없다면,

간선도 겹칠 수 없다.

그래프 전체를 거치는 보행

• 오일러 트레일 (Eulerian-Trail)
  모든 간선을 정확히 한번씩 사용하는 Trail.
  즉, 같은 정점을 여러번 사용해도 상관없다.  {2, 1, 3, 4, 5, 2, 3, 5}
  
  [그림 07]  오일러 트레일의 예시
  
  
  
• 해밀턴 경로 (Hamiltonian Path)
  모든 정점을 정확히 한번씩 사용하는 Path.   {1, 2, 5, 4, 3, 1}
  처음과 끝이 같은 해밀턴 경로는, 해밀턴 순환이라고 한다.
  
  [그림 08]  해밀턴 순환의 예시

 그래프의 크기

• 두 정점간의 거리
  두 정점 사이의 가장 짧은 경로에서, 간선의 수.
  아래 그래프에서 2와 3 사이의 거리는 1.
  
  [그림 09]  두 정점간의 거리 예시
  
  
  
• 이심률 (Eccentricity)
  한 정점에서 다른 정점 사이의 거리들 중, 가장 먼 거리.
  아래 그래프에서 2의 이심률은 2.
  
  [그림 10]  이심률 예시
  
  
  
• 지름 (diameter)
  그래프의 최대 이심률.
  아래 그래프의 지름은 4.
  
  [그림 11]  그래프의 지름 예시
  
  쭉 피면 아래처럼 된다.
  
  [그림 12]  그림 11과 같은 모양의 그래프