图
贡献者： xiaokuc; huanglei0829
- 该领域（图论）的相关概念尚不完善
- 缺少参考文献，
- 本文存在未完成的内容。
1. 1.基础定义
定义 1 图；顶点；边
图 $G(V,E)$ 是集合 V 上的一种二元关系 $E$。
集合 $V$ 的元素称为图的顶点，若两个顶点之间有这种确定的二元关系，则称有一条边连这两个点。
一个图的顶点的数目称为这个图的阶,记 作 $|G|$，图的边的数目称为它的度，记作 $||G||$。
定义 2 关联；相邻
- 若有一条边连一个图的某两个顶点，则称这两个顶点相邻，并称这两个顶点为这条边的端点。
- 若某一顶点是某一条边的端点，则称这个顶点和这条边关联。
- 若两条边和同一顶点关联，则称这两条边相邻.
2. 2.特殊图元素
定义 3 特殊点；特殊边
- 两个端点是同一个顶点的边称为环。
- 若某条边的两个端点不是同一个顶点，且只有一条边连这两个顶点，则称这条边为杆。
- 以某两顶点为端点的边可能不止一条，这时称连这两个顶点的边为重边。
定义 4 特殊图
- 只有一个顶点而没有边的图称为平凡图，没有边的图称为孤立图。
- 既可以有环，也可以有重边的图称为准图.
没有环而可能有重边的图称为带重图.
没有重边而可能有环的图称为带环图.
既没有重边也没有环的图称为简单图,每两个顶点都相邻的简单图称为完全图。n 阶完全图记作 $K^{n}$
- 若一个图的阶是有限的，则称这个图为有限图，否则称这个图为无限图。
- 若一个 n 阶图的点用 1 , 2，…，n 来代表，则称它为标定图
若在图的每一条边上赋以一个实数或者对于每个节点赋以一个实数，则称它为赋权图。
定理 1 n 阶完全图 $K^{n}$ 的度
\begin{equation}
||K^{n}||=\frac{n(n-1)}{2}~.
\end{equation}
证明：使用第一数学归纳法：
当 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}$
得证.
3. 3.点的性质
定义 5 顶点的次（度）
设点 $v \in V$,称图 $G$ 中以顶点 $v$ 作为端点的边数为点 $v$ 的度，记作 $d(v)$
注：顶点上的环计数时计两次
定理 2 简单图中顶点度与边数的关系
在简单图 $G$ 中，有：
$\sum_{v \in V}{d(v)}=2||G||$1
证明：由简单图中的每一条边有且仅有两个端点，且两个相邻的顶点间仅有一条边立得
推论 1 简单图中奇度点个数
在简单图 $G$ 中，有：$2\mid \sum\limits_{v\in V\atop 2\nmid d(v)}1$
定义 6 与度有关的特殊图元素
注：以上内容参考了《数学辞海》卷二
1. ^ 有时称为握手引理(Handshaking Lemma)
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。