会计学本章(běnzhānɡ)主要内容§1图的基本概念//抽象(chōuxiàng)问题的图蛋白质相互作用图基因(jīyīn)相互作用关系图具体问题的图：城市之间的铁路交通图、地铁线路图、航空线路图等。抽象问题的图：球队进行比赛的关系图、一群人的认识关系图、社交网络图、基因(jīyīn)调控关系图等一、无向(wúxiànɡ)图中的一些概念定理(dìnglǐ)1.图G=(V,E)中，所有点的次之和是边数的两倍.即链：图G=(V,E)中一个点边交替(jiāotì)的序列子图、支撑(zhīchēng)子图：图G=(V,E),G´=(V´,E´),若V´V，E´E，则称G´是G的子图；V´=V，E´E，则称G´是G的支撑(zhīchēng)子图。二、有向图中的一些(yīxiē)概念引例:自来水管道的铺设问题校门A点(水源(shuǐyuán));需要使用自来水的场所共有7个:v1,v2,…,v7;问题:为了各个场所都用上自来水,怎样铺设管道才能使挖开的道路数目最少?§2最小树问题(wèntí)树的定义(dìngyì)及性质树的性质：1.设G是一个(yīɡè)树，p(G)2,则G中至少有两个悬挂点。2.如下三个论断中的两个保证G是树：（1）连通;（2）无圈;（3）q(G)=p(G)-1.3.G=(V,E)是一个(yīɡè)树的充要条件是G中任意两个顶点间有且仅有一条链。4.从一个(yīɡè)树中去掉任意一条边，则余下的图是不连通的。5.在树中不相邻的两个点间添上一条边，恰好得到一个(yīɡè)圈。图的支撑(zhīchēng)树连通(liántōng)图的支撑树满足：（1）支撑性；（2）连通(liántōng)性；（3）无圈性。破圈法避圈法反圈法最小树问题(wèntí)支撑树的权：如果T=(V,E)是G的一个(yīɡè)支撑树，则称E中所有边的权之和为支撑树T的权，记为w(T)。即最小支撑树：如果支撑树T*的权w(T*)是G的所有(suǒyǒu)支撑树的权中最小者，则称T*是G的最小支撑树（简称最小树）。求最小树的方法(fāngfǎ)破圈法避圈法反圈法Step1从图G中任取一点vi,让viS,其余(qíyú)各点均包含在S=V\S中。Step2从（S,S)中选一条权最小的边e=vivj，加到T中。Step3令SvjS,S\vjS，(将所选边的另一个顶点添加到S中）。Step4重复2、3两步，直到图中所有点均包含在S中为止。课堂练习：1.分别用三种(sānzhǒnɡ)方法求下图的最小支撑树作业(zuòyè)P221：第3题§3最短路(duǎnlù)问题问题(wèntí)的提出2.最短路问题(wèntí)的Dijkstra算法3.假若v2到v3的边权不知道(zhīdào)(如下图)，还能否确定从v1到v3的最短路？例：某人要从甲地到乙地，可以(kěyǐ)选择的路线共有4条，分别需要经过A、B、C、D四个地方，如下图。假如经过A、B去乙地的路长已知；而从甲地经过C、D到乙地的路长未知，但是从甲到C、D的路长已知，分别为20、45公里，那么能否确定从甲地经过A、B、C、D哪个地方去乙地最近？算法的实现过程：从起点出发，逐步(zhúbù)向外探寻最短路，直到终点。算法的步骤：1.给始点vs（最短路的起点）标号[0，0]。2.确定割并计算相应的指标值：由所有一个端点(duāndiǎn)已标号另一个端点(duāndiǎn)未标号的边构成割，记为：3扩大(kuòdà)标号范围。找出当前割中指标值最小的一条边，给该边的未标号点vj标号（kij,vi）。4.重复2、3两步，直到终点vt得到标号为止。/例3：求下图中v1到v8的最短路(duǎnlù)。３.求任意两点之间最短距离的矩阵(jǔzhèn)算法课堂练习:求下图中v1到其它(qítā)各点的最短路及路长§4最大流问题(wèntí)问题(wèntí)的提出基本(jīběn)概念与基本(jīběn)定理2.可行流与最大流可行流：满足以下条件的流1)容量限制(xiànzhì)：对任意(vi,vj)A，0fijcij。2)平衡条件：中间点：流入量=流出量发点：流出量-流入量=流量v(f)收点：流入量-流出量=流量v(f)3.增广(zēnɡɡuǎnɡ)链4.割集与割的容量(róngliàng)3.寻求(xúnqiú)最大流的标号法（FordFulkerson）（1）标号(biāohào)过程：重复上述过程，直到vt得到标号(biāohào)或标号(biāohào)范围无法扩大为止。若vt得到标号(biāohào)，则可找到一条增广链，否则算法结束。例1：用标号法求下列(xiàliè)网络的最大流vs解（1）由于(yóuyú)各条