基本概念

1. 有n个顶点的图称作n阶图

2. 没有边(即边集$E=\varnothing$​)的图称作零图. 1阶零图称作平凡图，平凡图只有 一个顶点，没有边.

3. 在定义中规定顶点集非空 ，但在图的运算中可能产生顶点集为空集的结果 . 为此规定顶点集为空集的图称作空图，记作$\varnothing$​​​.

度数：

$$d_G(v_i)$$

握手定理

设$G=<V,E>$为任意一图（无向的或者有向的），$V=\{v_1,v_2,\cdots,v_n\}$，边的条数$|E|=m$，则

$$\sum^n_{i=1}{d(v_i)}=2m$$

推论

任何图(有向图或无向图)中，度数为奇数的顶点个数是偶数.

联通

联通分支的个数

$$p(G)$$