资源描述：
《运输配送图与网络分析(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图与网络分析问题提出应用：生产组织，邮递员问题，通讯网络等。哥尼斯堡七桥问题ABCD哥尼斯堡七桥问题在图中找一条经过每边一次且仅一次的路——欧拉回路。ADBC由点和边组成“环球旅行”问题在图中找一条经过每个点一次且仅一次的路——哈密尔顿回路。“中国邮路问题”在图中找一条经过每边的最短路——类似带权的欧拉回路。“货郎担问题”在图中找一条经过每个点一次且仅一次的最短路——带权的哈密尔顿回路。在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例1:图1是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示
2、城市，用点与点之间的线表示城市之间的铁路线。一、图与网络的基本知识太原重庆武汉南京徐州连云港上海郑州石家庄塘沽青岛济南天津北京图1例2:有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队。它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图2所示的有向图反映出来。v3v1v2v4v6v5图2一、图与网络的基本知识1.图的基本概念例1:铁路交通图例2:球队比赛图点:表示研究对象.连线：表示两个对象之间的某种特定关系。关系的对称性：两对象之间的关系可互换。边：不带箭头
3、的联线，表示对称关系。弧：带箭头的联线，表示不对称关系。无向图：简称图，由点和边组成。表示为：G=（V，E）V--点集合E--边集合例：右图V={v1，v2，v3，v4}E={e1，e2，…,e7}e1=[v1,v2]e2=[v1,v2],…,e7=[v4,v4]有向图：由点和弧组成。表示为：D=（V，A）V--点集合A--弧集合点数:p(G)或p(D)边数:q(G)弧数:q(D)v1v2v3v4v5例：右图V={v1，v2,…,v5}A={a1，a2,…,a7}a1={v1,v5},a2={v5,v4},…,a7={v1,v4}无向图的有关概念端点
4、:e=[u,v]∈E,则u,v是e的端点,称u,v相邻.关联边:e是点u,v的关联边.环:若u=v,e是环.多重边:两点之间多于一条边.简单图:无环,无多重边的图.多重图:无环,允许有多重边的图.次:以点v为端点的边的个数称为v的次.表示为:d(v)悬挂点:次为1的点.悬挂边:悬挂点的关联边.孤立点:次为0的点.奇点:次为奇数的点.偶点:次为偶数的点.孤立点悬挂边定理1:图G=(V,E)中,所有点的次之和是边数的两倍,即:定理2:任意一图中,奇点的个数为偶数.证明:设V1--奇点的集合,V2--偶点的集合偶数偶数偶数一、树及其性质在各种各样的图中，有
5、一类图是十分简单又非常具有应用价值的图，这就是树。树在自然科学和社会科学,特别是在计算机科学领域中有广泛的应用。例：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。第二节树v6v3v4v2v5v1六个城市的一个电话网就作成一个图。这个图必须是连通图。这个图必须是无圈的。图是一个不含圈的连通图，代表了一个电话线网。v6v3v4v2v5v1再比如，乒乓球单打比赛抽签后的对阵形式以及企业的组织结构图等。ABCDEFGH总经理市场总监常务副总经理学术总监市场总学术总教质部研发部人事部第二节树二、图的生成（支撑）树
6、定义15设图K=(V,E’)是图G=(V,E)的一生成（支撑）子图,如果图K=(V,E’)是一个树,那么称K是G的一个生成树。G中属于生成树的边称为树枝，不在生成树上的边称为弦。例如,图3b是图3a的一个生成树。图3v6v5v2v3v4v1av6v5v2v3v4v1b显然，如果图K=(V,E’)是图G=(V,E)的一个生成树，那么K的边数是n(G)-1，G中不属于生成树K的边数是m(G)-n(G)+1。第二节树图的生成树的求法1：定理7充分性的证明，提供了一个寻找连通图生成树的方法,叫做“破圈法”。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以
7、上步骤，直到不含圈时为止，这样就得到一个生成树。例:用破圈法求下图的一个生成树。V5V4V2V3V1e6e5e4e3e2e1e7e8第二节树圈(v1,v2,v3,v1)去e3；圈(v1,v2,v4,v3,v1)去e4；圈(v3,v4v5,v3)去e6；圈(v1,v2,v5,v4,v3,v1)去e7；得到生成树，如图所示。v2e1e2e5e8v1v3v4图8-12V5V4V2V3V1e6e5e4e3e2e1e7e8第二节树三、最小生成树问题定义16连通图G=（V，E），每条边上有非负权L(e)。一棵生成树所有树枝上权的总和，称为这个生成树的权。具有最小
8、权的生成树称为最小生成树（最小支撑树），简称最小树。这里所指的权，是具有广义的数量值。根据实际研究问题的不同
