그래프 $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}$ 는 다음과 같다.
이처럼 그래프를 구성하는 모든 정점의 차수가 `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` 사이에는 연결선이 존재하지 않으므로 다음과 같이 분할할 수 있다.
그래프 `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` 사이에 근접하는 변이 존재한다.
Microsoft Student (2023)
