【图论笔记】图论基础（1）：图论中的图

图论是组合数学与离散数学的一个分支，起源于1736年的柯尼斯堡七桥问题，并在四色问题历时一百多年的求证过程中得以壮大．它与理论计算机科学、组合最优化、复杂网络等学科分支有着密切的联系，是现代数学中相当活跃的一个分支．图论中的图，并不是我们日常用语中的图，而是一种数学结构，本文给出图的定义和基本性质．

目录

• 1. 图的定义
• 2. 图的直观表示
• 3. 简单图与重（chong）图
• 4. 顶点的邻域和度
• 返回【图论笔记】

1. 图的定义

一个图$G$由三个要素构成，即有限集合$V$，有限集合$E$，以及$E$到$V^{\{2\}}$的映射$\psi$，其中$V^{\{2\}}$是$V$全体二元子集的集合，此处所说的“二元子集”允许出现两个相同的元素．

由于有限集合$V$和$E$的地位不同，所以我们一般说：

图$G$ 是一个有序三元组$G(V,E,\psi)$

其中，

• 有限集合$V$叫做图$G$的顶点集，也记作$V(G)$，其元素称为$G$的顶点；
• 有限集合$E$叫做图$G$的边集，也记作$E(G)$，其元素称为$G$的边；
• 图$G$的顶点总数和边的总数分别记作$v(G)$和$e(G)$，分别叫做$G$的阶和规模；
• 映射$\psi$叫做图$G$的关联映射或关联函数，也记作$\psi_G$；

对于图$G(V,E,\psi)$设$u,v\in V$，$e\in E$

• 为了方便书写，我们通常把$V$的可重复二元子集$\{u,v\}$简写为成 $uv$．
• 如果$\psi(e)=uv$，则称$e$连接了$u$和$v$，也说$u$和$v$是$e$的端点．
• 如果$u,v$关联于同一个边$e$，我们也说$u$和$v$是相邻的或邻接的，并且互为邻点．

由于$G$的关联映射$\psi$通常会在上下文中明确指定，所以我们通常将之隐藏．例如，如果$\psi(e)=uv$，那么在隐藏$\psi$之后也可以写作$e=uv$，因而我们也说

图$G$是有序二元组$G(V,E)$

这是我们通常使用的写法．下面举例解释．

例1. 设$G(V(G),E(G))$是一个图，其中
$V(G)=\{u,v,w,x,y\},~E(G)=\{a,b,c,d,e,f,g\}$其关联函数$\psi_G$如下定义，
$\begin{matrix} a=uv & b=uu & c=vw & d=wx\\ e=vx & f=wx & g=ux & h=xy \end{matrix}$

当然，这个例子仍然有些抽象，我们更常见的使用图画的形式直观地表示一个图．

2. 图的直观表示

在实际使用中，我们通常会把图画在平面上，一般使用实心或空心的小圆圈表示顶点，用连接两个顶点的连续曲线段表示边，它所连接的两个顶点就是这条边的两个端点．平面上不用实心或空心小圆圈表示的点不是顶点．例如，前面例1中的图$G$直观地画在平面上就是这样

3. 简单图与重（chong）图

• 在例1中，$b=uu$，可见$b$是一条将$u$与自身连接的边，这种边叫做环．
• 在例1中，$d=wx$，$f=wx$，可见$d$和$f$都连接了相同的一对顶点$w$和$x$，但它们又是不同的边，所以这样的边$d$和$f$叫做一组平行边或者重（chong）边．

如果图$G$中既没有环也没有重边，我们就是$G$是一个简单图；否则称之为重（chong）图．

如果$G$是简单图，那么我们就没必要再为边标号了，我们可以直接用边的两个端点称呼这条边，例如如果我们在例1中删除边$b$和$f$，我们就得到了一个简单图，其中边$d$可以直接称为边$wx$．注意：这种做法在有平行边的图中会造成混淆，例如在例1中，如果你说边$wx$，我们将搞不清楚你指的是边$d$还是$f$．

4. 顶点的邻域和度

设$G(V,E)$是一个图，$v\in V$．

• $v$的邻点的集合称为$v$的邻域，记作$N_G(v)$或$N(v)$；
• $v$被$E$关联的总次数称为$v$的度，记作$d_G(v)$或$d(v)$．

注意：

• $N(v)$可能包含$v$．
• 当我们在计算$d(v)$时，我们不是在数关联于$v$的边的个数，而是在数$v$被关联的次数，这是因为如果$v$关联了一个环，那么它实际是被这个环关联了两次．换言之：
  • 在计算$d(v)$时，$v$所关联的环会被数两次，但$v$所关联的非环边只会被数一次；
    = 一般来说，$d(v)\ge|N(v)|$，因为环和重边可能存在；
  • 如果$G$是简单图，那么$d(v)=|N(v)|$．

关于图的度之和，有著名的握手定理，其证明非常简单，只需要对图的边数数两遍就可以了．

握手定理 $\sum_{v\in V(G)}d(v)=2e(G).$

返回【图论笔记】