평면 그래프: 그래프의 모든 변(간선)이 서로 교차하지 않게 그릴 수 있는 그래프를 평면 그래프라고 함.
평면 그래프가 아닌 예시: 완전 그래프, 완전이분그래프 등은 변(간선)이 교차하는 그래프이기 때문에 평면 그래프가 아님.
평면 그래프의 예시(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로 초기화를 진행함.
최종 과정: 해당 과정에서 인접한 정점 중 가중치가 가장 짧은 정점을 선택하는 과정에선 선택된 정점들의 집합 배열을 만들어 따로 저장을 하게 되는데, 이때 해당 선택 배열에 저장 된 정점들의 개수와 그래프의 정점의 개수가 동일해질때 모든 정점들을 다 거쳐서 최단 경로를 구했다고 판단해 반복이 종료됨.
