离散数学 图论 部分笔记

握手定理： 任何图中，所有结点的度数之和等于边数的两倍

推论：任何图中，奇数度的结点必有偶数个

无向完全图kn共有n（n-1）/2条边

有向完全图kn共有n*n条边

同构必要条件：

1.结点数相等

2.边数相等

3.度数相同的结点数目相等

对于有向图

每个结点可以到每个结点叫强连通

一个结点可以到每个结点叫单侧连通

底图（有向图去方向所得无向图）连通则称为弱连通

强连通必是单侧联通，单侧连通必是弱连通

G是连通平面图，G中所有面的次数之和等于其边数的两倍

G是连通平面图，有n个结点，m条边，r个面，则 n - m + r = 2 成立

G是连通平面图，有n个结点，m条边，若n≥3，则 m ≤ 3n - 6

G是连通平面图，有n个结点，m条边，若每个面至少由k边围成，有 m ≤ k（ n - 2 ）/ k - 2

库拉托夫斯基定理：一个图是平面图，当且仅当他不包括k3.3和k5同胚的子图

一个子图是强连通图，且子图中不存在另一个更大的强连通子图，则该子图叫强分图

一个子图是单侧连通图，且子图中不存在另一个更大的单侧连通子图，则该子图叫单侧分图

无向图是连通图，当且仅当他的可达矩阵所有元素均为1

有向图是强连通图，当且仅当他的可达矩阵所有元素均为1

有向图是单向连通图，当且仅当他的可达矩阵与其转置的并的所有元素均为1

有向图是弱连通图，当且仅当他的邻接矩阵与其转置的并的作为邻接矩阵求得的可达矩阵所有元素均为1

一条路所有结点不同，称路为通路

一条路所有边不同，称为迹

通路一定是迹

起点与终点相同的通路叫圈

起点与终点相同的迹叫闭迹

圈一定是闭迹

包含所有边的迹称为欧拉迹/欧拉路

包含所有边的闭迹称为欧拉回路，含欧拉回路的图称为欧拉图

包含所有结点的通路称为汉密尔顿路

包含所有结点的圈称为汉密尔顿圈，含汉密尔顿圈的图称为汉密尔顿图

G是欧拉图，当且仅当它是连通的，并且每个结点的入度等于其出度

G是欧拉图，当且仅当它是联通的，并且每个结点的度数均为偶数

存在割点的图不是汉密尔顿图

G是连通平面图，G中所有面的次数之和等于其边数的两倍

G是连通平面图，有n个结点，m条边，r个面，则 n - m + r = 2 成立

G是连通平面图，有n个结点，m条边，若n≥3，则 m ≤ 3n - 6

G是连通平面图，有n个结点，m条边，若每个面至少由k边围成，有 m ≤ k（ n - 2 ）/ k - 2

库拉托夫斯基定理：一个图是平面图，当且仅当他不包括k3.3和k5同胚的子图