[이산수학] 10강 - 그래프(2)

✅ 1. 그래프의 탐색

(1) 평면 그래프

• 평면 그래프: 그래프의 모든 변(간선)이 서로 교차하지 않게 그릴 수 있는 그래프를 평면 그래프라고 함.

• 평면 그래프가 아닌 예시: 완전 그래프, 완전이분그래프 등은 변(간선)이 교차하는 그래프이기 때문에 평면 그래프가 아님.

• 평면 그래프의 예시(1): 3-정규그래프는 평면 그래프로 변(간선)이 교차하지 않음. 또한, K4(완전그래프)와 동일한 완전 그래프로도 볼 수 있기 때문에 K4 또한 평면 그래프로 볼 수 있음.
• K4(완전그래프) 평면 그래프인 이유: 교차된 한 변(간선)을 밖으로 돌아가서 연결되도록 하면 평면 그래프이기 때문임.

• 평면 그래프의 예시(2): K5(완전그래프) 에서 한 변(간선)을 제거한 그래프는 위와같이 평면 그래프로 만들 수 있음.

(2) 오일러의 공식

• 오일러 공식을 이해하기 위한 면(Face) 정의: 연결된 평면 그래프에서 변(간선)에서 만들어지는 사이클을 경계로 형성된 공간을 의미하며, 쉽게 말해 위의 f1, f2, f3, f4 의 사이클 공간 자체가 하나의 면이 되는 것임.

• 오일러의 공식: 꼭지점의 수(v), 변의 수(e), 면의 수(f) 에 대한 공식 v - e + f = 2 가 항상 나오며, 이게 오일러 공식임.

(3) 4색 정리

• 4색 정리: 평면에 그려진 어떤 지도라도, 국경을 맞댄 이웃 나라끼리 서로 다른 색을 칠할 때 딱 4가지 색만 있으면 모든 나라를 구별해서 칠할 수 있는 정리를 의미한다.

• 4색 정리 - 평면 그래프 관점: 4색 정리의 또 다르게 정의를 내리면, 평면 그래프가 주어졌을 때, 각 꼭지점에 대하여 인접한 꼭지점과 서로 다른 색으로 칠하는데 필요한 색은 4가지면 충분하다로 정의를 내릴 수도 있음.

(4) 오일러 투어

• 오일러 트레일: 트레일 자체의 개념은 정점의 중복은 허용이지만, 변(선)에 대한 중복은 허용을 하지 않는다는 개념이며, 반드시 모든 변을 지나갈 필요는 없는 상위적 개념이지만, 오일러 트레일은 모든 변을 반드시 한 번씩만 지나가야 하는 개념임. 즉, 오일러 트레일과 트레일의 차이점으로 볼 수 있음. ( 정점의 중복 허용임 )
• 오일러 투어: 그래프에 있는 모든 변(선)을 단 한번씩만 거쳐서, 처음 출발했던 꼭지점으로 다시 돌아로는 경로를 의미함.
• 즉, 시작점과 종점이 같은 오일러 트레일이기 때문에, 닫힌 오일러 트레일로도 볼 수 있음.
• 정리: "모든 변(간선)을 단 한 번씩만 지나야 한다"는 조건은 오일러 투어에 적용되는 절대적인 규칙인 것임.

(5) 오일러 그래프 정리

• 오일러 그래프: 오일러 투어를 가지는 그래프를 오일러 그래프라고 부름.
• 오일러 그래프 정리: 연결 그래프가 오일러 투어를 가지기 위한 필요충분 조건은 그래프의 모든 꼭지점의 차수는 짝수다.
• 즉, 오일러 투어를 가지기 위해서는 연결 그래프(연결 성분이 하나인 그래프)에서 모든 꼭지점의 차수는 짝수여야 함.

• (1) 연결 그래프가 오일러 투어를 가지면 모든 꼭지점의 차수는 짝수 증명: 들어가는 간선이 존재한다면, 나가는 간선이 존재해야 하며, 그 이유는 중복된 간선의 사용은 허용하지 않는 트레일 구조이기 때문임.

• (2) 연결 그래프 G의 모든 꼭지점의 차수는 짝수이면 G는 오일러 그래프 증명: (1) 번의 내용을 토대로 결론을 내리면 모든 꼭지점의 차수가 짝수면, 오일러 투어의 규칙인 간선의 중복 미허용과 모든 간선의 방문을 통해서 나가는 길과 들어오는 길을 따로 만드는 짝수로 해당 명제는 참임을 증명함.
• 결과적으로 오일러 투어를 가지는 해당 그래프 G는 오일러 그래프로 볼 수 있음.

• 오일러 그래프 알고리즘 단계별 정리: 
• 1단계: G의 임의의 꼭지점 v를 고르기.
• 2단계: v에서 시작하고 v에서 끝나는 임의의 작은 사이클 C를 선택
• 3단계: 임의의 작은 사이클 C가 오일러 투어이면 즉, 모든 간선을 방문하고, 출발점으로 돌아온 상태이냐를 보고 맞으면 증명을 끝내고 만약 아니라면 아래 과정을 반복
• 3-1단계: 임의의 작은 사이클 C의 해당하는 모든 변을 제거한 나머지를 가지는 새로운 G' 그래프를 만듦
• 3-2단계: 버려진 C와 G' 가 공유하는 꼭지점 중 하나를 고르고 w로 정의를 함.
• 3-3단계: w에서 시작하고 w에서 끝나는 임의의 사이클 C'을 선택
• 3-4단계: 기존의 C와 새로 선택된 C'을 합쳐서 새로운 C를 만들고, 3단계로 돌아가서 증명이 참인지에 대한 검증을 반복함.
• 즉, 작은 임의의 면(사이클을 가지는 변들)을 만들고, 오일러 투어인지 보고, 아닐 경우 해당 면의 인접한 꼭지점 아무거나 잡아서 임의의 면 또 만들면서 반복하는 느낌임.

• 오일러 투어 찾기 예제: a, b, c, d 하나의 면을 v로 두고, 오일러 투어의 조건을 만족하는지 보면 e, f, h, g 가 있어서 조건을 만족하지 못하기 때문에 e, f, h, g 를 w로 두고, w와 v를 합치면 오일러 투어를 만족함.

(3) 해밀턴 경로

• 해밀턴 경로: 그래프의 모든 꼭지점들을 한 번씩만 지나는 경로를 의미한다.
• 해밀턴 사이클: 닫힌 해밀턴 경로를 의미하며, 시작점과 종점이 같은 해밀턴 경로이다.
• 정리하면, 그래프의 모든 꼭지점들을 한 번씩만 모두 지나는 경로만 존재하면 해밀턴 경로이며, 만약 시작점과 종점이 같은 해밀턴 경로라면 이것은 해밀턴 사이클로 부름.

• 해밀턴 경로 예제: 위의 왼쪽의 그래프 탐색이 해밀턴 경로이며, 모든 정점을 방문을 모습임.
• 해밀턴 사이클 예제: 오른쪽 그래프 탐색이 해밀턴 사이클이며, 모든 정점을 방문한 뒤 시작점으로 돌아온 모습임.

• 해밀턴 경로 및 사이클 예제: Herschel Graph 는 해밀턴 경로는 존재하나, 해밀턴 사이클(출발점으로 돌아오는 경로)는 존재하지 않는 특징이 있음.
• 12면체 그래프는 해밀턴 경로도 되고, 해밀턴 사이클도 가능함.

---

✅ 2. 그래프의 활용

(1) 가중 그래프

• 가중 그래프: 그래프의 각 변(간선)에 실수값이 붙여진 그래프를 의미하며, 변에 부여된 값은 가중치 라고 함.

• 위와 같이 꼭지점(정점)을 연결하는 변(간선)에 가중치의 값이 부여된 그래프(가중 그래프)로 볼 수 있음.

• 가중 그래프의 쓰임새: 최단경로 문제 또는 최소 신장 트리 문제에 가중 그래프의 가중치를 기반해서 쓰임.
• 최단경로 문제: 출발지와 도착지가 주어지고, 그 경로상에서 가장 빠른 경로를 찾는 문제임.

• 최소 신장 트리 문제: 그래프 G 안에서 총 가중치가 가장 작은 사이클이 없는 연결 그래프인 신장 트리를 구하는 문제임.

(2) 최단경로 문제 - 다익스트라 알고리즘

• 다익스트라 알고리즘: 해당 알고리즘은 최단 경로 문제를 구하기 위한 대표적인 알고리즘임. ( 그 외에도 여러개 있음. )
• 과정1: 각 정점에 도달하는 임의의 최단거리 배열을 만들어두고, 배열의 각 원소들을 무한으로 초기화
• 과정2: 만약 시작 정점을 a로 잡는다면, 해당 시작점의 최단거리 배열의 원소는 0으로 초기화. ( 즉, a = 0 )
• 과정3: a의 인접한 정점 b, e 를 보고 최단거리 배열의 b, e에 해당하는 배열의 원소를 각 2와 4로 초기화
• 과정4: a의 인접한 정점 중 가장 짧은 거리는 a - b(가중치:2) 이기 때문에, b의 인접한 정점(a,c,d,e,f)의 값을 가중치의 값에 맞게 최단거리 배열의 값을 초기화
• 과정5: b의 인접한 정점 중 가장 짧은 거리는 b-c(가중치:1) 이기 때문에, c의 인접한 정점은 c-d(가중치:3) 밖에 없으므로, 최단거리 배열 d의 값을 초기화를 시키는데, 이때 d는 과정4에서 이미 5로 초기화가 되어있는데 상태인데, 5보다 4가 작기 때문에 4로 초기화를 진행함.
• 최종 과정: 해당 과정에서 인접한 정점 중 가중치가 가장 짧은 정점을 선택하는 과정에선 선택된 정점들의 집합 배열을 만들어 따로 저장을 하게 되는데, 이때 해당 선택 배열에 저장 된 정점들의 개수와 그래프의 정점의 개수가 동일해질때 모든 정점들을 다 거쳐서 최단 경로를 구했다고 판단해 반복이 종료됨.