图同态 homomorphism
-
意义：提供了一种简化研究对象结构但是保留了原图邻接关系的一种方法.
-
定义：给定图 \(G,H\)，若存在映射 \(f: V(G)\rightarrow V(H)\) 使得 \(uv\in E(G)\) 可以推出 \(f(u)f(v)\in E(H)\)，则称 \(G\) 同态于 \(H\)，记为 \(G\rightarrow H\)，也称 \(G\) 是 \(H\)-可着色的（图 \(H\) 的任意一种正常着色可以给出图 \(G\) 的一种正常着色）.
-
上面 \(f\) 只是映射，可能不是单射（好几个萝卜放到一个坑里了），也可以不是满射（有的坑里没有萝卜）.
图同构 isomorphism
-
若 \(f\) 是双射，则称 \(G\) 同构于 \(H\). 此时两个图有相等数目的顶点和边.
-
图 \(G\) 的中心 core 是 \(G\) 的一个极小子图 \(H\) 且满足 \(G\rightarrow H\). 在同构意义下，任意图 \(G\) 只有一个 core.
图同胚 homeomorphism
- 定义：给定图 \(G,H\)，若\(G\) 的某个细分图同构于 \(H\) 的某个细分图（subdivision，边上添加2度点），则称 \(G\) 和 \(H\) 同胚.