图论-基本概念

《图论-基本概念》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1图论-基本概念回顾2布尔代数有限布尔代数提要3图的定义用图建模图的表示图的运算图的同构Königsberg七桥问题4问题的抽象：用顶点表示对象-“地块”用边表示对象之间的关系-“有桥相连”AADDCCBB图的定义Graph常常省略，写作：5G=(V,E)图G是一个三元组：G=(V,E,)V是非空顶点集，E是边集，且V⋂E=；:E(V),且eE.1

2、(e)

3、2.(e)称为边e的端点集.举例（数据中心、通信链接）底特律纽约旧金山丹佛芝加哥华盛顿洛杉矶图的定义（续）6图G=(V,E,)是

4、简单图，如果每条边有2个端点，即：eE.

5、(e)

6、=2，并且不同边有不同端点集，即：如果ee，则(e)(e)1212图G=(V,E,)是伪图，如果存在一条只有1个端点的边，即:eE.

7、(e)

8、=1，或者00有两条边具有相同的端点集，即:ee.(e)=(e)1212图的定义（续）7伪图（包含环或者多重边）示例底特律纽约旧金山丹佛芝加哥华盛顿洛杉矶图的定义（有向图）8有向图G是一个三元组：G=(V,E,)V是非空顶点集，E是有向边（弧）集，且V⋂E=；:EVV,若(e)=(u,v),

9、则u和v分别称为e的起点和终点.举例（简单有向图）底特律纽约旧金山丹佛芝加哥华盛顿洛杉矶图的术语9无向图G=(V,E,),(e)={u,v}u和v在G里邻接（相邻）e关联（连接）顶点u和v图G中顶点v的度,deg(v)，d(v)G与该顶点关联的边数，环为顶点的度做出双倍贡献。底特律纽约旧金山丹佛芝加哥华盛顿洛杉矶握手定理10无向图G有m条边，n个顶点v1,…vn.nd(vi)2mi1推论：无向图中奇数度顶点必是偶数个。图的术语（续）11有向图G=(V,E,),(e)=(u,v)u是e的起点，v是e的终点

10、假设uv，u邻接到v，v从u邻接有向图中顶点的出度和入度++d(v)=以v为始点的边的条数，deg(v)G--d(v)=以v为终点的边的条数，deg(v)G有向图中各顶点的出度之和等于入度之和。vVdeg+(v)=vVdeg-(v)=

11、E

12、有向图的底图特殊的简单图（完全图）12若简单图G中任意两点均相邻，则称为完全图。记为K,其中n是图中顶点数。nK中每个顶点皆为n-1度，总边数为n(n-1)/2。n边数达到上限的简单图。K1K2K3K4K5特殊的简单图（圈图与轮图）13CycleC3C4C5WheelW3W4W

13、5特殊的简单图（立方体图）14n-cube1101111011100101010011010001000001Q1QQ23正则图：顶点度相同的简单图子图15设G=,G’=,如果V’V,E’E,则称G’是G的子图。如果V’V,或者E’E,则称为真子图。诱导(导出)子图：可以由顶点集的子集，或者由边集的子集导出一个子图。图模型16交通网络航空、公路、铁路信息网络万维网图（WebGraph）引用图（CitationGraph）社会网络熟人关系图合作图，好莱坞图呼叫图体育（循环赛的图模型）

14、循环赛的冠军是哪个队？18BAC是什么思考帮助我们建模？问题的答案是什么？FDE优先图和程序并发执行19右边的程序有没有办法执行快一点？s1

15、

16、s2;s3

17、

18、s4;s5

19、

20、s6是什么思考帮助我们建模？问题的答案是什么？“巧渡河”问题20问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能架船。图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。起始状态是“人狼羊菜”，结束状态是“空”。问题的解：找到一条从起始状态到结束状态的尽可能短的

21、通路。“巧渡河”问题的解21注意：在“人狼羊菜”的16种组合种允许出现的只有10种。人羊狼菜人狼菜人羊狼人羊菜人羊狼菜狼菜羊空(成功)考试时间编排问题22问题：排考试时间，一方面要总时间尽可能短(假设教室没问题)，另一方面一个同学所选的任意两门课不能同时间。图模型：每门课程对应一个顶点。任意两点相邻当且仅当对应的两门课程有相同的选课人。解：用不同颜色给顶点着色。相邻的点不能同颜色。则最少着色数即至少需要的考试时间段数(可以将颜色相同的点所对应的课程安排在同一时间)。中国邮递员问题（管梅谷，1960）23邮递员从邮局出发，走过辖区

22、内每条街道至少一次，再回邮局，如何选择最短路线？Euler回路？添加重复边（权和最小）。旅行商(TSP)问题24n个城市间均有道路，但距离不等，旅行商从某地出发，走过其它n-1个城市，且只