

图论部分简介

图论（graph theory） 是数学的一个分支，它以图为研究的对象。

图论本身是应用数学的一部分，历史上图论曾经被很多数学家各自独立建立过。关于图论的最早文字记载最早出现在欧拉 1736 年的论著中，也就是著名的柯尼斯堡（Konigsberg）问题（七桥问题）。

图的定义¶

一个图 $G$ 是一个二元组，即序偶 $\langle V,E\rangle$ ，或记作 $G= \langle V,E\rangle$ ，其中 $V$ 是有限非空集合，称为 $G$ 的顶点集， $V$ 中的元素称为顶点或结点； $E$ 称为 $G$ 的边的集合， $\forall e_i \in E$ ，都有 $V$ 中的结点与之对应，称 $e_i$ 为 $G$ 的边。

简单来说，就是图 $G$ 就是一个结点的集合 $V$ 和边的集合 $E$ ，其中任意一条边都可以表示为两个结点之间的关系。若 $e_i\in E$ 表示为 $\langle u,v\rangle$ ，则有 $u\in V , v\in V$ 。

有向边和无向边¶

以上定义的结点对 可以是有序的，也可以是无序的 。如果边 $e_i$ 和结点无序对 $(u,v)$ 相对应，则称 $e_i$ 为无向边，记作 $e_i=(u,v)$ ，称 $u,v$ 为边 $e_i$ 的两个端点。

如果边 $e_i$ 和结点有序对 $\langle u,v\rangle$ 相对应，则称 $e_i$ 为有向边，记为 $e_i= \langle u,v\rangle$ ，称 $u$ 为边 $e_i$ 的始点， $v$ 为该边的终点。

简单来说，如果边对结点的关系是双向的，那么这条边是无向边；如果是单向的，那么这条边是有向边。

图的基本概念¶

无向图：每条边都是无向边的图。

有向图：每条边都是有向边的图。

混合图：在一个图中，有些边是有向边，另一些边是无向边，则该图为混合图。

有限图：一个图的点集和边集都是有穷集的图。

零图：边集为空集的图。

平凡图：仅有一个结点而没有边构成的图。

关联：若有 $e_i=(u,v)$ 且 $e_i\in E$ ，则称 $u$ 是和 $v$ 相关联的。

孤立点：无边关联的点。

自环：若一条边所关联的两个结点重合，则称此边为自环。

邻接：关联于同一条边的两个点 $u$ 和 $v$ 称为邻接的；关联于同一个点的两条边 $e_1$ 和 $e_2$ 是邻接的（或相邻的）。

结点的度数¶

设图 $G= \langle V,E\rangle$ 为一个有向图， $v\in V$ ，关联于结点 $v$ 的边的条数，称为点 $v$ 的度数，记作 $\deg(v)$ 。

注意：一个自环为它的端点增加 2 度。

当图 $G= \langle V,E\rangle$ 为一个有向图， $v\in V$ ，称以 $v$ 作为始点的边数之和称为结点 $v$ 的出度，记为 $\deg^{+} (v)$ 。将以 $v$ 作为终点的边数之和称为结点 $v$ 的入度，记为 $\deg^{-} (v)$ 。称以 $v$ 作为端点的边数之和为结点 $v$ 的度数或度，记为 $\deg(v)$ 。

显然， $\forall v\in V,\deg(v)=deg^{+} (v)+\deg^{-} (v)$ 。

定理 1¶

$\sum_{v\in V} \deg(v)=2\times |E|$

推论：在任意图中，度数为奇数的点必然有偶数个。

定理 2¶

$\sum_{v\in V} \deg^{+} (v)=\sum_{v\in V} \deg^{-} (v)=|E|$

即所有点入度之和等于出度之和。

子图的概念¶

设有图 $G= \langle V,E\rangle$ 和图 $G'= \langle V',E'\rangle$ 。

如果 $V'\subseteq V,E'\subseteq E$ ，则称 $G'$ 是 $G$ 的子图，记作 $G'\subseteq G$ 。

如果 $G'\subsetneqq G$ ，即 $V'\subset V$ 或 $E'\subset E$ ，则称 $G'$ 是 $G$ 的真子图，记作 $G'\subset G$ 。

如果 $V'=V,E'\subseteq E$ ，则称 $G'$ 是 $G$ 的生成子图。

如果 $V''\subseteq V$ 且 $V'' \neq \varnothing$ ，以 $V''$ 为结点集，以两端点均在 $V''$ 中的边为边集的 $G$ 的子图，称为 $V''$ 导出的 $G$ 的子图，简称为 $V''$ 的导出子图。

如果 $G''= \langle V'',E''\rangle$ 使得 $E''=E-E'$ ，且 $V''$ 中仅包含 $E''$ 中的边所关联的结点，则称 $G''$ 是子图 $G'$ 相对于原图 $G$ 的补图。

特殊的图¶

树：边数比结点数少一的连通图。更多内容，详见树相关基础。

森林：由 $m$ 棵（ $m\ge 0$ ）互不相交的树组成的图。

基环树：边数和点数相等的连通图。

仙人掌：每个结点至多在一个简单环上的图。

在无向图中，关联一对顶点的边多于 $1$ 条，则称这些边为重边（平行边），重边的条数称为重数。

简单图：不含重边和自环的图。

多重图：含重边的图。

完全图：每对不同的顶点之间都恰连有一条边相连的简单无向图。容易证明， $n$ 个顶点的完全图有 $\dfrac{n(n-1)}{2}$ 条边。

竞赛图：通过在完全图中为每条边分配方向而获得的有向图。

参考资料¶

离散数学（修订版），田文成周禄新编著，天津文学出版社，P184-187

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用