科数网
首页
题库
试卷
学习
VIP
你好
游客，
登录
注册
在线学习
离散数学
第五章 图论
二分图
最后
更新:
2025-01-22 09:22
查看:
63
次
反馈
同步训练
二分图
定义8．23（二分图）若图 $G$ 的顶点集 $V$ 能划分为两个子集 $V_1$ 和 $V_2$ ，并且每条边的一个端点在 $V_1$ 中，另一个端点在 $V_2$ 中，则称 $G$ 为二分图，记为 $G\left(V_1, V_2\right)$ 。 $V$ 划分为 $V_1$ 和 $V_2$ ，称为 $G$ 的一个二划分。记为 $\left(V_1, V_2\right)$ 。若简单图 $G$ 具有二划分 $\left(V_1, V_2\right)$ ，并且 $V_1$ 中每个顶点与 $V_2$ 中每个顶点恰有一条边相连，称 $G$ 为完全二分图。若 $\left|V_1\right|=m,\left|V_2\right|=n$ ，则这样的完全二分图记为 $K_{m, n}$ 。例如，图 8.10 给出完全二分图记为 $K_{3,3}$ 。 利用回路的概念，可以给出二分图的性质。  利用回路的概念，可以给出二分图的性质。 定理8．13 $G$ 是二分图当且仅当 $G$ 中没有奇回路。 证明：$\Rightarrow$ 设 $G$ 是具有二划分 $\left(V_1, V_2\right)$ 的二分图，并且 $G$ 具有一条回路 $C$ ：$\left(v_0\right.$ ， $v_1, \cdots, v_m, v_0$ ）。不失一般性，设 $v_0 \in V_1$ ，因为 $\left\{v_0, v_1\right\} \in E$ ，且 $G$ 是二分图，所 图 8.10以 $v_1 \in V_2$ ，同理 $v_2 \in V_1$ 。则可以推导出 $v_{2 i} \in V_1, v_{2 i+1} \in V_2$ 。因为 $v_0 \in V_1$ ，所以 $v_m \in V_2$ 。 因而存在 $k$ 使 $m=2 k+1$ ，即回路 $C$ 是偶回路。 $\
免费注册看余下 50%
非VIP会员每天15篇文章，开通VIP 无限制查看
上一篇：
路径矩阵
下一篇：
欧拉图和半欧拉图
本文对您是否有用？
有用
(
0
)
无用
(
0
)
更多
学习首页
数学试卷
同步训练
投稿
题库下载
会议预约系统
数学公式
关于
科数网是专业专业的数学网站 版权所有 本站部分教程采用AI辅助生成，请学习时自行鉴别
如果页面无法显示请联系 18155261033 或 983506039@qq.com