이산수학 9. 그래프

1. 그래프의 개념

• 그래프(graph, \(G=(V, E)\)): 정점의 집합 \(V\)와 변의 집합 \(E\)로 구성된 구조
  • 정점 \(v_i\)와 \(v_j\)는 인접(adjacent): \(v_i\)와 \(v_j\)를 연결하는 변이 존재
  • 변 \(e_k\)는 정점 \(v_i\)와 \(v_j\)에 근접(incident): \(e_k\)는 \(v_i\)와 \(v_j\)를 연결
• 단순 그래프(simple graph): 임의의 두 정점 사이에 오직 하나의 변이 있는 그래프
• 다중 그래프(multi graph): 임의의 두 정점 사이에 두 개 이상의 변이 있는 그래프
• 방향 그래프(directed graph, \(G = <V, E>\)): 정점 사이에 순서가 존재하여 화살표를 이용해 표현하는 그래프
• 가중치 그래프(weighted graph): 각 변에 가중치가 부여된 그래프
  • \(W[v_i, v_j]\): \(v_i\)와 \(v_j\)에 근접하는 변에 부여된 가중치
• 차수(degree, \(d(v)\)): \(v\)에 근접하는 변의 개수
  • 외차수(out-degree, \(d_{out}(v)\)): \(v\)를 시작점으로 하는 화살표의 개수
  • 내차수(in-degree, \(d_{in}(v)\)): \(v\)를 끝점으로 하는 화살표의 개수
  • 모든 정점의 차수의 합은 변의 개수의 2배
  • 차수가 홀수인 정점의 개수는 짝수

2. 그래프의 종류

• 부분 그래프(subgraph): \(V^\prime \subseteq V\)이고 \(E^\prime \subseteq E\)인 정점과 변으로 구성된 \(G \neq G^\prime\)인 그래프
• 신장부분 그래프(spanning subgraph): \(V^\prime = V\)이고 \(E^\prime \subseteq E\)인 정점과 변으로 구성된 그래프
• 동형 그래프(isomorphic graph): \(G_1 = (V_1, E_1)\)과 \(G_2 = (V_2, E_2)\)에 대한 함수 \(f: V_1 \rightarrow V_2\)가 \(u, v \in V_1\)에 대하여 \((u, v) \in E_1\)이면 \((f(u), f(v)) \in E_2\)를 만족하는 전단사 함수일 때, 두 그래프 \(G_1\), \(G_2\)
• 연결 그래프(connected graph): 임의의 정점 \(u, v\) 사이에 경로가 있는 그래프(소외된 부분 그래프가 없는 그래프)
• 경로(path): 임의의 정점 \(u, v\) 사이에 가능한 길 중에서 같은 변을 두 번 이상 포함하지 않는 길
• 평면 그래프(planar graph): 연결 그래프를 평면에 그릴 때 어떤 변도 교차하지 않도록 그릴 수 있는 그래프
• 오일러 공식: 평면 그래프에서 정점의 수를 \(v\), 변의 수를 \(e\), 영역의 수를 \(s\)라고 할 때, \(v - e + s = 2\)
• 정규 그래프(regular graph, \(k\)-정규그래프): 모든 정점의 차수가 \(k\)로 같은 그래프
• 완전 그래프(complete graph, \(K_n\)): 모든 정점 사이에 변이 존재하는 그래프
• 완전이분 그래프(complete bipartite graph, \(K_{m, n}\)): 정점 집합 \(V\)에서 \(V = V_1 \cup V_2\)와 \(V_1 \cap V_2 = \varnothing\)을 만족하는 \(V_1\)과 \(V_2\)에 대해, 모든 변이 \(V_1\)의 한 정점에서 \(V_2\)의 한 정점으로 연결되는 그래프
• 이분 그래프(bipartite graph): 정점 집합 \(V\)에서 \(V = V_1 \cup V_2\)와 \(V_1 \cap V_2 = \varnothing\)을 만족하는 \(V_1\)과 \(V_2\)에 대해, 어떤 변이 \(V_1\)의 한 정점에서 \(V_2\)의 한 정점으로 연결되는 그래프

3. 그래프의 표현

• 인접 행렬(adjacency matrix, \(A_G\))

  \[a_{ij} = \begin{cases} \text{해당 정점에 근접하는 변의 수}&,(v_i, v_j)\in E\\ 0&, (v_i, v_j) \notin E\\ \end{cases}\]

• 인접 리스트(adjacency list): 각 정점에 인접하는 정점들을 연결리스트로 표현한 것

4. 오일러와 해밀턴

• 순환(cycle): 연결 그래프에서 시작하는 정점과 끝나는 정점이 같은 경로
• 길이(length): 경로를 구성하는 변의 수
• 오일러 경로(Eulerian path): 임의의 정점에서 시작하여 모든 변을 한 번씩만 지나는 경로
  • 오일러 순환(Eulerian cycle): 오일러 경로이면서 순환하는 경로
  • 오일러 그래프(Eulerian graph): 오일러 순환을 가지는 그래프
    • 정점 중 차수가 홀수인 정점의 수가 0 또는 2개인 그래프
• 해밀턴 경로(Hamiltonian path): 모든 정점을 한 번씩만 지나는 경로
  • 해밀턴 순환(Hamiltonian cycle): 해밀턴 경로이면서 순환하는 경로
  • 해밀턴 그래프(Hamiltonian graph): 해밀턴 순환을 가지는 그래프