본문 바로가기

# Foundation/알고리즘

그래프 이론 (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과 같은 모양의 그래프