运筹学课件：五章1-图的基本概念最小支撑树-TJF

1、图与网络分析我们身处在相互联系、不可避免的网络世界中，无论是那些直接影响我们的，还是间接影响我们的网络体系。 Martin Luther King Jr.图与网络分析问题提出哥尼斯堡七桥问题应用：道路交通网络、生产流程、煤气管道铺设、邮递员问题等。哥尼斯堡七桥问题在图中找一条经过每边一次且仅一次的路欧拉回路。“中国邮路问题”管梅谷（1962年）提出一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？在图中找一条经过每边的最短路类似带权的欧拉回路。245563344494“出行问题”-从天大到大悦城前沿：复杂网络研究

2、小世界实验Milgram小世界实验：通过信件传递发现世界上任意两个人平均距离是6前沿：复杂网络研究小世界实验Kevin Bacon（凯文贝肯）游戏：任意一个演员和Bacon一起演过电影，则其Bacon数为1。平均Bacon数为2.944。周星驰的Bacon数为3：周星驰豪门夜宴与洪金宝合作，洪金宝死亡游戏与Colleen Camp合作， Colleen Camp在陷阱中与Bacon合作。混好莱坞且活跃在银屏上的各国影人，或不怎么混好莱坞但有一定资历的外国影人，Bacon number多为12。Brad Pitt（布拉德皮特）：1Denzel Washington（丹泽尔华盛顿）：2Takesh

3、i Kitano（黑泽明）：2Yun-Fat Chow（周润发）：2Zhang Ziyi（章子怡）：2用图表示比赛情况有A、B、C、D、E五支球队，他们之间的比赛情况可以用图表示出来。已知A队和其他各队都比赛过一次，B队和A、C队比赛过，D队和E、C队比赛过，E队和A、D队比赛过。该如何表示？用图表示比赛情况如果在比赛中：A胜E，B胜C，A胜D，C胜A，E胜D，A胜B，该如何表示？2022/7/26 第一节 图的基本概念1 . 图与子图e1e2e3e5e6e4e7v3v2v1v4如 G：图是由一些点和一些点之间的联线（带箭头或不带箭头）所组成。记作G=(V，E)或D =(V，A) ，其中V=(

4、v1，v2，vn)表示点的集合，E=(e1，e2，em) 为边的集合， A=(a1，a2，am) 为弧的集合。2022/7/26 第一节 图的基本概念1 . 图与子图e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如 G：2022/7/26 第一节 图的基本概念2 . 简单图一个结点对包含多条边，称为多重边。简单图：无环、无多重边的图。否则称为多重图。2022/7/263 . 关联与相邻4 . 链与圈2022/7/265. 有向图与无向图，圈，回路比较：2022/7/266. 树 例1 已知有5个城市，要在它们之间架设电话线网，要求任2城市都可通话（允许通

5、过其它城市），并且电话线的根数最少。v1v2v3v5v4 特点：连通、无圈。树无圈的连通图，记为T。2022/7/26v1v2v3v5v4树的性质：（1）树的任2点间有且仅有1链； （2）在树中任去掉1边，则不连通； （3）在树中不相邻2点间添1边，恰成1圈； （4）若树T有m个顶点，则T有m-1条边。2022/7/267.图的部分（支撑）树 若图G=（V，E）的子图T=（V，E）是树，则称T为G的部分树或支撑树。特点边少、点不少。性质：G连通，则G必有部分树。2022/7/26第二节 网络分析网络赋权图，记D=（V，E，C），其中C=c1，cn， ci为边ei上的权（设ci ）。网络分析主要

6、内容最小部分树、最短路、最大流。2022/7/26一. 最小部分（支撑）树问题问题：求网络D的部分树，使其权和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例 2 求如图网络的最小部分树。v5v1v3v6v4v2v72552335757112022/7/26避圈法是一种选边的过程，其步骤如下：1. 从网络D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；2. 把顶点集V分为互补的两部分V1, 1 ，其中2022/7/26用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分树如图上红线所示；最小权和为14。思考：破圈法是怎样做的呢？见圈就破，去掉其中权最大的。避圈法-例32022/7/2614321672253用避圈法求解一下问题的最小树：2022/7/26143216722531432167225314321672253与边相关联的点2022/7/261432