离散数学笔记(12)——图论的基本概念

离散数学笔记(12)——图论的基本概念

图论

图的基本概念

无向图的概念

设 $A,B$ 是两个非空集合,记:
$$
A \times B = \{\langle a,b \rangle | a \in A \land b \in B\} \\
A \& B = \{(a,b) | a \in A \land b \in B\}
$$
定义 1:一个无向图 $G$ 定义为一个二元组 $\langle V,E \rangle$,记作 $G = \langle V,E \rangle$,其中:

  1. $V$ 是一个非空集合,称为 $G$ 的顶点集,它的元素称为顶点
  2. $E \subseteq V \& V$,称为 $G$ 的边集,其元素称为,$V \& V$ 中的元素可以在 $E$ 中出现不止一次。

定义 2:没有任何边的图称为空图,只有一个点的图称为平凡图

定义 3:图中顶点的个数称为图的阶,若 $|V(G)| = n$,则称 $G$ 为 $n$ 阶图;连接两个相同顶点的边的条数称为边的重数,这些边称为平行边或多重边

邻接点:与一边关联的两个结点。

邻接边:关联同一个点的两条边。

:只关联一个结点的边。

简单图:没有环以及没有重数大于 $1$ 的边的图。

孤立点:不与任何点邻接的点。

以下记 $|V(G)| = n,|E(G)| = m$。

无向图结点 $v$ 的度

$G$ 是无向图,$v \in V(G)$,结点 $v$ 所关联边数,称之为结点 $v$ 的,记作 $d(v)$,环对度贡献为 $2$。

奇点:度为奇数的点。

偶点:度为偶数的点。

无向图的结点度序列

令 $G = \langle V,E \rangle$ 是无向图,$V = \{v_1,v_2,\cdots,v_n\}$,则称 $(d(v_1),d(v_2),\cdots,d(v_n))$ 为图 $G$ 的结点度序列

图的最大度和最小度

最大度:$\Delta(G) = \max \{d(v) | v \in G\}$

最小度:$\delta(G) = \min \{d(v) | v \in G\}$

相关定理

定理 1:每个无向图所有结点度总和等于边数的 $2$ 倍,即:
$$
\sum_{v \in V} d(v) = 2 |E|
$$
定理 2:每个无向图中,奇数度的结点必为偶数个。

$k$-正则图

一个无向简单图 $G$ 中,如果 $\Delta(G) = \delta(G) = k$,则称 $G$ 为 $k$-正则图。

完全图

$G$ 是个简单图,如果每对不同结点之间,都有边相连,则称 $G$ 是个无向完全图。如果 $G$ 有 $n$ 个结点,记为 $K_n$。

定理:完全图 $K_n$ 有边数 $\dfrac{n(n – 1)}{2}$。

补图

定义 1:设 $G$ 是简单图,$H$ 是一个以 $V(G)$ 为顶点集的图,且两个顶点在 $H$ 中邻接当且仅当它们则在 $G$ 中不邻接,则称 $H$ 是 $G$ 的补图,记作 $H = \overline{G}$。

定义 2:由 $G$ 的所有结点和为使 $G$ 称为完全图,所需要添加的那些边组成的图,称之为 $G$ 的补图。

图的同构

设 $G = \langle V,E \rangle$ 和 $G’ = \langle V’,E’ \rangle$ 是图,如果存在双射 $f : V \to V’$ 且任何 $e = (v_i,v_j) \in E$,有 $e’ = (f(v_i),f(v_j)) \in E’$,并且边 $e$ 与 $e’$ 的重数相同。

则称 $G$ 与 $G’$ 同构,记作 $G \stackrel{\backsim}{=} G’$。

两个图同构的必要条件

  1. 结点个数相等。
  2. 边数相等。
  3. 度数相同的结点数相等。
  4. 对应的结点的度数相等。

子图

定义 1:称图 $H$ 为图 $G$ 的子图,如果 $V(H) \subseteq V(G)$,$E(H) \subseteq E(G)$,且 $H$ 中边的重数不能超过 $G$ 中对应边的重数。

定义 2:设 $G = \langle V,E \rangle$,一个满足 $H = \langle V,E_1 \rangle$,$E_1 \subseteq E$ 的子图称为 $G$ 的生成子图。

定义 3:设 $V’$ 是图 $G$ 的顶点集 $V$ 的一个非空子集,以 $V’$ 作为顶点集,以两端点均在 $V’$ 的边的全体为边集的子图,称为由 $V’$ 导出的 $G$ 的子图,记为 $G[V’]$,称其为 $G$ 的导出子图。

定义 4:设 $E’$ 是图 $G$ 的边集 $E$ 的一个非空子集,以 $E’$ 为边集,以 $E’$ 中边的全体端点为顶点集组成的子图称为由 $E’$ 导出的子图,记为 $G[E’]$。

:$G$、空图均为 $G$ 的子图,而且是非空子图,称为平凡子图。其中,$G$ 为 $G$ 的点导出子图。

路与回路

路(walk)

给定图 $G = \langle V,E \rangle$,设 $v_0,v_1,\cdots,v_k \in V,e_1,e_2,\cdots,e_k \in E$,其中 $e_i$ 是关联 $v_{i – 1}$ 和 $v_i$ 的边,则称结点和边的交叉序列 $v_0e_1v_1\cdots e_kv_k$ 是连接 $v_0$ 和 $v_k$ 的

$v_0$ 是此路的起点,$v_k$ 是此路的终点。路中含有的边数 $k$ 称之为路的长度

如果 $G$ 是个简单图,则路可以只用结点序列表示。

回路

如果一条路的起点和终点是同一个结点,则称此路是一个回路

迹(chain)和闭迹

如果一条路中,所有边都不同,则称此路为

如果一条回路中,所有边都不同,则称此回路为闭迹

通路(path)和圈(cycle)

如果一条路中,所有结点都不同,则称此路为通路

如果一条回路中,除起点和终点外,其余结点都不同,则称此回路为

 

点赞 0

No Comments

Add your comment