大一各科课件离散图论

图论图论 11图论图论目的：树的六种定义，了解分支、森林、生成树、生成森林、最小生成树、枝、弦、基本回路、有向树、有向优二叉树的算法、定位二元有序树和有序森林的双重点：树的六种定义，各种概念、算法及基本的证明思难点：通过树的六种定义方式如何发现树的各种性质，大22图论图论树33图论图论44图论图论G＝〈Ｖ，Ｅ，Ψn阶无向图。可以下六个条件等价G没有自圈，并且对于G的任意两结点v和v′，在G中 v至v′的基本路径。G是连通的，如果v和v′是G的两结点，e不是GΨ′=〈e，{v，v〉}G＋{e}Ψ′有唯一的G是连通的，并且对于Ge，GeG是连通的，并且有n1G是非循环的n1条边。证明参见P145–146（P193）。55图论图论定理定理12.2：设树T是一个G(n,m)图，则m=n-1证明：用归纳法证明，对Tn对于n=1和n=2，定理显然成立。设对于所有的(i,mi)树(i<n)定理都成立。 T变成具有两个连通分支的不连通图，并且这两个连通分 (n1,m1)树和 和n2<n，根据归纳假设 n1- n2-1nn1+n2mm1+m21=n1-6+n2-1+1,所以，m=n–1,定理得证 证毕6图论图论定理12.3T中至少有两片树叶T为(n,m)图，n>1，T因为：dui2m=2(n–1 (m=n–1=2n–Tk片树叶，则分支顶点为nk个，分支顶点的次数大于1，即至少为2。 2n–2≥k+2(n–k k≥ 778图论8图论图论 图论图论如果森林F有n个结点，m条边和kmn–k证明：n个顶点的树有n-顶点，则：V1+V2+…+Vk

(V1-1)+(V2-1)+…+(Vk-1)=图论图论如果树T是无向图G的生成子图，则称TG的生成树FG的生成子图，则称FSpanningTree–图论图论找连通图G的生成树的方法 “避圈法

“破圈法添加e1，…，ei，在添加的每一步均保证：ei+1不与{e１，…，ei}的任何子集构成回路。2、破圈法：在G0(即G)，G1，G2，…中去掉e1，e2，e3，… ei为Gi-1中某条回路中的边 图论图论设〈G，W〉是图，G′GG′中所有边的长度之和称为G′的长度设G是连通无向图，〈G，W〉是图MinimumSpanningTreeAminimumspanningtreeisasubgraphofanundirectedweightedgraphG,suchthatitisatree(i.e.,itisitcoversallthevertices–contains|V|-1thetotalcostassociatedwithtreeedgesistheminimumamongallpossiblespanningtreesnotnecessarily图论图论MinimumSpanningTreesProblem:LayingephoneCentralNaveCentralCentralWiring:BetterCentralMinimizethetotallengthofwireconnectingtheMinimumSpanningThequestioncanbesolvedbymanydifferentalgorithms,hereisthreeclassicalminimum-spanningtreealgorithms:Prim'sBoruvka'sKruskal's图论图论Kruskal'sAlgorithm(JosephBernardKruskal,Kruskal–Selecttheminimumweightedgethatdoesnotformacycle Kruskal'sAlgorithm- Kruskal'sAlgorithm- Prim’sAlgorithm(RobertClayPrim,Input:Anon-emptyconnectedweightedgraphwithverticesVandedgesE.Initialize:Vnew={x},wherexisanarbitrarynode(root)fromV,Enew=RepeatuntilVnew=Chooseanedge(u,v)withminimalweightsuchthatuisinVnewandvisnot(iftherearemultipleedgeswiththesameweight,anyofthemmaybepicked)AddvtoVnew,and(u,v)toOutput:VnewandEnewdescribeaminimalspanningPrim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136图论图论Boruvka'sOtakarInventorofCzechIntroducedtheTheoriginalpaperwaswritteninCzechinThepurposewastoefficientlyprovideelectriccoverageofBohemia.Prim“in图论图论设TG的生成树T的边为枝，G的不属于T的边称为弦。与给定的Te却可能是弦。G的任何生成树，枝的数目弦的数目图论设G是有m条边的n阶连通无向图，则对于G的任何生成树T，都有n–1个枝和m–n+1个弦。 图论图论由定理7.6.1知，如果在生成树中增加一条弦，则恰产生一个定义7.6.7（基本回路）设TG e e5 e e3C1=(e1,e2,e6,eC2=(e5,e6,C3=(e4,e3,e6,eG34C4=(e7,e3,G3412C={C,12

,C,

问n,m)图的生成树

图论图论§12.4定义12.2（根树）若一个有向树有一个引入次数为0的顶点，顶点的级是从树根出发到该顶点的通路的长度。 图论图论 图论常用谱系中的一些术语来描述根树中的顶点：称从顶点u出发可以到达的每一个顶点为u的后裔，称u为其后裔的祖先;称u亲;称同一个父亲的顶点互为兄弟。 Tree: Tree:

internaldescendantsofancestordescendantsofparentofchildofsiblingsiblingof的有序树。例如，图12.2的b和c表示的是同一根树，但是不everyinternalvertexhasnomorethanmchildren.Thetreeiscalledafullm-arytreeifeveryinternalvertexhasexactlymeveryinternalvertexhasnomorethanmchildren.Thetreeiscalledafullm-arytreeifeveryinternalvertexhasexactlymbinary children（完全 ）.Anm-arytreewithm=2iscalledbinaryArethesefullm-aryTheoremTheorem.Afullm-arytreewithiinternalverticesn=mi+1Everyvertex(exceptroot)isthechildofaninternalEachoftheiinternalverticeshasmTherearemivertices(otherthantheThereforen=mi+ii=4internalm=n=3×4+1= ：对每片树叶都附加了权Pi(i=1,2,…,t)的二 t

3

2图论图论7A57A5B2C4D2C4D7A5B7A5B2C (a)带权路径长度为 (b)带权路径长度为 m每一个顶点的引出次数完全m每一个顶点的引出位置m：每一个顶点的儿子都分别有确定的位置的m元

当m=2时，分别称为 ，c是位置二元

虽然d与a是同构根树，但 的左儿子的字符串为a0，u的给定一个位置二,可以得到一个前缀编码。反之, 出一个前缀编码,也能够画出对应的位置二。 例：设在通讯中7 0 55

0

1

5

5

思考 证明：假设P是T中最长的基本链，P的起点或终点的次数不为1，即它的次数至少是2，则至少有一个顶点与P的起点或终点 基础图是完全无向图的有向图有路径，试证明从G中删去顶点v及其关联边，得到G’，由归纳假设，有在G中有一条弧(v,v1)，则有有向路(v,v1,v2,…,在G中没有弧(v,v1)，则必有弧(v1,v)。若存在vi，vi是v1之后第一个碰到并且有弧(v,vi)的顶点，则显然得到一条有向路 …,vi-1,v,vi,在G中没有弧(v,vi)，而对所有vi，均有弧(vi,v)，i=1,2,n，证明：若e=n-1，因为G是连通的，所以为一棵树(树的定一个长度大于等于3的回路，则在这个回任意证明：证明恰好有两个顶点的次数为1的树必为一基本因此得到2n-2>2n-2， nt），它等于边的总数m。又因为m=n-1，故有2（n-nt）=n-1，解得n2nt-1。因此mn-12(nt-1)知：m=n-1=2(nt-1)（偶数），而m=n-1(n:奇数）。Foralln≥3,thenumberofdistinctHamiltoncyclesinthecompletegraphKnis(n−1)!/2.Proof：Inacompletegraph,everyvertexisadjacenttoeveryothervertex.Therefore,ifweweretotakealltheverticesinacompletegraphinanyorder,therewillbeapaththroughthoseverticesinthatorder.JoiningeitherendofthatpathgivesusaHamiltoncycle.Hencetherearen!waysofbuildingsuchaHamiltonNotallthesearedi