最后更新: 2024-04-06 18:26 查看: 151 次反馈刷题

结点的度与子图

## 结点的度
定义 3 无向图中与结点 $v$ 关联的边数称为 $v$ 的次数 (或度数、度), 记作 $\operatorname{deg}(v)$ (若 $v$有环, 则它对 $v$ 的度计为 2)。有向图中, 以结点 $v$ 为起点的边数称为 $v$ 的出度, 记作 $\operatorname{deg}^{+}(v)$;以 $v$ 为终点的边数称为 $v$ 的入度, 记作 $\operatorname{deg}^{-}(v)$; $\operatorname{deg}^{+}(v)+\operatorname{deg}^{-}(v)$ 称为 $v$ 的度, 记作 $\operatorname{deg}(v)$ ，即 $\operatorname{deg}(v)=\operatorname{deg}^{+}(v)+\operatorname{deg}^{-}(v)$ （若 $v$ 有环，它对 $v$ 的出度和入度各计 1)。

定理 1 (握手定理) 设图 $G=<V, E>, V=\left\{v_1, v_2, \Lambda, v_n\right\},|E|=m$, 则 $\sum_{i=1}^n d\left(v_i\right)=2 m$ 。又若 $G$ 为有向图, 则 $\sum_{i=1}^n \operatorname{deg}^{+}\left(v_i\right)=\sum_{i=1}^n \operatorname{deg}^{-}\left(v_i\right)=m$
推论 在任何图中, 奇度结点的个数为偶数。
度为 1 的结点所关联的边称为悬挂边, 该结点称为悬挂结点。
无向图 $G$ 中结点的最大度记作 $\Delta(G)$, 最小度记作 $\delta(G)$; 有向图中最大和最小出度分别记作 $\Delta^{+}$和 $\delta^{+}$, 最大和最小入度分别记作 $\Delta^{-}$和 $\delta^{-}$。

每个结点的度为 $n-1$ 的 $n$ 阶无向图称为 $n$ 阶无向完全图, 记作 $K_n$; 每个结点的出度和入度均为 $n-1$ 的 $n$ 阶有向图称为 $n$ 阶有向完全图, 也记作 $K_n ; n$ 阶完全无向图的定向图称为竞赛图; $\Delta(G)=\delta(G)=k$, 即各结点的度均为 $k$ 的无向图称为 $k$ 正则图 (对有向图也可定义正则图, 但没有相应类型的无向图重要)。例如由正四面体、正方体、正八面体、正十二面体、正二十面体的顶点和边构成的图均为正则图, 分别称为四面体图 (即 $K_4$ )、方体图、八面体图、十二面体图、二十面体图, 统称为柏拉图图。其中的四面体图、方体图和十二面体图均为 3 正则图, 八面体图为 4 正则图, 二十四体图为 5 正则图。
$n$ 边形的顶点和边构成的图称为 $n$ 边形图, 记作 $C_n(n \geq 3)$ 。显然 $C_n$ 是 2 正则图。在 $C_{n-1}$内放置一个顶点, 使之与 $C_{n-1}$ 的各顶点相邻, 这样构成的简单图称为轮图, 记作 $W_n$ 。

若无向图 $G=<V, E>$ 的 $V$ 可分成两个不相交的非空子集 $V_1$ 和 $V_2$, 使 $G$ 的每条边的端点, 一个属于 $V_1$, 另一个属于 $V_2$, 则称 $G$ 为二部图 (或二分图、二元图、偶图), 记作 $G=\left\langle V_1, V_2, E>, V_1\right.$ 和 $V_2$ 称为互补结点子集。又若简单二部图 $G$ 中 $V_1$ 的每个结点与 $V_2$ 的所有结点相邻, 则称 $G$ 为完全二部图, 记作 $K_{n, m}$, 其中 $n=\left|V_1\right|, m=\left|V_2\right| \circ K_{1, m}$ 称为星形图。 $n$ 阶图中的 $n$ 个结点组成的 (单调增加) 序列称为 $G$ 的度序列, 记作 $\left(d_1, d_2, \Lambda, d_{\mathrm{n}}\right)$ 。

## 子图
定义 4 设图 $G=<V, E>$ 和 $G^{\prime}=\left\langle V^{\prime}, E^{\prime}>\right.$, 若 $V^{\prime} \subseteq V, E^{\prime} \subseteq E$, 则称 $G^{\prime}$ 为 $G$ 的子图, $G$ 为 $G^{\prime}$ 的母图, 记作 $G^{\prime} \subseteq G$ 。

若 $V^{\prime} \subset V$ 或 $E^{\prime} \subset E$, 则称 $G^{\prime}$ 为 $G$ 的真子图; 若 $V^{\prime}=V, E^{\prime} \subseteq E$, 则称 $G^{\prime}$ 为 $G$ 的生成子图或支撑子图; 若 $V^{\prime} \subseteq V, E^{\prime}$ 是关联结点都在 $V^{\prime}$ 中的 $G$ 的边集合, 则称 $G^{\prime}$ 为 $G$ 的由 $V^{\prime}$ 导出的子图, 记作 $G\left(V^{\prime}\right)$; 若 $E^{\prime} \subseteq E, V^{\prime}$ 是 $E^{\prime}$ 中的边关联的结点集合, 则称 $G^{\prime}$ 为 $G$ 
的由 $E^{\prime}$ 导出的子图, 记作 $G\left(E^{\prime}\right)$ 。
由 $G$ 的所有结点和为了使 $G$ 成为完全图所需要添加的边组成的图, 称为 $G$ 的补图,记作 $\bar{G}$ 。

开VIP会员

非会员每天6篇，会员每天16篇，VIP会员无限制访问

题库训练自我测评投稿

上一篇：图的基本概念

下一篇：图的重构与运算

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