数学|图论基础-集合2-yiteyi-C++库

先决条件—— 图论基础-集合1 图是由一组对象构成的结构，其中一些对象对在某种意义上是“相关的”。图中的对象对应于顶点它们之间的关系符合边缘 .一个图形以图解的方式描述为一组点，这些点描绘的是由描绘边的线或曲线连接的顶点。正式地

null

“一张图表 $G = (V, E)$ 包括 $V$ ，一组非空的顶点（或节点）和 $E$ 一套边缘 .每条边都有一个或两个与其关联的顶点，称为其顶点端点 .”

图表类型： 有几种图是根据边、方向、权重等来区分的。

1.简单图- 每条边连接两条边的图形 不同的 没有两条边连接同一对顶点的顶点称为简单图。例如，考虑下面的图表——

图片[4]-数学|图论基础-集合2-yiteyi-C++库

上面的图是一个简单的图，因为没有顶点有自循环，也没有两个顶点有多条边连接它们。边由它们连接的顶点表示- ${A,B}$ 边是连接顶点的吗 $A$ 和 $B$ .

2.多重图- 多条边可以连接同一对顶点的图称为多重图。由于同一对顶点之间可能有多条边，因此 多种多样 边数表示两个顶点之间的边数。

图片[8]-数学|图论基础-集合2-yiteyi-C++库

上面的图是一个多重图，因为它们之间有多条边 $B$ 和 $C$ .边缘的多样性 ${B, C}$ 是2。

在一些图中，与上图不同的是，边是 指导的 这意味着对象之间的关系是单向的，而不是双向的。在某些应用中，边缘的方向可能很重要。

根据边缘是否有方向，我们可以 有向图 和 无向图 这个性质可以推广到简单图和多重图，得到简单有向或无向简单图和有向或无向多重图。

基本图形术语：

在上面的讨论中，已经解释了一些关于图的术语，例如顶点、边、有向边和无向边等。还有更多的术语描述顶点和边的属性。

邻接—— 在图表中 $G$ 两个顶点 $u$ 和 $v$ 据说是相邻如果它们是边的端点。边缘 ${u, v} - e$ 据说与顶点有关。如果边缘是定向的， $u$ 据说是毗邻 $v$ 和 $v$ 据说是邻近的 $u$ 在这里 $u$ 据说是 初始顶点 和 $v$ 据说 终端顶点 .
学位- 顶点的阶数是与其相关联的边数，但自循环除外，它对顶点阶数的贡献是两倍。顶点度 $u$ 表示为 $deg(u)$ . 对于有向图，度进一步分类为 程度上 和 外学位 .顶点的阶数是以给定顶点为终点的边数。顶点的出度是以给定顶点为初始顶点的边数。在程度上表示为 $deg^-(u)$ 向外度表示为 $deg^+(u)$ . 例如，在上面描述城市间航班的有向图中，顶点“德里”的入度为3，出度也为3。

注：如果顶点的度数为零，则称为 偏远的 .如果学位是1，那么就叫做吊坠 .

握手定理：

如果把一个图的所有顶点的度数相加，会得到什么。对于无向图，每条边贡献两次，一次用于其初始顶点，另一次用于其终端顶点。所以度数之和等于边数的两倍。这一事实在握手定理中得到了说明。

Let  be an undirected graph with  edges. Then





In case G is a directed graph,

对于无向图，握手定理有一个有趣的结果——

An undirected graph has an even number of vertices of odd degree.

证据： 允许 $V_{1}$ 和 $V_{2}$ 分别是偶数度和奇数度的顶点集。通过握手定理我们知道， $2e = sum_{uin V} deg(u)$ 所以 $2e = sum_{uin V} deg(u) = sum_{uin V_{1}} deg(u) + sum_{uin V_{2}} deg(u)$ 具有偶数度的顶点的度数之和为偶数。LHS也是偶数，这意味着奇数度顶点的度数之和必须是偶数。因此，奇数阶的顶点数为偶数。