图的基本概念

p(G)为顶点数，q(G)为边数，d(v)为顶点的度

简单图

如果一个图，无环无重边，则称为简单图。

定理1.2.5： 完全图

若图G每一对不同的顶点恰有一条边连接，则称此图为完全图，具有n个顶点的完全图记为K_n。

其边数E = n*(n-1)/2

定理1.2.7： 二分图（偶图）

若把简单图G的顶点集合分成两个不相交的非空集合V₁和V₂ ,使得图G中的每一条边，与其关联的两个顶点分别在V₁和V₂中，则G称为二分图或者偶图。

定理1.3.1： 握手定理

任何图中所有顶点的度之和必为偶数

定理1.3.2

在任何图中G=（V,E)中，顶点的度为奇数的个数必为偶数

证明：证明每个碳氢化合物的分子所含的氢原子数是偶数。

因为碳和氢的原子价分别4价和1价，所以氢原子的顶点的度为1 ，是奇数，由定理1.3.2可知，顶点的度为奇数的个数必为偶数，所以氢原子的个数一定是偶数。

推论1.3.3

非负整数序列是某个图的序列，当且仅当度之和为偶数。

可绘图序列的判定算法

（1）从序列S中删除第一个数K

（2）如果S的第一个数到第K个数都都大于等于一，则将这个K个数分别减去一，得到新序列S¹；否则，停止，得到结论：原序列不可绘图。如果全部序列全为 0 ，停止，得到结论： 原序列可以绘图。

（3）将序列S¹按照非递减排序

（4）令S = S¹

例如序列 3 ，2 ，2 ， 1 ， 1， 1是否可绘图

​ 2 ， 2 ， 1 ，1 ，1

​ 1， 1， 0 ，1 ，1

​ 1 ， 1， 1 ，1 ，0

​ 1 ， 1 ， 1， 0

​ 0 ，1， 1 ， 0

​ 1 ， 1 ，0， 0

​ 1 ，0， 0

​ 0 ， 0 ，0

此时，说明原序列可绘图

​

定理1.5.1

若简单图G 中的每一个顶点的度至少是K（K >=2）,则G 中必然包含一条长度最少是回路是K+1。

证明： 在G 的所有路中，取一条最长路，那么起点V₀和顶点的V_t的所有邻边都在其中，如果不是，则与最长路矛盾。而 V₀ 的度大于等于K，K大于等于2。这些K个邻接点构成的路径w长度至少为K-1，则V₀ - W - V₀ 至少为K+1

定理1.5.4 连通图

设u和v是图G 的任意两个顶点，都存在一条u-v路，则称图G是连通的。否则，称为非连通图。

定义1.5.6 割点

图G 的顶点u称之为割点，如果图G删去顶点u后，图G 的连通分支数增加。

定理1.5.5

若图G 是P阶段连通图，则q(G) >= p-1

度为1 的点称之为悬挂点

定理1.5.6

设连通图至少有两个顶点，且边数小于顶点数，则此图至少有一个悬挂点。