离散数学第七章图论.ppt

该【离散数学第七章图论 】是由【1557281760】上传分享，文档一共【179】页，该文档可以免费在线阅读，需要了解更多关于【离散数学第七章图论 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第七章图论2024/3/281图论的起源问题:能否从河岸或小岛出发,不重复地经过所有的桥回到原地。Konigsberg(哥尼斯堡)七桥问题2024/3/282Euler将河岸和小岛作为图的结点,七座桥为边,构成一个无向重图,问题化为图论中简单道路的问题。Euler(欧拉)1736年对这个问题给出了否定的回答。2024/3/283一、图的基本概念洛杉矶旧金山芝加哥丹佛华盛顿底特律纽约2024/3/284设A、B是两个集合,称A&B={{a,b}|a?A,b?B}为A与B的无序积。为方便起见,常将无序对{a,b}记为(a,b)<V,E>,记为G,其中(1)V≠?称为结点集,元素称为结点或顶点;(2)E称为边集,它是无序积V&V的多重子集,其元素称为无向边,简称为边。常把无向图记为G=<V,E>2024/3/285例1、G1=<V,E>V={v0,v1,v2,v3}E={(v0,v2),(v0,v3),(v1,v2),(v1,v3),(v2,v3)}v0v3v2v1G12024/3/286G2v0v1v2v3例2、G2=<V,E>V={v0,v1,v2,v3}E={(v0,v3),(v1,v3),(v1,v3),(v2,v3),(v0,v0)}平行边环G简单图(不含平行边也不含环)多重图2024/3/287洛杉矶旧金山芝加哥丹佛华盛顿底特律纽约2024/3/<V,E>,记为D,其中(1)V同无向图;(2)E称为边集,它是笛卡尔积V×V的多重子集,其元素称为有向边,简称为边。v0v1v2DD=<V,E>V={v0,v1,v2},E={<v0,v1>,<v1,v0>,<v1,v2>}2024/3/289例3、D=<V,E>,其中V={v1,v2,v3,v4}E={<v1,v1>,<v1,v2>,<v2,v3>,<v2,v4>,<v3,v4>,<v3,v4>,<v2,v1>}v1v2v3v4平行边2024/3/2810