(⑦联图 设G1,G,是两个不相交的图，作G+G,并且将G,中每个顶点和G2 中的每个顶点连接，这样得到的新图称为G,与G,的联图。记为： (⑧)积图 设G1=(V1,E1),G2=(V2,E2) 是两个图。对点集V=V,×V2 的任意两个点u=(u1,u2)与v=(Wv2,当(u1=v和u2adjv2)或(u2=V2和 u1adjv)时，把u与v相连。如此得到的新图称为G,与G2的积图。 记为 G =G1×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 7 (7) 联图 设G1,G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2 中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为 ： G G 1 2 (8) 积图 设 是两个图。对点集 1 11 2 2 2 G VE G V E ( , ), ( , ), V VV 1 2 的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2)或(u2=v2和 u1adjv1)时，把u与v相连。如此得到的新图称为G1与G2的积图。 记为 GGG 1 2
(⑨)偶图 所谓具有二分类(X,Y)的偶图（或二部图）是指一个图，它的点 集可以分解为两个（非空）子集和Y,使得每条边的一个端点在中，另 一个端点在Y中 注：掌握偶图的判定。 2、树、森林，生成树，最小生成树、根树、完全m元树。 (1)树 不含圈的图称为无圈图，树是连通的无圈图。 (2)森林 称无圈图G为森林。 8
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 8 (9) 偶图 所谓具有二分类（X, Y）的偶图（或二部图）是指一个图，它的点 集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在中，另 一个端点在Y中. 注: 掌握偶图的判定。 2、树、森林，生成树，最小生成树、根树、完全m元树。 (1) 树 不含圈的图称为无圈图，树是连通的无圈图。 (2) 森林 称无圈图G为森林
3)生成树 图G的一个生成子图T如果是树，称它为G的一棵生成树；若1 为森林，称它为G的一个生成森林。 生成树的边称为树枝，G中非生成树的边称为弦。 (4)最小生成树 在连通边赋权图G中求一棵总权值最小的生成树。该生成树称 为最小生成树或最小代价树。 注：要求熟练掌握最小生成树的求法。 (⑤根树 一棵非平凡的有向树T,如果恰有一个顶点的入度为0，而其余所有顶 点的入度为1，这样的的有向树称为根树。其中入度为0的点称为树根， 出度为0的点称为树叶，入度为1，出度大于或等于1的点称为内点。又 将内点和树根统称为分支点。 9
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 9 (3) 生成树 图G的一个生成子图T如果是树，称它为G的一棵生成树；若T 为森林，称它为G的一个生成森林。 生成树的边称为树枝，G中非生成树的边称为弦。 (4) 最小生成树 在连通边赋权图G中求一棵总权值最小的生成树。该生成树称 为最小生成树或最小代价树。 注：要求熟练掌握最小生成树的求法。 (5) 根树 一棵非平凡的有向树T，如果恰有一个顶点的入度为0，而其余所有顶 点的入度为1，这样的的有向树称为根树。其中入度为0的点称为树根， 出度为0的点称为树叶，入度为1，出度大于或等于1的点称为内点。又 将内点和树根统称为分支点
(6)完全m元树 对于根树T,若每个分支点至多m个儿子，称该根树为m元根树； 若每个分支点恰有m个儿子，称它为完全m元树。 注：对于完全m元树，要弄清其结构。 3、途径（闭途径），迹（闭迹），路（圈），最短路，连通图，连 通分支，点连通度与边连通度。 注：上面概念分别在1和3章 4、欧拉图，欧拉环游，欧拉迹，哈密尔顿圈，哈密尔顿 图，哈密尔顿路，中国邮路问题，最优H圈。 10
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 10 (6) 完全m元树 对于根树T，若每个分支点至多m个儿子，称该根树为m元根树； 若每个分支点恰有m个儿子，称它为完全m元树。 注：对于完全m元树，要弄清其结构。 3、途径(闭途径)，迹(闭迹), 路(圈), 最短路，连通图，连 通分支，点连通度与边连通度。 注：上面概念分别在1和3章 4、欧拉图，欧拉环游，欧拉迹，哈密尔顿圈，哈密尔顿 图，哈密尔顿路，中国邮路问题，最优H圈
(1)! 欧拉图与欧拉环游 对于连通图G,如果G中存在经过每条边的闭迹，则称G为欧 拉图，简称G为E图。欧拉闭迹又称为欧拉环游，或欧拉回路。 (2)欧拉迹 对于连通图G,如果G中存在经过每条边的迹， 则称该迹为G 的一条欧拉迹。 (3)哈密尔顿图与哈密尔顿圈 如果经过图G的每个顶点恰好一次后能够回到出发点，称这样 的图为哈密尔顿图，简称H图。所经过的闭途径是G的一个生成圈， 称为G的哈密尔顿圈。 (4)哈密尔顿路 图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 11 (1) 欧拉图与欧拉环游 (2) 欧拉迹 对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧 拉图，简称G为E图。欧拉闭迹又称为欧拉环游，或欧拉回路。 对于连通图G，如果G中存在经过每条边的迹，则称该迹为G 的一条欧拉迹。 (3) 哈密尔顿图与哈密尔顿圈 如果经过图G的每个顶点恰好一次后能够回到出发点，称这样 的图为哈密尔顿图，简称H图。所经过的闭途径是G的一个生成圈， 称为G的哈密尔顿圈。 (4) 哈密尔顿路 图G的经过每个顶点的路称为哈密尔顿路