跳转至

图论部分简介

图论(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 个顶点的完全图有 \frac{n\times (n-1)}{2} 条边。

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

参考资料

离散数学(修订版), 田文成 周禄新 编著, 天津文学出版社, P184-187


评论