2023-12-07DiscreteStructure-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 가지 색으로 색칠할 수 있다.