그래프

그래프 - 그래프란?

컴퓨터 과학에서 그래프란, ‘연결된 정점(node or vertex)과 그 정점을 연결하는 선인 간선(edge)으로 이루어진 자료구조’
그래프에 대한 쉬운 정의
- 유한개의 점과 그 점을 연결하는 선으로 이루어진 도형 즉, 점과 선 그리고 그들의 연결로서 표현된 도형을 그래프라고 한다
- 그래프는 모든 정점이 간선으로 연결되어 있지 않을 수 있다. 이러한 그래프를 비연결 그래프(disconnected graph)라고 한다
그래프 표기
- 그래프(graph) $G = (V, E)$
- $V$ : 그래프 $G$ 의 정점
- $E$ : 그래프를 연결하는 간선(edge)

그래프 - 그래프의 차수(degree)란?

차수란
- 한 정점에 연결된 간선의 수
홀수 점과 짝수 점
- 홀수 점 : 차수가 홀수인 정점
- 짝수 점 : 차수가 짝수인 정점
방향 그래프에서 진입 차수(In Degree)와 진출 차수(Out Degree)
- 아래 그림에서 노드 2로 들어오는 진입 차수는 2이고, 진출 차수는 1이다
Q. 그래프의 차수를 노드에 숫자로 표시하기

그래프 - 그래프의 종류

방향에 따른 분류
- 방향 그래프(directed graph)
  - 정점과 정점 사이 방향성이 있는 간선으로 이루어진 그래프
- 무방향 그래프(undirected graph, 또는 양방향 그래프)
  - 정점과 정점 사이 방향성이 없는 간선으로 이루어진 그래프
  - 보통 그래프라고 하면 이 무방향 그래프를 말함
- 그래프 표기
  - 방향 그래프
    - $G = < V, E >$
  - 무방향 그래프
    - $G = (V, E)$
구조적 특징에 따른 분류
- 단순 그래프(simple graph)
  - 두 정점 사이에 오직 한개의 간선만 존재하는 그래프
- 다중 그래프(multiple graph)
  - 두 정점 사이에 두 개 이상의 간선이 존재하는 그래프
- 의사 그래프(pseudo graph)
  - 다중 간선과 루프(loop)를 허용하는 그래프
- 완전 그래프(complete graph)
  - 모든 정점이 연결된 그래프, 두 정점 간에 최소한 한 개, 또는 그 이상의 경로가 반드시 있게 된다. 즉, 모든 정점의 쌍 사이에는 간선이 반드시 존재
  - $n$ 개의 정점으로 구성된 그래프에서 간선 수가 최대인 그래프
    - 무방향 그래프의 최대 간선의 수
      - $\frac{n ( n - 1 )}{2}$ 개
    - 방향 그래프의 최대 간선의 수
      - $n (n - 1$ ) 개
- 정규 그래프
  - 그래프 내에 있는 모든 정점의 차수가 같은 그래프
- 가중치 그래프
  - 간선에 가중치가 부여된 그래프
    - 가중치는 길이, 비용, 시간 등 다양하게 설정 가능
- 평면 그래프
  - 그래프가 평면(2차원)상에 그려질 수 있는 그래프이며, 이때 간선들은 서로 교차 하지않는 것. 어떤 두개의 간선도 교차하지 않게 그릴 수 있는 그래프
Q. 가중치 그래프에서 간선의 숫자는 거리를 말한다. $v 1$ 에서 $v 6$ 로 가는 최단 경로는

그래프 - 오일러 그래프

오일러 공식
- 평면 그래프에서 꼭짓점의 수를 $v$ , 모서리 수를 $e$ , 영역의 수를 $s$ 라고 할 때 다음 공식이 성립
  - 영역(face)
    - 간선에 의해 나누어진 면의 개수
    - 정삼각형의 영역은 2
      - 삼각형 안과 밖
- $v - e + s = 2$
오일러 경로
- 모든 모서리를 꼭 한 번씩만 지나는 경로
오일러 순환, 오일러 회로
- 꼭짓점 $v$ 에서 시작해 모든 모서리를 꼭 한 번씩만 지나 $v$ 로 다시 돌아오는 경로
- 회로(cycle)
  - 그래프 이론에서 회로란 시작점과 끝점이 일치하는 경로
오일러 그래프
- 오일러 순환을 가지는 그래프
한 붓 그리기
- 평면 그래프를 그릴 때, 모든 선분이 한 번만 그려지도록 하는 것
- 한붓그리기가 가능한 그래프를 플레이너 그래프(Planar Graph)라고 함
- 한붓그리기 가능한 조건
  - 그래프의 꼭짓점 중에서 차수가 홀수인 것의 개수가 0 또는 2개일 때, 한붓그리기가 가능. 이를 오일러의 한붓그리기 정리라고 함
- Q. 다음 도형에서 한붓그리기가 가능한 것을 고르시오

그래프 - 해밀턴 그래프

해밀턴 경로란?
- 모든 꼭짓점을 한 번씩 지나는 경로
  - 출발했던 꼭짓점으로 다시 돌아올 필요는 없음
해밀털 순환(회로)이란?
- 한 꼭짓점에서 시작해서 모든 꼭짓점을 꼭 한 번씩만 지나 원래 꼭짓점으로 다시 돌아오는 경로
해밀턴 그래프
- 해밀턴 순환을 갖는 그래프
Q. 해밀턴 경로를 그리시오

그래프 - 그래프와 색칠문제

4색 정리
- 4색 정리는 ‘어떤 지도든 서로 맞닿은 국가 혹은 행정구역이 서로 다른 색을 띠도록 만드는데 4색이면 충분하다.‘라는 정리를 말함
  - (많은 수학자가 증명에 실패하다가, 컴퓨터의 도움을 받아 4색 정리가 증명됨)
- 3색은 불가능
색칠한 영역을 그래프로 바꾸기
- 지도를 색칠하는 문제는 그래프 형태로 바꾸어 생각해 볼 수 있다
  - 색칠한 영역을 정점(노드)으로 하고 영역과 영역을 간선으로 연결하면 그래프가 만들어진다. 그래프의 인접한 정점들은 같은 색깔을 가지지 않도록 해야 한다
Q1. 종이의 각 부분에 5개의 색을 이용하여 각 칸을 구별하려고 한다면, 색칠하는 방법의 가짓수는
Q2. 5가지 색을 이용하여, 선으로 연결된 곳은 다른 색을 칠해야할 때, 색칠하는 방법은 몇가지인가?