资源描述：
《图与网络分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章图与网络分析1.图的基本概念2.树3.最短路4.最大流问题5.最小费用最大流6.中国邮递员问题图与网络分析问题提出应用：生产组织，邮递员问题，通讯网络等。哥尼斯堡七桥问题ABCD哥尼斯堡七桥问题在图中找一条经过每边一次且仅一次的路——欧拉回路。ADBC由点和边组成“环球旅行”问题在图中找一条经过每个点一次且仅一次的路——哈密尔顿回路。“中国邮路问题”在图中找一条经过每边的最短路——类似带权的欧拉回路。“货郎担问题”在图中找一条经过每个点一次且仅一次的最短路——带权的哈密尔顿回路。1.图的基本概念例1:铁路交通图例2:球队比赛图点:表示研究对象.连线：表示两个对象之
2、间的某种特定关系。关系的对称性：两对象之间的关系可互换。边：不带箭头的联线，表示对称关系。弧：带箭头的联线，表示不对称关系。无向图：简称图，有点和边组成。表示为：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
3、},…,a7={v1,v4}无向图的有关概念端点: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--偶点的集合偶数偶数偶数链：点
4、边交错系列，记为：圈：的链。初等链：点均不相同。初等圈：点均不相同。简单链：链中边均不相同。简单圈：圈中边均不相同。例：右图无重复点,无重复边有重复点,无重复边连通图：任意两点之间至少有一条链。不连通图：连通分图：对不连通图，每一连通的部分称为一个连通分图。支撑子图：对G=（V，E），若G`=(V`,E`),使V`=V,E`E,则G`是G的一个支撑子图（生成子图）.G-v:图G去掉点v及v的关联边的图.有向图的有关概念基础图:对D=(V,A),去掉图上的箭头.始点和终点:对弧a=(u,v),u为a的始点,v为a的终点.链:点弧交错序列,若在其基础图中对应一条链,则称为
5、D的一条链.圈,初等链,初等圈:类似定义.方向可以不同道路:若是D中的一条链，且，t=1,2,…,k-1,称之为从到的一条道路。回路:的路.初等路:道路中点不相同.初等回路:回路中点不相同.简单有向图:无自环,无多重弧.多重有向图:有多重弧.方向相同2.树2.1树及其性质2.2图的支撑树（生成树）2.3最小支撑树问题2.4根树及其应用2.1树及其性质例:电话线架设、比赛程序、组织结构等。树:连通的无圈的无向图称为树。树的性质：图G=（V，E），p个点、q条边下列说法是等价的（1）G是一个树（2）G连通，且恰有p-1条边。（3）G无圈，且恰有p-1条边。（4）G连通，但每
6、舍去一边就不连通。（5）G无圈，但每增加一边即得唯一一个圈。（6）G中任意两点之间恰有一条链(简单链)。2.2图的支撑树（生成树）定义:设图T=(V，E’)是图G=(V,E)的支撑子图,如果T是一个树,则称T是G的一个支撑树。定理5：图G=（V，E）有支撑树的充分必要条件是G是连通的。找图中生成树的方法：求支撑树的破圈法求支撑树的避圈法找图中生成树的方法：深探法广探法2.3最小支撑树问题赋权图(网络）:给图G=(V,E),对G中的每一条边[vi,vj],相应地有一个数wij,则称这样的图为赋权图,wij称为边[vi,vj]上的权.支撑树的权:若T=(V,E’)是G的一个
7、支撑树,E’中的所有边的权之和称为支撑树的权,记为w(T):定义:最小支撑树(最小树)T*:求最小树的避圈法:例:图8-27求最小树的破圈法:例:图8-282.4根树及其应用有向树中根树在计算机科学、决策论的应用有向树：根树：有向树T，恰有一个结点入次为0，其余各点入次为1，则称T为根树。M叉树：二叉树：根叶分点枝第一层第三层第二层三叉树带权的二叉树T：有s个叶子，权分别为pi，根到各叶子的距离（层次）为二叉树的总权数最优二叉树（Huffman树）：总权数最小的二叉树算法步骤：——Huffman算法将s个叶子按权由小到大排列，将两个最小的
