计算机七篇章.ppt

内容：二部图、欧拉图。;二部图;例1、;判断二部图的定理;例2、判断以下是否二部图。 ;二部图;同构;完备匹配;图7.4;;;三、欧拉图问题的提出。 ; 对于哥尼斯堡七桥问题，大数学家欧拉最先意识到哥尼斯堡七桥问题的求解与 A, B, C, D 的大小和它们之间的长度无关，从而将问题求解转换为对多重图的遍历，即：找到一条遍历多重图每条边恰好一次的回路。若需要，回路可以重复访问结点。;欧拉图;;注意： ; 欧拉在问题求解过程中注意到，哥尼斯堡多重图中每个结点的度数为奇数。因此，哥尼斯堡多重图中的任何结点都不能作为起始结点，因为回路都是从某个结点出发回到该结点，然后再从该结点出发再返回，如此循环往复，那么每个起始结点的度数都应是偶数。类似的，哥尼斯堡多重图中的任何结点都不能作为中间结点，因为回路都是进入某个结点后离开，然后再进入另一个结点离开，如此循坏往复，那么这些中间结点的度数也应该是偶数。 由此，欧拉得出了存在欧拉回路的一个必要条件，后又被证明该条件同时也是充分的，如此得出了下面的定理。 ;定理 无向连通图G为欧拉图(具有欧拉回路)的充分必要条件是图中各个顶点的度数都是偶数. 定理 无向连通图G是半欧拉图的充分必要条件是：图中除有2个顶点为奇度顶点外，其他各点的度数都为偶数. （欧拉图：从任意一点出发，可以一笔画出此图） （半欧拉图：从特定点出发，特定点结束可以一笔画出）;图中（1）（2）(3) 不是欧拉图, (4) 是欧拉图. ;例;例(蚂蚁比赛问题);定理 一个有向连通图D是欧拉图(具有欧拉回路),当且仅当图中每个顶点的入度和出度相等. 定理 一个有向连通图D是半欧拉图（具有欧拉通路）,当且仅当图中除了两个顶点外,其余顶点的入度均等于出度.这两个特殊的顶点中,一个顶点的入度比出度大⒈另一个顶点的入度比出度小1.;(1)既无欧拉回路,也无欧拉通路. (2)中存在欧拉通路,但无欧拉回路. (3)中存在欧拉回路. ;例;【例 】设某城市的街道布局如下图所示。每条边代表一条特定街道的一段街区，每个结点代表街区间的交点。扫雪车车库位于结点 d。证明存在一条路线使得扫雪车清扫每个街区恰好一次且清扫完最???一个街区正好返回车库。为这个扫雪车找出完成任务的路线。;解：首先，注意到图是连通的，并且每个结点的度数为偶数，那么，根据定理可以推知出图中存在欧拉回路。而图是扫雪街区布局的模型图， 所以可以推出存在一条使得扫雪车经过每个街区恰好一次最后回到车库的路线。;内容：哈密尔顿图、平面图。;哈密尔顿图;哈密尔顿图;哈密尔顿通路(回路)、哈密尔顿图;注意：;哈密尔顿图的充分条件和必要条件;例;例2、画一个无向图，使它;(3) 具有哈密尔顿回路而没有欧拉回路，;例;a; 　平面图;　两个基本的非平面图;　欧拉公式;例13.27;定理 ;欧拉公式;例;;;库拉托夫斯基定理;第三节　无向树;一、无向树的定义;例;树的等价定义;定理 设T＝V,E是n阶非平凡的树,则T中至少有2片树叶. 证明 因为T是非平凡树,所以T中每个顶点的度数都大于等于1,设有k片树叶,则有(n-k)个顶点度数大于等于2,由握手定理可知 又由树的等价定义，m＝n-1,将此结果代入上式经过整理得k≥2,这说明T至少有2片树叶.;生成树;(2)为(1)的一棵生成树T,(3)为T的余树,注意余树不一定是树.;最小生成树;Kruskal算法;　　在一个新建的城市中，煤气厂必须供应煤气给几个住宅区，需要铺设煤气管道。例如，图中的A表示煤气厂，B、C、D、E、F、G表示各住宅区，煤气管必须沿着图中所示的路线铺设，每条路线上的数字表示铺设煤气管的费用。现在问应该怎样铺设煤气管道，使煤气能供应给各个住宅区，且其费用最小？;　　;第四节 根树及其应用;有向树;左图为一棵根树。v0为树根，v1，v4,v3,v6,v7为树叶，v2,v5为内点，v0,v2,v5均为分支点。层高为3。由于在根树中有向边的方向均一致（向下），故可省掉其方向，用右图 代替。 ;家族树;在编码理论和计算机程序等问题中，常常要考虑同一层上的顶点的顺序，因而需要有序树的概念． 如果将根树每一层上的顶点都规定次序，这样的根树称为有序树． 次序可排在顶点处，也可以排在边上。次序常常是从左向右，不一定是连续的. ;设T为一棵根树： （1）若T的每个分支点至多有r个儿子，则称T为r元树； （2）若T的每个分支点都恰好有r个儿子，则称T为r元正则树； （3）若r元树T是有序的，则称T是r元有序树； （4）若r元正则树T是有序的，则称T是r元有序正则树； （5)若T是r元正则树，且所有树叶的层数相同，都等于树高，则称T为r元完全正则树； （6）若r元完全正则树T是有序树，则称T是r元有序完全正