[이산 수학] 그래프의 종류

그래프의 종류

• 그래프는 정점과 변이 어떻게 구성되는지에 따라 종류를 구분한다.

 

부분 그래프와 신장 부분 그래프

부분 그래프(Subgraph)

그래프 $G = (V, \; E)$ 에 대하여, $V' ⊆ V$ 이고 $E' ⊆ E$ 인 정점과 변으로 구성된 $G \ne G'$ 인 그래프 $G' = (V', \; E')$

 

신장 부분 그래프(Spanning Subgraph)

그래프 $G = (V, \; E)$ 에 대하여, $V' = V$ 이고 $E' ⊆ E$ 인 정점과 변으로 구성된 그래프 $G' = (V', \; E')$

• 부분 그래프 `G'` 은 어떤 그래프 `G` 에 포함된 정점과 변의 일부 또는 전체로 구성된 그래프이다.
• 부분 그래프 `G'` 을 구성하는 정점의 집합과 변의 집합은 각각 그래프 `G` 의 정점의 집합과 변의 집합의 부분 집합이다.
• 특히 그래프 `G` 의 모든 정점과 일부 변으로 구성되는 신장 부분 그래프는 부분 그래프의 한 종류이다.
• 이처럼 부분 그래프와 신장 부분 그래프는 그래프 `G` 의 일부 또는 전체 정점과 변으로 표현되므로 다양한 형태가 존재한다.

 

예

$$G = (V, \; E) \\ V = \{A, \; B, \; C, \; D \} \\ E = \{(A, B), (A, D), (B, C), (B, D) \}$$

• 그래프 `G` 와 `G` 의 부분 그래프, 신장 부분 그래프를 그리면 다음과 같다.

그래프 G의 부분 그래프와 신장 부분 그래프

• `G` 의 부분 그래프나 신장 부분 그래프는 위에서 구한 것 외에도 다양하다.
• 부분 그래프와 신장 부분 그래프를 비교해보면, 부분 그래프는 그래프 `G` 의 일부 정점만을 포함해도 되지만, 신장 부분 그래프는 반드시 `G` 의 모든 정점을 포함해야 한다.
• 반면, 다음과 같은 그래프는 그래프 `G` 의 변의 집합 `E` 에 변 `(A, C)` 나 `(C, D)` 가 포함되지 않으므로 그래프 `G` 의 부분 그래프도, 신장 부분 그래프도 아니다.

그래프 G와 상관 없는 그래프

 

동형 그래프(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}$

• 두 그래프 $G_{1}$ 과 $G_{2}$ 가 동형 그래프이려면 그래프 $G_{1}$ 의 정점 집합 $V_{1}$ 과 그래프 $G_{2}$ 의 정점 집합 $V_{2}$ 가 상등이고, 그래프 $G_{1}$ 의 변 집합 $E_{1}$ 과 그래프 $G_{2}$ 의 변 집합 $E_{2}$ 가 상등이어야 한다.
• 그래서 그래프 $G_{1}$ 과 $G_{2}$ 의 수학적 표기는 정확하게 일치한다.

 

예

동형 그래프인 예와 아닌 예

• 그래프 `A, B, C` 각각의 정점 집합 $V_{A}, V_{B}, V_{C}$ 와 변 집합 $E_{A}, E_{B}, E_{C}$ 는 다음과 같다.

$$A = (V_{A}, E_{A}), \quad V_{A} = \{a, b, c, d \}, \quad E_{A} = \{(a, b), (a, c), (a, d), (b, c), (b, d), (c, d) \} \\ B = (V_{B}, E_{B}), \quad V_{B} = \{a, b, c, d \}, \quad E_{B} = \{(a, b), (a, c), (a, d), (b, c), (b, d), (c, d) \} \\ C = (V_{C}, E_{C}), \quad V_{C} = \{a, b, c, d \}, \quad E_{C} = \{(a, b), (a, d), (b, c), (b, d), (c, d) \}$$

• 위 내용으로 확인할 수 있는 그래프 `A, B, C` 의 정점 집합과 변 집합 사이의 상등 관계는 다음과 같다.

$$V_{A} = V_{B}, \quad V_{A} = V_{C}, \quad V_{B} = V_{C} \\ E_{A} = E_{B}, \quad E_{A} \ne E_{C}, \quad E_{B} \ne E_{C}$$

• 위의 상등 관계에서 알 수 있듯이, 그래프 `A` 와 `B` 는 정점 집합과 변 집합이 모두 상등이므로 그래프 `A` 와 `B` 는 동형 그래프이다.
• 하지만, 그래프 `C` 는 변 집합이 다른 그래프의 변 집합과 상등이 아니므로 그래프 `C` 는 그래프 `A` 나 `B` 와 상등이 아니다.

 

연결 그래프(Connected Graph)

그래프 $G = (V, \; E)$ 에 포함되는 임의의 정점 $u, \; v$ 사이에 경로가 있는 그래프

 

경로(Path)

그래프 $G = (V, \; E)$ 에 포함된 임의의 정점 $u, \; v$ 사이에 가능한 길 중에서 같은 변을 두 번 이상 포함하지 않는 길

※ 길(Walk) : 그래프 $G = (V, \; E)$ 에서 정점 $v_{i}$ 와 $v_{i + 1}$ 에 근접하는 변을 $e_{i}$ 라고 할 때, $v_{1}$ 에서 시작하여 $v_{k}$ ($k > 1, \; k \in N$) 에 도착하는 정점과 변의 나열
$$v_{1}, e_{1}, v_{2}, e_{2}, v_{3}, \cdots, v_{k-1}, e_{k-1}, v_{k} \quad \text{또는} \quad v_{1} → v_{2} → \cdots → v_{k-1} → v_{k}$$

• 연결 그래프는 그래프를 구성하는 임의의 정점 사이에 경로가 있어야 한다.
• 만약 두 정점을 직접 연결하는 변이 존재하지 않더라도 다른 정점과 변을 거쳐서 두 정점이 연결되면 두 정점 간에 경로가 존재하여 연결 그래프가 된다.

 

예

연결 그래프인 예와 아닌 예

• 그래프 `A` 는 모든 정점 사이에 경로가 존재하므로 연결 그래프이다.
  • 예를 들어, 정점 `a` 와 `d` 사이에 `a→d, a→b→d`, `a→c→b→d` 와 같은 경로가 있다.
• 그러나 그래프 `B` 의 경우 정점 `a, b, c, d` 와 정점 `e, f` 사이에 경로가 전혀 없다.
  • 그러므로 그래프 `B` 는 연결 그래프가 아니다.

 

평면 그래프(Planar Graph)

연결 그래프 $G = (V, \; E)$ 를 평면에 그릴 때 정점이 아닌 위치에서는 어떤 변도 교차하지 않도록 그릴 수 있는 그래프

• 평면 그래프는 정점이 아닌 위치에서 서로 다른 변이 교차하지 않도록 그릴 수 있는 모든 그래프를 말한다.

 

예

평면 그래프인 예와 아닌 예

• 그래프 `A` 는 모든 변이 정점이 아닌 위치에서는 교차하지 않으므로 당연히 평면 그래프이다.
• 그래프 `B` 는 변 `(a, d)` 와 변 `(b, c)` 가 정점이 아닌 위치에서 교차하고 있으나, 두 변 중 하나를 이동하여 그린 동형 그래프(그래프 `A`) 가 평면 그래프이다.
  • 그러므로 그래프 `B` 도 평면 그래프이다.
• 그러나 그래프 `C` 는 정점이 아닌 위치에서 교차하는 변 `(a, f), (c, d), (b, e)` 의 위치를 이동해도 정점이 아닌 위치에서 교차할 수 있으므로 평면 그래프가 아니다.

 

평면 그래프와 영역(Space)

• 평면 그래프에서는 정점과 변에 의해 하나 이상의 영역(Space)이 만들어질 수 있다.
• 만약 평면 그래프가 아닌 경우에는 그래프에서 영역을 구할 수 없다.

평면 그래프의 영역

• 그래프 `A, B, C` 는 모두 평면 그래프로, 영역을 구할 수 있다.
• 그래프 `A` 에서 영역 ①은 정점 `a, b, c, f` 와 변 `(a, c), (a, f), (b, c), (b, f)` 로 만들어진 닫힌 영역이고, 영역 ②는 열린 영역이므로 영역 ①의 바깥 영역에 해당한다.
  • 그러므로 그래프 `A` 는 2개의 영역으로 구성된다.
• 반면, 그래프 `B` 와 `C` 는 모두 열린 영역으로 구성되어 하나의 영역을 갖는다.

 

오일러 공식(Euler's Formula)

• 평면 그래프의 정점과 변, 영역 사이의 관계를 정리하면 다음과 같다.

평면 그래프 `G` 에서 정점의 수를 `v`, 변의 수를 `e`, 영역의 수를 `s` 라고 할 때, 다음 오일러 공식이 성립한다.

$$v - e + s = 2$$

 

증명

• 오일러 공식을 증명하기 위해 변의 수를 이용한 수학적 귀납법을 이용한다.

 

① 기본 가정 : `e = 1` 일 때, 변이 하나인 그래프는 다음과 같이 두 종류이다.

• 그래프 `A` : 루프에 의해 닫힌 영역 하나와 그 바깥 영역 하나로 영역이 2개 존재한다.
  • $v = 1, e = 1, s = 2 \Rightarrow v - e + s = 1 - 1 + 2$ 이므로, 오일러 공식이 성립한다.
• 그래프 `B` : 열린 영역 1개가 존재한다.
  • $v = 2, e = 1, s = 1 \Rightarrow v - e + s = 2 - 1 + 1 = 2$ 이므로, 오일러 공식이 성립한다.

 

② 귀납 가정 : `e = k` 일 때, `v - k + s = 2` 가 성립한다고 가정한다.

 

③ 귀납 증명 : `e = k + 1` 일 때, 평면 그래프에 변을 하나 추가하는 방법은 다음과 같이 2가지 경우가 있다.

• (i) 정점을 하나 추가하여 기존의 정점 하나와 연결하면 `e = k + 1` 이고 `v' = v + 1` 이다. 이 때, 영역의 수는 증가하지 않는다.
  • $v' - e + s = (v + 1) - (k + 1) + s = v - k + s = 2$ (∵ 귀납 가정 `v - k + s = 2`)
• (ii) 기존의 정점 사이에 변을 하나 추가하면 `e = k + 1` 이다. 이 때, 정점의 수는 증가히지 않지만 영역의 수는 하나 증가하여 `s' = s + 1` 이다.
  • $v - e + s' = v - (k + 1) + (s + 1) = v - k + s = 2$ (∵ 귀납 가정 `v - k + s = 2`)
• ∴ 오일러 공식이 성립한다.

 

예제 : 다음 그래프를 이용하여 오일러 공식이 성립함을 보여라.

(a)

$v = 4, e = 5, s = 3 \Rightarrow v - e + s = 4 - 5 + 3 = 2$

 

(c)

이 평면 그래프에 대해 정점이 아닌 위치에서 변들이 교차하지 않는 동형 그래프를 그리면 다음과 같다.

$v = 7, e = 14, s = 9 \Rightarrow v - e + s = 7 - 14 + 9 = 2$

(정점이 아닌 위치에서 변이 교차하지 않도록 동형 그래프를 그리지 않더라도, 정점과 변의 개수와 오일러 공식을 이용해 영역의 수를 구할 수 있다. (v - e + s = 7 - 14 + s = 2, ∴ s = 9)

 

정규 그래프와 완전 그래프

정규 그래프(Regular Graph : `k`-정규 그래프)

그래프 $G = (V, \; E)$ 내에 있는 모든 정점의 차수가 `k` 로 같은 그래프

$$V = \{ v_{1}, v_{2}, \cdots, v_{n} \} \text{일 때, } d(v_{1}) = d(v_{2}) = \cdots = d(v_{n}) = k$$

 

예

정규 그래프와 완전 그래프의 예

• 위의 두 그래프는 모두 정규 그래프이다.
• 두 그래프의 정점과 차수를 각각 구하면 다음과 같이 모든 정점의 차수가 같기 때문이다.

그래프 `A` : $d(a) = 2, \quad d(b) = 2, \quad d(c) = 2, \quad d(d) = 2$ 그래프 `B` : $d(a) = 3, \quad d(b) = 3, \quad d(c) = 3, \quad d(d) = 3$

• 이처럼 그래프를 구성하는 모든 정점의 차수가 `k` 인 정규 그래프를 `k`-정규 그래프라고 표기한다.
• 따라서 그래프 `A` 는 2-정규 그래프이고, 그래프 `B` 는 3-정규 그래프이다.
• 특히 그래프 `B` 는 그래프에 포함된 모든 정점이 다른 정점과 연결되는데, 이러한 그래프를 완전 그래프라고 한다.

 

완전 그래프(Complete Graph : $K_{n}$ )

그래프 $G = (V, \; E)$ 내에 있는 모든 정점 사이에 변이 존재하는 그래프

$$|V| = n \text{일 때, } d(v_{i}) = n - 1, \quad 1 \le i \le n$$

• $|V| = n$ 일 때 완전 그래프에 포함된 모든 정점의 차수는 자신을 제외한 나머지 모든 정점과 근접한 변의 개수 `n - 1` 이므로 항상 $d(v_{i}) = n - 1$ 이다.
• 이 때, 모든 정점의 차수가 같으므로 완전 그래프는 정규 그래프이기도 하다.
• 완전 그래프는 그래프에 포함된 정점의 수(`n`)를 이용하여 $K_{n}$ 으로 표기한다.

 

정규 그래프와 완전 그래프의 예

• 위의 그래프 `B` 를 보면 $|V_{B}| = 4$ 이고 모든 정점의 차수는 $d_{B}(v_{i}) = |V_{B}| - 1 = 3$ 임을 확인할 수 있다.
• 그러므로 그래프 `B` 는 3-정규 그래프이면서 완전 그래프 $K_{4}$ 이다.

 

이분 그래프와 완전 이분 그래프

완전 이분 그래프(Complete Bipartite Graph : $K_{m, n} \; (|V_{1}| = m, \; |V_{2}| = n)$ )

그래프 $G = (V, \; E)$ 에서 정점 집합 `V` 가 $V = V_{1} \cup V_{2}$ 와 $V_{1} \cap V_{2} = \varnothing$ 을 만족하는 두 집합 $V_{1}$ 과 $V_{2}$ 로 분리되고, 그래프의 모든 변이 $V_{1}$ 의 한 정점에서 $V_{2}$ 의 기울기 정점으로 연결되는 그래프

 

이분 그래프(Bipartite Graph)

그래프 $G = (V, \; E)$ 에서 정점 집합 $V$ 가 $V = V_{1} \cup V_{2}$ 와 $V_{1} \cap V_{2} = \varnothing$ 을 만족하는 두 집합 $V_{1}$ 과 $V_{2}$ 로 분리되고, 그래프의 어떤 변이 $V_{1}$ 의 한 정점에서 $V_{2}$ 의 기울기 정점으로 연결되는 그래프

• 이분 그래프와 완전 이분 그래프는 그래프의 정점 집합을 2개의 부분 집합으로 분할(Partition)할 때 한 부분 집합의 정점과 다른 부분 집합의 정점 사이에만 변이 존재하는 그래프로, 같은 부분 집합에 포함된 정점 사이에는 변이 존재해서는 안 된다.

 

예

이분 그래프, 완전 이분 그래프인 예와 아닌 예

• 그래프 `A, B, C` 는 모두 6개의 정점 $V = \{ a, b, c, d, e, f \}$ 로 구성된다.
• 완전 이분 그래프와 이분 그래프를 판별하기 위해 인접하지 않는 정점끼리 같은 집합으로 구성하여 각 그래프의 정점 집합 `V` 를 분할해보자.
• 그래프 `A` 와 `B` 의 경우, 정점 집합 `V` 에 포함되는 정점 중 `a, c, e` 사이와 `b, d, f` 사이에는 연결선이 존재하지 않으므로 다음과 같이 분할할 수 있다.

$$V = \{ V_{1}, V_{2} \} = \{ \{a, c, e \}, \{b, d, f \} \} \quad (V_{1} \cup V_{2} = V, \; V_{1} \cap V_{2} = \varnothing)$$

• 그래프 `A` 는 정점 `a` 와 `b, d, f`, 정점 `c` 와 `b, d, f`, 정점 `e` 와 `b, d, f` 사이에 근접하는 변이 있다.
  • 즉, $V_{1}$ 의 모든 정점이 각각 $V_{2}$ 의 모든 정점과 근접하는 변을 갖는다.
  • 그러므로 그래프 `A` 는 완전 이분 그래프이고, $K_{3, 3}$ 으로 표기한다.
• 그래프 `B` 는 정점 `a` 와 `d, f`, 정점 `c` 와 `b, d`, 정점 `e` 와 `d, f` 사이에 근접하는 변이 있다.
  • 즉, $V_{1}$ 의 모든 정점이 $V_{2}$ 의 일부 정점과 근접하는 변을 갖는다.
  • 그러므로 그래프 `B` 는 완전 이분 그래프는 아니고 이분 그래프이다.
• 그래프 `A, B` 와는 달리 그래프 `C` 의 경우, 정점의 집합을 분할하면 같은 부분 집합에 포함된 정점 사이에 근접하는 변이 존재한다.
  • 예를 들어, 그래프 `C` 의 정점 집합 `V` 를 $V = \{V_{1}, V_{2} \} = \{ \{a, c, e \}, \{ b, d, f \} \}$ 로 분할한다고 가정할 때, $V_{1}$ 에 포함되는 정점 `a` 와 `c` 또는 정점 `c` 와 `e` 사이에 근접하는 변이 존재한다.
  • 따라서 그래프 `C` 는 완전 이분 그래프도, 이분 그래프도 아니다.