5、匹配、最大匹配、完美匹配、最优匹配、因子分解。 (1)匹配 匹配M--如果M是图G的边子集（不含环），且M中的任意两条边没有 共同顶点，则称M是G的一个匹配或对集或边独立集。 (2)最大匹配与完美匹配 最大匹配M--如果M是图G的包含边数最多的匹配，称M是G的一个 最大匹配。特别是，若最大匹配饱和了G的所有顶点，称它为G的一 个完美匹配。 (3)最优匹配 设G=X,Y)是边赋权完全偶图，G中的一个权值最大的完美匹配称为G 的最优匹配
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12 5、匹配、最大匹配、完美匹配、最优匹配、因子分解。 (1) 匹配 匹配 M--- 如果M是图G的边子集(不含环），且M中的任意两条边没有 共同顶点，则称M是G的一个匹配或对集或边独立集。 (2) 最大匹配与完美匹配 最大匹配 M--- 如果M是图G的包含边数最多的匹配，称M是G的一个 最大匹配。特别是，若最大匹配饱和了G的所有顶点，称它为G的一 个完美匹配。 (3) 最优匹配 设G=(X, Y)是边赋权完全偶图，G中的一个权值最大的完美匹配称为G 的最优匹配
(4)因子分解 所谓一个图G的因子分解，是指把图G分解为若干个边不重的因子 之并。 注 要弄清楚因子分解和完美匹配之间的联系与区别。 6、平面图、极大平面图、 极大外平面图、平面图的对偶 图。 (1)平面图：如果能把图G画在平面上，使得除顶点外，边与边之 间没有交叉，称G可以嵌入平面，或称G是可平面图。可平面图G的边 不交叉的一种画法，称为G的一种平面嵌入，G的平面嵌入表示的图称 为平面图
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 (4) 因子分解 所谓一个图G的因子分解，是指把图G分解为若干个边不重的因子 之并。 注：要弄清楚因子分解和完美匹配之间的联系与区别。 6、平面图、极大平面图、极大外平面图、平面图的对偶 图。 (1) 平面图： 如果能把图G画在平面上，使得除顶点外，边与边之 间没有交叉，称G可以嵌入平面，或称G是可平面图。可平面图G的边 不交叉的一种画法，称为G的一种平面嵌入，G的平面嵌入表示的图称 为平面图
(2)极大平面图：设G是简单可平面图，如果G是Ki(1i至4)，或者在 G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图， 则称G是极大可平面图。 极大可平面图的平面嵌入称为极大平面图。 (3)极大外平面图：若一个可平面图G存在一种平面嵌入， 使得其所有 顶点均在某个面的边界上，称该图为外可平面图。外可平面图的一种 外平面嵌入，称为外平面图。 (4)平面图的对偶图：给定平面图G,G的对偶图G*如下构造： 1)在G的每个面f内取一个点y*作为G*的一个顶点； 2)对G的一条边e,若e是面与f的公共边，则连接y*与y*,且连线 穿过边e;若e是面fi中的割边，则以y为顶点作环，且让它与e相交
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 (2) 极大平面图: 设G是简单可平面图，如果G是Ki (1≦i≦4),或者在 G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图， 则称G是极大可平面图。 极大可平面图的平面嵌入称为极大平面图。 (3) 极大外平面图：若一个可平面图G存在一种平面嵌入，使得其所有 顶点均在某个面的边界上，称该图为外可平面图。外可平面图的一种 外平面嵌入，称为外平面图。 (4) 平面图的对偶图：给定平面图G，G的对偶图G*如下构造： 1) 在G的每个面fi内取一个点vi*作为G*的一个顶点； 2) 对G的一条边e, 若e是面 fi 与 fj 的公共边，则连接vi*与vj*，且连线 穿过边e;若e是面fi中的割边，则以vi为顶点作环，且让它与e相交
7、边色数、点色数、色多项式 (1)、边色数 设G是图，对G进行正常边着色需要的最少颜色数，称为G的边色 数，记为：x(G) (2)、点色数 对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图 G的点色数用x(G) 表示。 (3)、色多项式 对图进行正常顶点着色，其方式数P(G)是k的多项式，称为图G 的色多项式。 5
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 7、边色数、点色数、色多项式 (1)、边色数 设G是图，对G进行正常边着色需要的最少颜色数，称为G的边色 数，记为： ( ) G (2)、点色数 对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图 G的点色数用 表示。 ( ) G (3)、色多项式 对图进行正常顶点着色，其方式数Pk(G)是k的多项式，称为图G 的色多项式
8、强连通图、单向连通图、弱连通图 (1)、强连通图 若D的中任意两点是双向连通的，称D是强连通图； (2)、弱连通图 若D的基础图是连通的，称D是弱连通图； (3)、单向连通图 若D的中任意两点是单向连通的，称D是单向连通图。 16
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 8、强连通图、单向连通图、弱连通图 (1)、强连通图 (2)、弱连通图 (3)、单向连通图 若D的基础图是连通的，称D是弱连通图； 若D的中任意两点是单向连通的，称D是单向连通图。 若D的中任意两点是双向连通的，称D是强连通图；