最后更新: 2025-01-21 16:56 查看: 98 次纠错评论(0) 课件开VIP

图的同构

定义7－1．9 给定图G＝＜V，E＞及图G＇＝＜V＇， $E ^{\prime}>$,如果存在一一对应的映射 $g: v_i \rightarrow v^{\prime} i$ 且 $e=\left(v_i, v_j\right)$（或 $\langle v i, v j\rangle)$ 是 $G$ 的一条边，当且仅当 $e^{\prime}=\left(g\left(v_i\right), g\left(v_j\right)\right)$ （或 $\left\langle g \left( v _{ i }\right), g \left( v _{ j }\right)>\right.$ ）是 $G ^{\prime}$ 的一条边，则称 $G$ 与 $G ^{\prime}$ 同构，记作 $G \cong G ^{\prime}$ 。
注：同构的充要条件是两个图的结点和边分别存在着一一对应，且保持关联关系。
 ![图片](/uploads/2025-01/ce7b4e.jpg)
 
###  说明
类似地，可以定义两个有向图的同构。
图的同构关系看成全体图集合上的二元关系。
图的同构关系是等价关系。
在图同构的意义下，图的数学定义与图形表示是一一对应的。
### 两图同构的必要条件：
结点数目相同
边数相等
度数相同的结点数目相等

例1-5 判断下面两图是否同构。
 ![图片](/uploads/2025-01/fb5719.jpg)
 
 
 例1-6 判断图是否同构并说明理由。
  ![图片](/uploads/2025-01/6bee02.jpg)
  
  答：图中 $(a)$ 和 $(b)$ 不同构，下面给出理由。
若（a）和（b）同构，则一定存在一个同构映射。设 f 是同构映射，即 $f: V_1 \rightarrow V_2$ 是双射，其中 $V_1=\{1,2,3,4,5\}$ ， $V _2=\{ a , b , c , d , e \}$ 。不难从图同构定义中知， f 是图的同构映射，一定有 $d \left( v _i\right)= d \left( f \left( v _i\right)\right)$ 。即图9．5（a）中的两个3度顶点必须和图9．5（b）中的两个3度顶点对应，无论你怎样搭配。不失一般性，设 $f(2)=c, f(4)=d$ 。但是不能保证在图9．5（a）的边集中有两个 3 度顶点为端点的边与 $\{c, d\}$ 边相对应，因为 $\{2,4\} \notin E_1,\{c, d\} \in E_2$ ，即 $f$ 不能保证相应的边集的一一对应。故 f 不是图的同构映射。

例1-7 指出下述两图不同构的理由。
 ![图片](/uploads/2025-01/f0881f.jpg)
 反证法： 假使两图同构。 不妨假设红点对应
红点,则3个绿点对应3个绿点, 剩下的2个黑点
对应2个黑点，而在左图中2个黑点间无边，而
在右图中2个黑点间有边。矛盾！

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：子图与补图

下一篇：路与回路

本文对您是否有用？有用 (0) 无用 (0)