[이산구조] L07.그래프

• toc {:toc}

그래프

• 그래프 G=(V, E) : 유한한 개수의 정점 V와 연결선 E로 이루어진다.

• 그래프

  • 방향 그래프 G=(V, E)
    • V : 정점의 집합
    • E : 정점들의 순서화된 쌍(아크), 연결선들의 집합
    • v → w 일 때 v는 선행자, w는 후속자라고 한다.
    • v와 w를 연결하는 연결선 e는 u와 v를 ‘접했다’고 하고 u와 v는 ‘인접했다’고 한다.
  • 무방향 그래프
  • 단순 그래프 : 한 쌍의 정점 사이에 하나의 연결선으로 이루어진 그래프. 자기 자신으로의 연결선이 없다.
  • 멀티 그래프 : 한 쌍의 정점 사이에 연결선 개수의 제한이 없는 그래프
  • 부분 그래프 : G = (V, E), G’ = (V’, E’)에서 , 인 경우
    • 정점, 연결선이 부분 집합에 속할 때
  • 생성 부분 그래프 : , 인 경우

• 경로 : 정점들의 열(순서)를 말한다. a, b, c

• 경로는 지나간 변을 반복해서 통과하지 않는 것에 유의하자.

  • 단순 경로 : 경로가 같은 연결선을 두 번 포함하지 않는 경로
  • 기본 경로 : 어떤 정점들도 두 번 방문하지 않는 경로
  • 사이클, 순회 : 경로에서 종점과 시점이 일치하는 경우
  • 단순 사이클 : 같은 연결선을 반복하여 방문하지 않는 사이클
  • 기본 사이클 : 시작점을 제외한 어떤 정점도 반복해 방문하지 않는 사이클
  • 오일러 경로 : 멀티 그래프에서 모든 연결선들을 꼭 한 번씩만 통과하는 경로

• 그래프 정점들 간 연결 여부

  • 연결 그래프 : 그래프의 모든 정점들이 연결되어 있는 그래프
  • 강한 연결 그래프 : 방향 그래프에서 두 정점 a, b에 대해 a → b 경로, b → a 경로들이 존재하는 그래프

• 연결 요소 : 모든 정점들이 연결되어 있는 부분

• 연결수 : G 에서의 연결 요소의 개수

• 차수 : 정점과 인접하는 연결선들의 개수 d(v) = 3 → v에 대한 차수는 3이다.

• 쾨니히스베르크 다리 문제 - 오일러 경로를 판별하는 문제

  • 오일러 경로 판별 규칙
    • 모든 정점에서 연결된 개수가 홀수인 정점의 개수가 0 또는 2인 경우

그래프의 표현 방법

• 인접 행렬 : G = (V, E) 에서 V의 원소의 개수가 N일 때 NxN 행렬 A로 나타낸다.

  • 연결되면 1, 아니면 0으로 나타낸다.

• 인접 리스트 : 정점에 대해 포인터가 주어지고 연결된 정점을 차례로 리스트로 표시한다.

  • 같은 리스트 내에서는 순서에 관계가 없다.

특수 형태의 그래프

• 모든 정점들의 차수의 합 = 연결선의 개수 x 2

• 오일러 경로 : 그래프에서 각 연결선을 단 한 번씩만 통과하는 경로

  • 오일러 경로를 가지기 위한 필요 충분 조건
    • 모든 정점에서 연결된 개수가 홀수인 정점의 개수가 0 또는 2인 경우

• 오일러 순회 : 그래프에서 정점은 여러 번 지날 수 있지만, 각 연결선을 단 한 번씩만 통과하는 순회

  • 오일러 순회를 가지기 위한 필요충분조건
    • G = 연결 그래프, 모든 정점들이 짝수 개의 차수를 가지는 경우
    • 모든 정점이 짝수 개로 연결되어 있는 경우

• 한붓그리기 조건 : 시작점과 끝점을 제외한 모든 정점의 차수가 짝수여야 한다.

• 해밀턴 경로 : 그래프에서 모든 정점을 오직 한 번씩만 지나지만 시작점으로 돌아오지 않는 경로

• 해밀턴 순회 : 그래프에서 모든 정점들을 오직 한 번씩만 지나는 순회

• 오일러의 정리 : 연결된 평면 그래프 조건

  • 정점의 수 : v
  • 연결선의 수 : e
  • 면의 수 : f
  • v - e + f = 2

특수 그래프

• 가중 그래프 : G의 각 연결선에 0보다 큰 수가 할당되었을 때의 값을 가중값이라 하고, 가중값을 갖는 그래프를 말한다.
• 동형 그래프 : 두 그래프 G와 G’가 있을 때 전단사 함수 f:V → V’ 가 존재하고 인 경우 f를 동형이라 하고 동형인 두 그래프를 동형 그래프라 한다.
• 평면 그래프 : 평면상에서 어떤 연결선들도 서로 교차할 수 없도록 그려진 하나의 그래프 (동형으로 변형해서 교차되지 않으면 평면 그래프이다.)
  • 평면의 개수를 셀 때 그래프 바깥의 평면도 세야 한다.
• 완전 그래프 : 모든 정점들의 쌍 사이에 연결선이 존재하는 그래프
  • 즉, 각 정점이 다른 모든 정점들과 연결되는 그래프
  • n 개의 연결선을 갖는 완전 그래프의 연결선의 개수 n(n-1)/2
• 정규 그래프 : 모든 정점의 차수가 k이면 k차 정규 그래프라 한다.
• 이분 그래프 : 집합 X와 Y = V - X로 나누어져 연결선이 X와 Y내의 정점의 쌍으로 연결된 그래프
• 완전 이분 그래프 : X, Y의 모든 정점 사이에 연결선이 존재하는 그래프
• 방향 비사이클 그래프(Directed Acyclic Graph : DAG) : 사이클이 없는 방향 그래프
  • 트리보다는 일반적이나 임의의 방향 그래프보다는 제한적이다.

그래프의 응용

• 최단 경로 문제 : 가장 짧은 거리의 경로를 찾는 문제

• 출발점 : 경로의 시작점

• 도착지 : 경로의 목적지

• 다익스트라 알고리즘 : 출발점으로부터 목적지까지의 최단 경로 찾기

• 해밀턴 순회 응용 : 순회판매원 문제

• 그래프 탐색

  • 깊이 우선 탐색
  • 너비 우선 탐색

그래프와 색칠 문제

• 색칠 문제 : 어떤 인접한 두 영역도 같은 색이 되지 않도록 칠하는 문제

• 그래프 G를 색칠하는데 필요한 색의 수 x(G), G의 색칠 수

• 쌍대 그래프 : 지도 색칠 문제는 그래프 정점 색칠 문제와 같다.

• 그래프 G에 대해 다음은 서로 동치이다.

1. G는 두 가지 색으로 칠할 수 있다.
2. G는 이분 그래프이다.
3. G의 모든 순환은 짝수의 길이를 가진다.

• 4색 문제 : 모든 평면 그래프는 4가지 색으로 색칠할 수 있다.