科数网
学习首页
高中数学
高中物理
微积分
线性代数
概率论
赞助
在线教程
图论
图的重构与运算
最后更新:
2024-04-06 18:27
查看:
46
次
下载
编辑本文
科数网
图的重构与运算
## 图的同构 定义 5 设 $G_1=<V_1, E_1>, G_2=<V_2, E_2>$, 若存在双射 $f: V_1 \rightarrow V_2$, 使得边之间有如下关系: 如果 $f\left(v_i\right)=u_i, f\left(v_j\right)=u_j$, 且 $\left(v_i, v_j\right) \in E_1$ (或 $\left\langle v_i, v_j>\in E_1\right)$ 当且仅当 $\left(u_i, u_j\right) \in E_2$ (或 $\left\langle u_i, u_j>\in E_2\right.$ ), 而且 $\left(v_i, v_j\right)$ (或 $\left\langle v_i, v_j>\right)$ 与 $\left(u_i, u_j\right)$ (或 $\left\langle u_i, u_j\right\rangle$ ) 的重数相同,则称 $G_1$ 与 $G_2$ 是同构的, 记作 $G_1 \cong G_2$ 。 若两个图存在同构 $f$, 则 $f$ 不一定惟一。同构的图要求结点与结点之间, 边与边之间都存在一一对应, 而且它们的关联关系也必须保持其对应关系。同构的图除了它们的结点标记可能不同外, 其他的完全相同。图的同构关系是等价关系。判断两个图是否同构, 一般情况下并不容易。因为若两个图都有 $n$ 个结点, 它们之间的双射有 $n$ 个, 即使 $n$ 不大,检查这些双射是否保持结点与边的关联关系, 计算量也很大。但还是有一些办法可以帮助我们缩小所要考虑问题的范围。两个图同构, 首先它们要有相同的结点数和边数, 且度序列也相同, 因为同构的两个图中, 只有度相同的点才能建立对应关系。但两个度序列相同的图不一定同构。判断两个图不同构往往可采用如下办法: 将图的结点按某种对判断同构有意义的标准分类, 如按度分类。两个同构的图对应结点类的导出子图也应该同构, 这样就将问题局部化了。 ## 图的运算 设 $G_1=<V_1, E_1>, G_2=<V_2, E_2>$ 为无向图。若 $V_1$ I $V_2=\varnothing$, 则称 $G_1$ 与 $G_2$ 不相交;若 $E_1 \mathrm{I} E_2=\varnothing$, 则称 $G_1$ 与 $G_2$ 边不相交; 以 $E_1 \mathrm{Y} E_2$ 为边集, 以 $E_1 \mathrm{Y} E_2$ 中边关联的结点为结点集的图 $G$ 称为 $G_1$ 与 $G_2$ 的并图, 记作 $G=G_1 \mathrm{Y} G_2$; 以 $E_1 \mathrm{I} \quad E_2$ 为边集, 以 $E_1 \mathrm{I} \quad E_2$ 中边关联的结点为结点集的图 $G$ 称为 $G_1$ 与 $G_2$ 的交图, 记作 $G=G_1$ I $G_2$ 。当 $E_1$ I $E_2=\varnothing$ 时, $G_1$ I $G_2$ 为 $\varnothing$; 以 $E_1-E_2$ 为边集, 以 $E_1-E_2$ 中边关联的结点为结点集的图 $G$ 称为 $G_1$ 与 $G_2$的差图或 $G_2$ 相对于 $G_1$ 的补图, 记作 $G=G_1-G_2$ 。当 $E_1-E_2$ 为 $\varnothing$ 时, $G_1-G_2$ 为 $\varnothing$; $\left(G_1 \mathrm{Y} G_2\right)-\left(G_1 \mathrm{Y} G_2\right)$ 称为 $G_1$ 与 $G_2$ 的环和, 记作 $G_1 \oplus G_2$ 。当 $E_1=E_2$ 时, $G_1 \oplus G_2$为 $\varnothing$ 。
上一篇:
结点的度与子图
下一篇:
通路与回路
本文对您是否有用?
有用
(
0
)
无用
(
0
)
科数网知识库旨在打造一个可以顺序阅读的在线电子学习教程,点击顶部的
编辑本文
来完善本文,如果本文对您有用,也欢迎
赞助我们
0
篇笔记
写笔记
更多笔记
提交笔记