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

《实用工程数学 教学课件 ppt 作者 盛光进电子教案ppt 7图论2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、无向图的矩阵表示一有向图的矩阵表示二7.3图的矩阵表示第三节图的矩阵表示7.3图的矩阵表示图可以用数学定义来描述，也可以用图形表示，还可以用矩阵来表示.一、无向图的矩阵表示1.无向图的关联矩阵7.3图的矩阵表示无向图的关联矩阵中的元素的确定【例1】已知图，写出图的矩阵.【解】图的矩阵表示为7.3图的矩阵表示关联矩阵的性质：7.3图的矩阵表示显然矩阵中的元素mij可能取值为0(vi与ej不关联)，1(vi与ej关联1次)，2(vi与ej关联2次，即ej是以vi为端点的环).v3v1e4v2v4v5e1e3e5e6e7v6e210001000000010010010001

2、100100011000200010v1v2v3v4v5v6e1e2e3e4e5e6e7图的关联矩阵例，写出下图的关联矩阵7.3图的矩阵表示习题7-3，4.求图7－27的关联矩阵．关联矩阵为7.3图的矩阵表示例如，下图的邻接矩阵为A【定义2】设是无向简单图，，令其中矩阵中的元素为两点间的边的条数，则称矩阵为的G邻接矩阵，记作A(G)，简记A.7.3图的矩阵表示无向简单图的邻接矩阵【问题】根据下图，写出其邻接矩阵?【答案】其邻接矩阵为：7.3图的矩阵表示习题7-3，5.求图7－28的邻接矩阵．邻接矩阵为7.3图的矩阵表示二、有向图的矩阵表示1.有向图的关联矩阵例如，下图

3、的关联矩阵是：【定义3】设是无环有向图，，,令7.3图的矩阵表示有向图的关联矩阵的性质例如，下有向图的关联矩阵为：-1-11100001-10100000-101-11000-1-117.3图的矩阵表示2.有向图的邻接矩阵v1例如，下图的邻接矩阵是？邻接矩阵中的元素为起点到终点的边的条数7.3图的矩阵表示邻接矩阵的性质①若邻接矩阵的元素全为零,则其对应的图是零图．②若对角线元素为1,则表其对应结点上有环．③若对角线元素为零，其余元素全为1，则其对应图为完全图．④矩阵某结点行的和为出度,列的和为入度．⑤矩阵所有元素之和为图的边的总数．【问题】指出下图的邻接矩阵.v1v2

4、v3v41210001000010010v1v2v3v4v1v2v3v4【答案】图的邻接矩阵：7.3图的矩阵表示P151，习题7-3，4（1）写出图的邻接矩阵7.3图的矩阵表示3.有向图的可达矩阵例如，下图的可达矩阵P为7.3图的矩阵表示v1v2v3v41111011100110011P(D)=v1v2v3v4v1v2v3v4【问题】写出下图的可达矩阵.【答案】图的可达矩阵为第四节欧拉图与哈密顿图7.4欧拉图与哈密顿图二欧拉图的应用欧拉图一四哈密顿图的应用三哈密顿图哥尼斯堡七桥问题如何不重复地走完七桥后回到起点？陆地岛屿岛屿陆地一、欧拉图抽象转化7.4欧拉图与哈密顿图

5、7.4欧拉图与哈密顿图4个图中,不能一笔画出图①,②,而能一笔画出图③,④且在④中笔又能回到出发点。①ABCD②③笔不离开纸，不重复地走完所有的边，(回到原处或不回到原处），就是所谓的一笔画.下面哪些图能一笔画？找出能一笔画的图规律？④ABCDEFGHJ12345678910111213147.4欧拉图与哈密顿图【定义1】通过图中每条边恰好一次,且经过所有顶点的路称为欧拉路.通过图中每条边恰好一次且经过所有顶点的回路称为欧拉回路.具有欧拉回路的图称为欧拉图.具有欧拉路而无欧拉回路的图称为半欧拉图。存在欧拉回路，是欧拉图.只存在欧拉路，无回路.不是欧拉图，是半欧拉图.一

6、、欧拉图7.4欧拉图与哈密顿图【例1】下列各图，哪些是欧拉图，哪些是半欧拉图?或者两者都不是.【解】图（a）中有欧拉回路:abcdeca,所以图（a）是欧拉图.图（b）中存在欧拉路：abcdac，但不存在欧拉回路，所以图（b）不是欧拉图，但是半欧拉图.(a)cacbde(b)cabcd(C)图（C）中不存在欧拉路，自然不存在欧拉回路，所以图（b）两者都不是.一个图满足什么样要的条件才存在欧拉回路呢？7.4欧拉图与哈密顿图一、欧拉图【定理1】(1)无向连通图具有欧拉回路的充要条件是：图中所有结点的度数是偶数．(2)无向连通图具有欧拉路而无欧拉回路的充要条件是：图中恰有两

7、个奇度结点（其余结点的度数全为偶数），并且这两个奇度结点是欧拉路的两个端点．ABCD根据无向图中，欧拉回路和欧拉路的判别准则知，哥尼斯堡七桥问题有了准确的答案.由于,故不存在欧拉路，当然也就不存在欧拉回路，因此一次走完所有的桥的路线是不存在的.7.4欧拉图与哈密顿图【例2】据欧拉图和欧拉路的判别准则知，下图中，由于图⑴、⑵中每个结点的度数都是偶数，则存在欧拉回路，都是欧拉图，故可以一笔画.图⑶中，不是恰有两个奇度结点，而是有四个奇度结点，则不存在欧拉通路，故不能一笔画．（2）（1）（3）7.4欧拉图与哈密顿图【问题】考察下图是否为欧拉图或存在欧拉通路