实用工程数学教学课件作者盛光进电子教案7图论1课件.ppt

图的连通性是图的最基本、是最重要的性质。如果我们将图设想成公路网或通讯网的话，这将有助于理解关于图的真实涵义. 7.2 图的连通性 一、路与回路 7.2 图的连通性 一、路与回路 在一条路中，若所有的边互不相同，则称其为简单路； 若所有结点互不相同（当然边也不相同），则称其为初级路（或基本路）． （1）adcfe是长度为4的简单路. （2）abedab是长度为5的路，但不是简单路. 问：deca是不是图中的一条路？ 观察图中的 路和简单路？ 7.2 图的连通性 开始和结束是同一点的路称为回路. 若回路中出现的所有的边互不相同，则称其为简单回路； 若简单回路中除起点和终点相同外，其余结点均不相同，则称其为初级回路（或圈）． （1）bcfeb是长度为4的简单回路. （2）adcfba是长度为5的简单回路. 【问题】aefbea是不是图中的一条回路？ （3）adcfea是长度为5的初级回路. 7.2 图的连通性 7.2 图的连通性 图(3)为v1到v1的长为6的简单回路. 在有向图中, 环和两条方向相反边构成的回路分别为长度为1和2的初级回路. 图(3)为v0 到v5 (= v0) 的长为5的初级回路. 图(1)为v0 到v4的长 为4的初级路. 图(2)为v0 到v8的长为8的简单路. 【问题】提出下列各图中的初级路、简单路与初级回路. 7.2 图的连通性 【问题】考察下图中开始于结点1结束于结点3的路： 1 2 3 4 P1: (1, 2, 3), P2: (1, 4, 3) P3: (1, 2, 4, 3) P4: (1, 2, 4, 1, 2, 3) P5: (1, 2, 4, 1, 4, 3) P6: (1, 1, 2, 3) 【答案】 P5是简单路但不是初级路。 P1, P2, P3是初级路, (当然也是简单路）. 指出上列六条路中，哪些是简单路，初级路？ 一条初级通路一定是简单通路, 反之不然. 7.2 图的连通性 【问题】指出下列六条路中的回路，简单回路，初级回路？ 1 2 3 4 C1: (1, 1), C2: (1, 2, 1) C3: (1, 2, 3, 1) C4: (1, 4, 3, 1) C5: (1, 2, 3, 2, 1) C6: (1, 2, 3, 2, 3, 1) 【答案】 C1, C2, C3 , C4是初级回路, (当然也是简单回路), C5是简单回路但非初级回路, C6 是回路，但既非初级回路亦非简单回路. 7.2 图的连通性 【例1】（1） 请判断下列4种路况,将左边的路与右边答案连线 ，并指明其长度. v1 v3 e4 。 。 。 。 。 v2 v4 v5 e1 e2 e3 e5 e6 e7 v1e1v2e6v5e4v4e7v2 v1e1v2e2v3e3v4e7v2e6v5e5v1 v1e5v5 e6v2 v1e1v2e7v4e4v5e5v1 v1到v2的简单通路 v1到v2的初级通路 v1到v1的简单回路 v1到v1的初级回路 7.2 图的连通性 (e2), (e3, e4, e2), (e3, e5, e6, e10, e2), 路(e3, e5, e6, e7, e1)是从C到B的4个有向路.这4条有向路只有第一条，第四条是初级的. A B C D E F e1 e2 e3 e4 e5 e6 e7 e9 e8 e10 C到c的回路：(e3, e4),(e3, e5, e6, e10),(e8),(e9)是4条有向回路;有向图G中,从B到其它任意点都没有有向路. 【例1】（2）在下图中,求C到B的通路和C到c的回路,要求各找出4个以上. C到B的通路有： 7.2 图的连通性 【例2 】“摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河．另外，不能让狼和羊、羊和菜单独留下．问怎样安排摆渡过程？ 【解】　将安全摆渡过河问题转化成图论问题，即可得到狼羊菜的安全摆渡模型． 注意这里的狼和菜是可以单独在一起的。河左岸允许出现的情况有以下10种情况（或状态）：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视