最后更新: 2025-11-21 16:43 查看: 158 次纠错评论(0) 课件开VIP

无向图与有向图

## 无向图
在集合论中已给出了集合与笛卡儿积的概念ꎬ这里还需要给出多重集与无序积的概念。

集合中的元素不重复出现，当允许元素重复出现时称作**多重集**。如，$\{a, a, b, c, c, c\}$ 与 $\{a,b, c\}$ 作为集合是相同的，而作为多重集是不相同的．

设 $A, B$ 为两集合，$\{\{a, b\} \mid a \in A \wedge b \in B\}$ 称为 $A$ 与 $B$ 的**无序积**，记作 $A \& B$ ．为方便起见，将无序对 $\{a, b\}$ 记作 $(a, b)$ 。无论 $a, b$ 是否相同，显然有 $(a, b)=(b, a)$ 。例如，设 $A=\left\{a_1\right.$ ， $\left.a_2\right\}, B=\left\{b_1, b_2\right\}$ ，则

$$
\begin{aligned}
& A \& B=\left\{\left(a_1, b_1\right),\left(a_1, b_2\right),\left(a_2, b_1\right),\left(a_2, b_2\right)\right\}, \\
& A \& A=\left\{\left(a_1, a_1\right),\left(a_1, a_2\right),\left(a_2, a_2\right)\right\} .
\end{aligned}
$$

**定义5.1** 一个无向图 $G$ 是一个二元组 $\langle V, E\rangle$ ，其中：
（1）$V$ 是一个非空的有穷集合，称为 $G$ 的**顶点集**，$V$ 中元素称为**顶点**或**结点**；
（2）$E$ 是无序积 $V \& V$ 的一个多重子集，称为 $G$ 的**边集**，$E$ 中元素称为**无向边**或简称**边**．

图 $G$ 的顶点集记作 $V(G)$ ，边集记作 $E(G)$ 。在图的运算中，有时会产生顶点集为 $\varnothing$ 的结果，因而规定顶点集为 $\varnothing$ 的图为**空图**．

以上给出的是一个无向图的数学定义，还可以用图形表示无向图，更直观．用小圆圈或实心点表示顶点，用连接两个顶点的线段表示边，其中顶点的位置、线段的曲直及是否相交都无关紧要。例如，$G=<V, E>, V=\left\{\boldsymbol{v}_1, \boldsymbol{v}_2, \boldsymbol{v}_3, \boldsymbol{v}_4, \boldsymbol{v}_5\right\}, E=\left\{\left(\boldsymbol{v}_1, \boldsymbol{v}_2\right),\left(\boldsymbol{v}_2, \boldsymbol{v}_2\right),\left(\boldsymbol{v}_2, \boldsymbol{v}_3\right)\right.$ ， $\left.\left(v_1, v_3\right),\left(v_3, v_1\right),\left(v_1, v_4\right)\right\}, G$ 的图形如图5．1（a）所示．

![图片](/uploads/2025-11/2497c3.jpg)

## 有向图

一个有向图 $D$ 是一个二元组 $\langle V, E\rangle$ ，其中：
（1）$V$ 是一个非空的有穷集合，称为 $D$ 的**顶点集**，$V$ 中元素称为**顶点**或**结点**；
（2）$E$ 是笛卡儿积 $V \times V$ 的多重子图，称为 $D$ 的边集，其元素称为**有向边**，也简称**边**．

也用 $V(D), E(D)$ 分别表示有向图 $D$ 的顶点集和边集．有向图 $D$ 也可以用图形表示，与无向图的区别是：用带箭头的连线表示有向边．例如，$D=\langle V, E\rangle$ ，其中 $V=\left(v_1, v_2, v_3, v_4\right. \left.v_5\right), E=\left(\left(v_1, v_1\right),\left(v_1, v_2\right),\left(v_3, v_2\right),\left(v_3, v_4\right),\left(v_2, v_4\right),\left(v_4, v_5\right),\left(v_5, v_4\right)\right\}$ ，$D$ 的图形如图5．1（b）所示。为方便起见，也可以给边起个名字。例如，在图5．1（a）中，用 $e_1$ 表示边（ $v_2$ ， $\left.\boldsymbol{v}_2\right), e_2$ 表示边 $\left(\boldsymbol{v}_1, \boldsymbol{v}_2\right)$ 等。图5．1（b）中，用 $e_1$ 表示边 $\left\langle\boldsymbol{v}_1, \boldsymbol{v}_1\right\rangle, e_2$ 表示边 $\left\langle\boldsymbol{v}_1, \boldsymbol{v}_2\right\rangle$ 等。

无向图和有向图通称为**图**,但有时也把无向图简称为图.常用Ｇ表示无向图,用Ｄ表示有向图,有时用Ｇ泛指无向图或有向图

> 注意 读者应该注意到，在有向图的图表示中，顶点的放置位置不是重要的．顶点之间的距离也没有意义，连接顶点的线的性质也不重要等。另外，两个弧交叉与否也不重要；交叉点不是有向图的顶点．有向图中的所有信息就是观察给定的一对顶点是否由一条有向线或弧相连接以及弧的走向等。因此，下图中的有向图 $D_1$ 和 $D_2$ 是相同的有向图，只是画法不同．在后面章节中，我们将说明 $D_1$ 和 $D_2$ 是同构的．

下面两个图看起来不一样，但是本质是一样的。
 ![图片](/uploads/2025-11/93baa7.jpg){WIDTH=400PX}

如果存在从顶点 $u$ 到顶点 $v$ 的弧，我们就说 $u$ 与 $v$ **相邻**的．因此，在上图的有向图 $D_1$ 中，$u$ 与 $v$ 和 $w$ 相邻，$w$ 与 $x$ 相邻等．

### 环

在有向图中，完全有可能在两个方向上都有弧，有从 $u$ 到 $v$ 的弧和从 $v$ 到 $u$ 的弧，如在下图的 $D_3$ 中所示的那样．也可能有从一个顶点到其自身的弧，如 $D_3$ 中的顶点 $w$ ．这样的弧称为环（loop）．然而，从 $u$ 到 $v$ 的弧的数量却不可能大于 1 ．通常在有向图的理论和应用中，这样的多重弧是很有用的，例如在化学键的研究中就是如此．那时，我们需要研究多重图 （multigraph）或多重有向图（multidigraph），而不是有向图．

![图片](/uploads/2025-11/68831d.jpg)

### 总结

经常出现的情况是，当存在从 $u$ 到 $v$ 的弧时也存在从 $v$ 到 $u$ 的弧．在这种情况下，我们称有向图 $(V, A)$ 是图（graph）．图 3.8 给出了几个图．在画图时，我们不考虑箭头，而且用连接顶点 $u$ 和顶点 $v$ 的单一无向线取代顶点 $u$ 和顶点 $v$ 之间的一对弧（并用无向环取代有向环）．我们称这样的线为这个图的一条边（edge），并把它看成顶点的无序对 $\{u, v\}$（顶点 $u, v$ 可以相同）．如果图中存在边 $\{u, v\}$ ，那么我们称 $u$ 和 $v$ 是邻居（neighbor）。以这种方式画出图3．8中的图，就得到图3．9．因此，图 $G$ 可以定义为对 $(V, E)$ ，其中 $V$ 是顶点集合，$E$ 是 $V$ 中无序元素对的集合，即边的集合．如果考虑多个图，我们将使用 $V(G)$ 和 $E(G)$ 分别表示 $G$ 的顶点集合和 $G$ 的边的集合．

![图片](/uploads/2025-11/ec3732.jpg){width=600px}

> **很多图论研究者都明确地做了下面的假设：不存在多重弧或边，即从顶点 $u$ 到顶点 $v$ 的弧或边的数量不大于 1 **

图 $G$ 的顶点 $u$ 的度（degree） $\operatorname{deg}(u)$ 或 $\operatorname{deg}_G(u)$ 计数 $u$ 的邻居数目．注意，如果我们把 $G$ 的所有顶点的度加起来，那么我们就计数每一条边两次，计数每一个顶点一次．因此我们有下面的定理．

**定理**  如果 $G$ 是有 $e$ 条边的任意图，那么有

$$
\sum_{u \in V(G)} \operatorname{deg}(u)=2 e .
$$

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：图论的作用

下一篇：顶点的度数与握手定理

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