图

定义 1　图；顶点；边

　　 图 $G(V,E)$ 是集合 V 上的一种二元关系 $E$。

　　 集合 $V$ 的元素称为图的顶点，若两个顶点之间有这种确定的二元关系，则称有一条边连这两个点。

　　 一个图的顶点的数目称为这个图的阶,记 作 $|G|$，图的边的数目称为它的度，记作 $||G||$。

定义 2　关联；相邻

• 若有一条边连一个图的某两个顶点，则称这两个顶点相邻，并称这两个顶点为这条边的端点。
• 若某一顶点是某一条边的端点，则称这个顶点和这条边关联。
• 若两条边和同一顶点关联，则称这两条边相邻.

定义 3　特殊点；特殊边

• 两个端点是同一个顶点的边称为环。
• 若某条边的两个端点不是同一个顶点，且只有一条边连这两个顶点，则称这条边为杆。
• 以某两顶点为端点的边可能不止一条，这时称连这两个顶点的边为重边。

定义 4　特殊图

• 只有一个顶点而没有边的图称为平凡图，没有边的图称为孤立图。
• 既可以有环，也可以有重边的图称为准图.
  没有环而可能有重边的图称为带重图.
  没有重边而可能有环的图称为带环图.
  既没有重边也没有环的图称为简单图,每两个顶点都相邻的简单图称为完全图。n 阶完全图记作 $K^{n}$
• 若一个图的阶是有限的，则称这个图为有限图，否则称这个图为无限图。
• 若一个 n 阶图的点用 1 , 2，…，n 来代表，则称它为标定图
  若在图的每一条边上赋以一个实数或者对于每个节点赋以一个实数，则称它为赋权图。

定理 1　n 阶完全图 $K^{n}$ 的度

证明：使用第一数学归纳法：
当 n=1 时，完全图为孤立图，故||K||=0,下设 n 时成立，考虑 n+1 的情形：
由于 $K^{n+1}$ 可以由 $K^{n}$ 添加 1 个顶点及 n 条边得到知：
$||K^{n+1}||=||K^{n}||+n=\frac{n(n-1)}{2}+n=\frac{n(n+1)}{2}$
得证.

定义 5　顶点的次（度）

　　 设点 $v \in V$,称图 $G$ 中以顶点 $v$ 作为端点的边数为点 $v$ 的度，记作 $d(v)$
注：顶点上的环计数时计两次

定理 2　简单图中顶点度与边数的关系

　　 在简单图 $G$ 中，有： $\sum_{v \in V}{d(v)}=2||G||$¹
证明：由简单图中的每一条边有且仅有两个端点，且两个相邻的顶点间仅有一条边立得

推论 1　简单图中奇度点个数

　　 在简单图 $G$ 中，有：$2\mid \sum\limits_{v\in V\atop 2\nmid d(v)}1$

定义 6　与度有关的特殊图元素