[이산수학] 9강 - 그래프(1)

✅ 1. 기본사항

(1) 그래프 소개

• 1737년 쾨니히스베르크 도시에 다리 건너기 문제를 당시 천재 수학자 오일러가 풀려고 접근함.
• 이때, 오일러가 해당 문제를 풀 때, 본질만 남기고 다 지우는 추상적인 방법을 사용하는데, 결과로 나온 것이 그래프임.
• 해당 그래프를 활용해서 문제를 보니, 답이 없는 문제임을 알아낼 수 있었음.

(2) 주요 용어

• 그래프 G = (V, E) 들로 구성이 되어있으며, V = 정점들의 집합, E = 간선들의 집합임.
• 인접: 연결된 두 꼭지점은 서로 인접한다고 함.
• 병렬 변: 두 꼭지점을 연결하는 변이 여러개 있는 경우를 의미함. ( ex: v1, v2 를 잇는 간선이 e1 뿐 아니라 e3.. 등 있을 때 )
• 루프: 동일한 꼭지점을 연결하는 변을 의미하며, 꼭지점 v1에 동그랗게 다시 자신을 가리키는 간선을 의미함.
• 고립된 꼭지점: 어떠한 변도 연결되지 않은 꼭지점을 의미하며, 쉽게 말해 간선이 존재하지 않은 꼭지점을 의미함.

• 그래프 예제1: (1) v1과 인접한 꼭지점은 루프가 있으므로, v1 과 v2 둘 다 인접함. (2) 루프를 가지는 꼭지점은 v1 임. (3) 병렬 변은 여러개 간선을 가지는 꼭지점간의 간선이므로, e2, e3 임. (4) 고립된 꼭지점은 v4 임.

• 그래프 예제2: 정점간의 간선 연결이 동일할 때, 동일하기 때문에 4번째 그래프가 동일하지 않은 그래프임.
• 동형 그래프: v1, v2, e1, e2, .. 와 같이 그래프의 꼭지점 및 변의 이름을 제거하고 모양만 봤을 때 동일한 것들은 동형이라함.

(3) 주요 용어 - 방향 그래프, 무향 그래프

• 방향 그래프: 변(간선)이 방향을 가지고 있는 그래프를 의미함.
• 무향 그래프: 무방향 그래프로도 불리며, 변(간선)이 방향을 가지고 있지 않은 그래프를 의미함.

(4) 주요 용어 - 단순 그래프, 부분 그래프, 신장 부분 그래프

• 단순 그래프: 루프와 병렬 변을 가지지 않는 무향 그래프를 의미함. ( 루프, 병렬 변 없는 무방향 그래프 )
• 단순 그래프의 반대는 다중 그래프로 볼 수 있음.

• 부분 그래프: 원래 그래프 G에서 점도 몇 개 내 맘대로 고르고, 선도 몇 개 내 맘대로 골라서 대충 원본의 일부만 떼어내 만든 그래프를 의미하며, 수학에서 말하는 '부분집합'과 같은 개념임.
• 당연히 없는 점이나 없는 선을 새로 만들어낼 수는 없으며, 선을 고를 때는 그 선에 연결된 점도 함께 골라야 그래프가 성립됨.
• 신장 부분 그래프: 원본 그래프의 모든 점을 이용한 부분 그래프를 신장 부분 그래프라고함.

• 부분 그래프 예시: 그래프 G에서 e1을 포함한 모든 부분 그래프는 위와같이 5가지가 나올 수 있음.

(5) 주요 용어 - 그래프 차수

• 차수: 꼭지점(정점)의 인접한 변(간선)의 개수를 의미함. ( ex: v1의 차수는 변의 개수가 2개이므로, 차수는 2임. )
• 총 차수: 그래프 G에 속한 모든 꼭지점(정점)의 차수의 합을 의미함.
• 진입차수: 꼭지점(정점) v 로 들어오는 변(간선)의 수를 의미함.
• 진출차수:  꼭지점(정점) v 에서 나가는 변(간선)의 수를 의미함.

• 그래프 차수 예시: 각 정점 a,b,c,d 의 총 차수는 각 3,4,3,3 이 되며, 마지막 그래프 G의 총 차수는 14가 됨.

• 악수 정리: 홀수 번 악수한 사람들의 전체 악수 횟수의 총합은 항상 주고 받고니까, 2배가 되므로 짝수가 될 수 있는데, 이때 홀수 번 악수한 짝수 명 있어야만 해당 정리가 성립이 되는 것임.
• 쉽게 말해, 차수가 홀수인 정점들의 개수는 항상 짝수개가 된다는 작은 정리를 의미하는 것임.

• 진입차수 예제: v1의 경우 v1(루프), v2, v3(2개) 이므로, 총 4개가 될 수 있으며, 그 나머지도 비슷한 원리로 구할 수 있음.
• 진출차수 예제: 진입차수의 반대로 나가는 선의 개수로 보면 됨.

(6) 그래프 탐색

• 그래프 탐색: 꼭지점 v0 에서 시작해 vk 에 도착하는 꼭지점과 변들을 순서대로 나열한 것을 의미함.
• 위와 같이, 정점에서 화살표로 가는 것 또는 간선만을 구성해서 표현을 할 수 있음.
• v0 이 vk 로 출발 지점에서 출발해 제자리로 돌아왔다는 의미로, 닫힌 워크라고 부름.

(7) 그래프 탐색 - 워크, 트레일, 경로 개념

• 워크(Walk): 워크 자체는 아무 제약없이, 단순히 정점과 변을 번갈아가며 이동하는 느낌으로, 갔던 길을 또 가도 되고 방문했던 정점을 또 방문해도 됨. ( 제약이 없음. )
• 트레일(Trail): 변(간선) 중복 금지를 의미하며, 워크 중에서 한 번 지나간 간선(변)은 다시 지나가지 않는 규칙을 추가한 것이지만, 정점은 다시 방문해도 됨.
• 경로(Path): 정점 중복 금지를 의미하며, 트레일 중에서 한 번 밟은 땅(정점)은 절대 다시 밟지 않는다는 규칙을 추가한 것이며, 정점을 중복해서 밟지 않기 때문에 간선(변) 또한 중복될 일이 없음. ( 매우 엄격하다고 보면 됨. )
• 즉, 집합 관점으로 보면, 규칙이 까다로울수록 조건을 만족하는 대상이 적어지기 때문에 walk 안에 trail 이 있고, trail 안에 path가 있는 집합으로 볼 수 있음.

• 워크 예시: 위와 같이 v1 에서 v4 까지의 워크는 e1,e2,e2,e3,e4 로 갈수가 있음.
• 트레일 예시: 위와 같이 v1 에서 v4 까지의 트레일은 e1,e2,e3,e4 로 갈수가 있음. ( 간선의 중복 허용 x )
• 경로 예시: v1 에서 v4 까지의 경로는 e1,e3,e4 로 갈수가 있음. ( 정정의 중복 허용 x => 자연스럽게 간선도 중복 x )
• 경로에서 e2 를 방문하지 않는 이유: e1 에선 v1 -> v2 형태로 정점을 방문 할텐데, e2 간선을 거치게 되면 v2 를 한 번더 거치는 중복이 발생하기 때문임.

• 닫힌 트레일: W(워크)가 트레일 이면서, 출발 정점으로 다시 돌아온 경우임.
• 닫힌 경로: W(워크)가 트레일 이면서, 경로인 경우와 출발 정점으로 다시 돌아온 경우를 의미함.

• v1 에서 v1 까지의 시작 정점과 끝 정점이 같은 경우를 닫혀있다고 보고 있음.
• 이 경우에서 워크, 트레일, 경로 조건에 따라서 갈리는 것임. ( 참고: 닫힌 경로는 사이클로도 볼 수 있음. )

(8) 그래프 탐색 - 연결, 연결 성분, 연결 그래프

• 연결: 그래프 상에서 u 에서 v 로 가는 경로가 존재하면 해당 u 와 v 는 연결되어 있다고 함.

• 연결성분: 그래프 내에서 V(정점)들은 서로 연결되고 다른 집합과 겹치지 않는 꼭지점들의 집합 V1, v2, ... , Vn 으로 나눌 수 있는데, 이러한 집합들이 그래프 G의 연결성분이 되는 것임.
• 연결 그래프: 연결 성분의 집합이 곧 V인 경우로, 오직 하나의 연결 성분으로만 구성이 되어있으며, 이것은 곧 그래프의 정점 전체가 연결이 되어있다고 볼 수 있음. ( 이러한 구조를 띄는 그래프를 연결 그래프라 함 )

• (1) 그래프 G1 의 연결 성분은 V1 으로 모두 연결된 경우이며, 이것은 연결 그래프로 볼 수 있음.
• (2) 그래프 G2 의 연결 성분은 V1, V2, V3 가 있으며, 3개의 연결된 요소로 나뉘기 때문에 연결 그래프가 아님.

• 단순 연결 그래프는 정점의 루프가 없어야 하며, 병렬변이 없어야하며, 방향이 없어야 함.
• (1) 번은 루프와 병렬변이 있기 때문에 => 단순 연결 그래프가 아님. ( 연결 그래프는 맞음. )
• (2) 번은 병렬변이 있기 때문에 => 단순 연결 그래프가 아님. ( 연결 그래프는 맞음. )
• (3) 번은 같은 방향으로가는 병렬변이 없고, 루프가 없기 때문에 => 단순 연결 그래프임.
• (4) 번은 루프, 병렬변이 없지만, 두 개의 연결성분을 가지기 때문에 연결 그래프로 볼 수 없기 때문에 => 단순 연결 그래프 X.

---

✅ 2. 그래프의 종류

(1) 완전 그래프

• 완전 그래프: 임의의 두 꼭지점을 꺼내서 연결하려고 할 때, 항상 두 꼭지점을 연결하는 변이 존재하는 그래프를 의미함.
• 쉽게 말해, 임의의 두 꼭지점을 연결하는 간선이 존재해야 하기 때문에 모든 정점은 인접해 있어야 하며, 부수되어 있어야함.

• 완전 그래프 예제: 위의 예시와 같이 완전 그래프는 모든 정점이 인접해 있는 구조를 띄고 있음.
• 위와 같은 특성이 존재함. ( 모든 꼭지점 차수는 n - 1 )

(2) 이분 그래프

• 이분 그래프: 그래프 G 의 V들의 그룹을 2개로 분할 했을 때, 각 그룹의 정점들간의 간선이 존재하지 않는 경우 해당 그래프를 이분 그래프라고 정의함.

• 이분 그래프 예제: 위와 같이 두 그룹 내에서는 간선이 존재하지 않아야 하며, 두 그룹간의 정점은 연결되어 있는 형태임.

(3) 완전 이분 그래프

• 완전 이분 그래프: 이분 그래프의 특성에 따라 그래프의 정점을 두 그룹으로 나누고, 나뉜 각 그룹 내에서는 정점간의 간선 연결이 없어야 하며, 한 그룹의 모든 정점이 다른 그룹의 모든 정점과 전부 연결된 그래프를 의미함.

• 완전 이분 그래프 예제: 위와 같이 두 개로 분할 된 정점들에서 각 그룹안에서는 연결이 없는 형태이며, 한 그룹의 모든 정점이 다른 구릅의 모든 정점과 연결된 모습을 볼 수 있음. ( 위와같이 K1,3 / K2,3 형식으로 표현함. )

(4) k-정규 그래프

• 정규 그래프: 그래프 G의 모든 꼭지점(정점)들이 동일한 수의 인접한 꼭지점(정점)을 갖는 경우 G를 정규 그래프라고 말함.
• 즉, 정규 그래프 G는 모든 꼭지점이 동일한 차수를 가질 수 있다고도 볼 수 있음.
• k-정규 그래프: 모든 정점의 차수가 정확히 k가 될 수 있기 때문에 k인 그래프라고 해서 k-정규 그래프라고도 부름.

• 0-정규 그래프: 모든 정점이 0개의 차수를 가지는 정규 그래프
• 1-정규 그래프: 모든 정점이 1개의 차수를 가지는 정규 그래프
• 2-정규 그래프, 3-정규 그래프: 동일하게 모든 정점이 2,3개의 차수를 가지는 정규 그래프
• 해당 3-정규 그래프는 완전 그래프(모든 정점이 모든 정점과 연결된 그래프)라고도 볼 수 있음.

---

✅ 3. 그래프의 표현

(1) 발생행렬

• 발생행렬: 그래프의 꼭지점(정점)과 변(간선)의 특징을 행렬로 표현한 것을 의미한다. ( MI = (aij) 로 표현함 )
• 쉽게 말해, 꼭지점(정점) = 행 / 변(간선) = 열 구조로 발생행렬을 만들 수 있으며, 내부는 부울행렬 구조로 연결이 되어있을 때를 발생함으로 보고 원소 값을 1로 표현하며, 그 밖의 경우는 0으로 표현함.
• 그래프를 발생행렬로 표현을 하면 당연히 V(정점) * E(간선) 의 크기의 부울행렬로 표현함.

• V(정점)을 행으로 표현하기 때문에 v1,v2,v3 의 행과 e1,e2,e3,e4 의 열을 가지는 3 * 4 부울 행렬로 표현함.
• 정점에 부수된 간선이라면 1로 표현 나머지는 0으로 표현함.

(2) 인접행렬

• 인접행렬: 발생행렬과는 다르게, 꼭지점(정점)만을 가지고, 행과 열을 표현한 행렬임.
• 즉, 정점의 개수 * 정점의 개수 ( V * V ) 크기의 행렬로 만들어지며, 행렬의 원소로는 연결 된 간선의 개수 즉, 연결 개수가 원소고 들어가게 됨.

• 인접행렬 예제: 방향 그래프의 경우에 인접 행렬을 만든다면, 위와 같이 정점간의 연결 된 간선의 개수가 원소로 들어감.

(3) 인접 리스트

• 인접 리스트: 그래프의 각 정점의 인접하는 정점들을 차례대로 연결 리스트로 표현한 것을 의미함.

• 예제: 단순히 그래프의 각 정점들을 리스트로 두고, 각 요소들에 인접한 정점들을 연결 리스트로 구성하는 것임.