[이산수학] 동형 그래프, 완전 그래프, 정규 그래프, 이분 그래프

동형 그래프

동형 그래프 (Isomorphic graph)
그래프 $G_1 = (V_1, E_1)$과 $G_2 = (V_2, E_2)$가 주어졌을 때 전단사 함수 $f: V_1 → V_2$가 존재하여 $\{u, v\} \in E_1 \iff \{f(u), f(v)\} \in E_2$이면 $f$를 동형(isomorphism)이라 하고 $G_1$과 $G_2$를 동형 그래프라 함

동형 그래프의 예시. 2개의 그래프는 같은 그래프이다.

완전 그래프

완전 그래프 (complete graph)
그래프 $G = (V, E)$의 모든 정점들의 쌍 사이에 연결선이 존재하면 $G$를 완전 그래프라 함. $n$개의 정점으로 구성된 완전 그래프는 $K_n$으로 표기함

각각 $n = 4$, $n = 5$, $n = 6$인 그래프. $K_4$, $K_5$, $K_6$

 

정규 그래프

정규 그래프 (regular graph)
그래프 $G = (V, E)$의 모든 정점의 차수가 $k$이면 $G$를 $k$차 정규 그래프라고 함

 

이분 그래프

이분 그래프 (bipartite graph)
그래프 $G = (V, E)$에서 $V$가 두 부분 집합 $X$와 $Y = V - X$로 나누어져 각 연결선이 $X$ 내의 정점과 $Y$ 내의 정점의 쌍으로 연결되면 그래프 $G$를 이분 그래프라고 함.
완전 이분 그래프 (complete bipartite graph)
$X$ 내의 모든 정점들과 $Y$ 내의 모든 정점들 사이에 연결선이 존재하면 완전 이분 그래프라고 함.

$K_{2, 3}$ / $K_{3, 4}$