大一各科课件-离散图论

1图论1图论 图论图论树、有向目的：树的六种定义，了解分支、森林、生成树、生成森、最小生成树、枝、弦、基本回路、有向树、有向优二叉树的算法、定位二元有序树和有序森林的双重点：树的六种定义，各种概念、算法及基本的证明思2难点：通过树的六种定义方式如何发现树的各种性质，大23图论3图论树非循环的连通无向图称为树4图论4图论图论图论定理G＝〈Ｖ，Ｅ，Ψn阶无向图。可以下六个条件等价G是连通的，又是非循环的G没有自圈，并且对于G的任意两结点v和v′，在G中 v至v′的基本路径。G是连通的，v和v′是G的两结点，e不是GΨ〈e，{v，v〉}G＋{e}Ψ′有唯一的G是连通的Ge，Ge5G是连通的，并且有n–1条边。vi)G是非循环的，并且有n1条边。证明参见P145–146（P193）。5图论图论定理定理12.2T是一个G(n,m)图，则mn-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.3：非平凡树T中至少有两片树叶证明：设T为(n,m)图，n>1，T因为：dui2m=2(n–1 (m=n–1=2n–Tk片树叶，则分支顶点为nk个，分支顶点的次数大于1，即至少为2。 2n–2≥k+2(n–k7 k≥ 78图论8图论图论森每个分支都是树的无向图称为森林 图论图论定如果森林F有n个结点，m条边和kmn–k证明：n个顶点的树有n-顶点，则：V1+V2+…+Vk

条边，设每个分支有Vi(V1-1)+(V2-1)+…+(Vk-1)=图论图论生成树、生成如果树T是无向图G的生成子图，则称TG的生成树FG的生成子图，则称FSpanningTree–图论图论找连通图的生成树找连通图G的生成树的方法 1、避圈法

添加e1，…，ei，在添加的每一步均保证：ei+1不与{e１，…，ei}的任何子集构成回路。2、破圈法：在G0(即G)，G1，G2，…中去掉e1，e2，e3，…eiGi-1即把G中的所有回路均挑若Gi无圈，则TG←Gi并终止；否则转+1←Gi- 图论 图，G′G 长度之和称为G′ 长度设G是连通无向图，〈G，W〉 图G的所有生成树 长度最小者称为〈G，W〉的最小生成树 MinimumSpanningTreeAminimumspanningtreeisasubgraphofanundirectedweightedgraphG,suchthatitisatree(i.e.,itisitcoversallthevertices–contains|V|-1thetotalcostassociatedwithtreeedgesisminimumamongallpossiblespanningnotnecessarily图论MinimumSpanningTreesProblem: ephoneCentral NaveCentralCentralWiring:BetterCentralMinimizethetotallengthofwireconnectingtheMinimumSpanningThequestioncanbesolvedbymanyalgorithms,hereisthreeclassicalminimum-spanningtreealgorithms:Prim's图论图论Kruskal'sAlgorithm(JosephBernardKruskal,Kruskal–SelecttheminimumweightedgethatdoesnotformacycleKruskal算法(避圈法) 设G是n个顶点的带权连通无向图设已选取的边为e1e2，…，ei，在G中选取不同于e1e2…，ei的边ei+1，使ei+1与{e1e2，…，ei中的边不构成圈，并且（4）ii+1，转 Kruskal'sAlgorithm- Kruskal'sAlgorithm- Prim’sAlgorithm(RobertClayPrim,Input:Anon-emptyconnectedweightedgraphwithverticesVedgesEInitialize:Vnew={x},wherexisanarbitrarynode(root)fromV,Enew=RepeatuntilVnew=Chooseanedge(u,v)withminimalweightsuchthatuisinVnewandvis(iftherearemultipleedgeswiththesameweight,anyofthemmaybeAddvtoVnew,and(u,v)toOutput:VnewandEnewdescribeaminimalspanningPrim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-99136Prim'sAlgorithm-966 Prim'sAlgorithm-966 Prim'sAlgorithm-99136图论图论Boruvka'sOtakarInventorofCzechIntroducedtheTheoriginalpaperwaswritteninCzechThepurposewastoefficientlyprovidecoverageofPrim“in图论图论设TG的生成树T的边为枝G的不属于T的边称为弦与给定的TeG的任何生成树，枝的数目弦的数目图论定设G是有m条边的n阶连通无向图，则对于G的任何生成树T，都有n–1个枝和m–n+1个弦。 图论图论基本回路（圈由定理7.6.1知，如果在生成树中增加一条弦，则恰产生一个G的只包含一条弦的回路称为基本回路 所有基本圈构成的集合，称为关于生成树TG的基本圈组e e5 e e3C1=(e1,e2,e6,eC2=(e5,e6,C3=(e4,e3,e6,eG234基本圈C4=(e7,e3,G234基本圈11

,C,

C} 问(n,m图的生成树

有多图论图论课后实验目§12.4定义12.2（根树）若一个有向树有一个引入次数为0的顶点，根树是一种特殊的有树叶：在根树中，称引出次数为0的顶点为顶点的级是从树根出发到该顶点的通路的长度。所有结点的级的最大值称为有向树的高 图论图论有向每个弱分支都是有向树的有向图称为有向森林 图论常用谱系中的一些术语来描述根树中的顶点：称从顶点u出发可以到达的每一个顶点为u的后裔，称u为其后裔的祖先;称u亲;称同一个父亲的顶点互为兄弟。 Tree: internalinternalancestorancestorofdescendantsofparentparentofchildofsiblingsiblingof有序树:给根树的顶点或弧都指定了次序的根有序林:每个连通分支都是有序树的的有序树。例如，图12.2的b和c表示的是同一根树，但是不Definition2Arootedtreeiscalledanm-arytree(m元树）ifeveryinternalvertexhasnomorethanmchildrenThetreeiscalledafullm-arytreeifeveryinternalvertexhasexactlymchildren（完全n元树）Anm-arytreewithm2iscalledabinarytree.Arethesefullm-aryTheoremTheorem.Afullm-arytreewithiinternalverticesn=mi+1Everyvertex(exceptroot)isthechildofaninternalEachoftheiinternalverticeshasmTherearemivertices(otherthantheThereforen=mi+ii=4internalm=n=3×4+1=最优二元(叉）树及其t为带权二元树T的权

树中，称权最小的带权二元树为最优二元树。3

2图论图论7A57A5B2C4D2C4D7A5B7A5B2C (a)带权路径长度为 (b)带权路径长度为 最优二叉树的Huffman输入：正实数序列w1,w2,…,wtT棵根树（森林），其根的权分别是w1,w2,…,wt ）2重复第2步，直至形成一注意结果可能不唯一(如果“当前”权最小顶点对不唯一)位置m元树：每一个顶点的儿子都分别有确定的位置的m元

图12.3a是二元树，b是完当m2时，分别称为二元树，二元树，c是位置二元树完全二元树和位置二元树

虽然d与a是同构根位置二元树的前缀编码表示树根的左儿子的字符串为a0，u的位置二元树的前缀编码｜a是树叶对应的字符串}给定一个位置二元树,可以得到一个前缀编码。反之,给出一个前缀编码,也能够画出对应的位置二元树。最优二元树的例：设在通讯中7个字母出现的频率如 0 55数位为：（（5＋5）×4＋（10＋10＋15）

0

1

5

5

思考 证明：假设P是T中最长的基本链，P的起点或终点的次数不为，即它的次数至少是2，则至少有一个顶点与P的起点或终点邻接，因存更长与是中的本链 因树T中最长基本链的起点和终点次数必为1。基础图是完全无向图的有向图有 路径，试证明假设n个顶点时成立，设G是n+1个顶点，且满足上述条件从G中删去顶点v及其关联边，得到G’，由归纳假设， （v1,v2,…,vn),G在G中有一条弧(v,v1)，则 有向路(v,v1,v2,…,在G中没有弧(v,v1)，则必有弧(v1,v)。若存在vi，vi是v1之后第一个到并且有弧 vi)的顶点，则显然得到一 有向路 …,vi-1,v,vi,在G中没有弧(vvi)，而对所有vi，均有弧(viv)，i=12n，则若G是简单连通图，边数为e，结点数为n。若e>=n，G至少有3棵生成树/*只需证明e=n时，命题成立证明：若e=n-1，因为G是连通的，所以为一棵树(树的定一个长度大于等于3的回路，则在这个回任意证明：证明恰好有两个顶点的次数为1的树必为一基本证明：假设T是任意一个恰好有两个顶点的次数为1的树，如果T不是一基本链则至少有一个分支顶点的次数大于2。设T有n个顶点，则T有n-2个分顶点(去除两片叶子），n-1条边。根据握手定理，T的顶点的度数之等于T的边数的2倍，可>2+2（n-2）（两片叶子次数+所有次数为2的分支结点的次数因此得到2n-2>2n-2， nt），它等于边的总数m。又因为m=n-1，故有2（n-nt）=n-1，解得n2nt-1。因此mn-12(nt-1)证明：设完全二元树T有n个顶点，条边，它有n片树叶，由上题知：m=1=2nt（）m=。另：有（的路C’为G中的最长路，则C是图G 回路/*反证法证明令C的长度为m。若C不 回路，则圈外必存在一圈上与v关联的一边为e，则C-e的长度为m-而C-e+uv的长度为m；得C-e不是最长路 Foralln≥3,thenumberofdistinctHamiltoncyclesinthecompletegraphKnis(n−1)!/2.Proof：Inacompletegraph,everyvertexisadjacenttoeveryothervertex.Therefore,ifweweretotakealltheverticesinacompletegraphinanyorder,therewillbeapaththroughthoseverticesinthatorder.JoiningeitherendofthatpathgivesusaHamiltoncy