图论概念定理知识点梳理

1、图论基本知识点梳理第一部分(基本概念)1.G连通的充分必要条件是0(G)=1。或若|V(G)|=2k,且对VvV(G),有d(v)之k,则G是连通图。4.图G为二分图当且仅当G中无奇圈。5.在仅两个奇次顶点的图中，此二奇次顶点连通。6.设G为简单图，若6(G)22,则G中有圈。7 .设G为简单图，若5(G)之3,则G中有偶圈。具体地，(1)单星妖怪中有偶圈。(2)在k正则图G中，若k至3,则G中有偶圈。8.简单图G与其补图Gc不能都不连通。29.在的三角剖分中，正常三角形为奇数个。10.以下等价(1)G是树(无圈连通图)。(2)G中任两顶点间恰有一条轨。(3)G无圈，w=v1。(4)G是连通图

2、，1。(5)G是连通图，且对G的任意边e,G-e不连通。(树每边皆割边)(6)G无圈，且对任一不在E(G)的边e,G+e恰含一个圈。11 .若G连通，则(G)v(G)-1oG的生成树是G最小的连通生成子图。12 .G是连通图的充分必要条件是G有生成树。13 .v2的树 T T 至少有两个叶。14.完全图Kn的生成树个数T(Kn)=nn。15 .图G可平面嵌入的充分必要条件是G可以球面嵌入。(染地球上各国等价于染地图上各国)16 .(Euler公式)G是连通平面图，则Y-w+=2.17.证明：若G是v23的连通平面图，则0O23单星妖怪的边色数是4。24二分图的边色数等于图的最大度。25 .简单

3、图G的边色数(G)WS(G)d(G)+“。26 .M M 与N是图G的无公共边的匹配，且|M|N|,则存在无公共边的匹配 M M与 N N , ,使得|M日M|-1,|N|=|N|+1,MN=MUN。27G是有边二分图的充要条件是7(G)=2。28 .G是无边图的充要条件是7(G)=1。29 .G是完全图的充要条件是7(G)=|V(G)|。30.设Wn为轮图，则有当n为偶数时，X(Wn)=3,当n为奇数时，(Wn)=4o31 .平面图的色数不大于5。32.图G的颜色多项式P(G,k)=k(k1)(kv+1)的充要条件是G=Kv。33图G的颜色多项式P(G,k)=k的充要条件是|E(G)|=0。

4、34.图G的颜色多项式P(G,k)是k的Y次多项式，n=|V(G)|,且降哥排列时，首项为kv,第二项为-水,，无常数项，系数是正负交替出现的整数，其中E=|E(G)|。35.图G的颜色多项式P(G,k)满足：P(Ge,K)=P(Ge,k)+P(G,k)。36 .图G的颜色多项式P(G,k)=k(k1)W当且仅当G是v顶的树。若图G的颜色多项式P(G,k)=k(k1)v;则G是连通图，且w=v1。37 .I I 为G的独立集的充要条件是V(G)-I是G的覆盖集。38 .若I为G的极大独立集，则V(G)-I是G的极小覆盖集。39 .图G的独立数久(G)与覆盖数P(G)满足a(G)+P(G)=|V

5、(G)|。40.平凡的Ramsey数：r(1,l)=r(k,1)=1,r(2,l)=l,r(k,2)=k,r(k,l)=r(l,k)41 .关于二维Ramsey数，正确的是：r(3,3)=6,r(3,4)=9,r(3,5)=14,r(4,5)=25。42 .k与l是不小于2的自然数，则r(k,l)2,则Ramsey数r(k,l)EC：；/。kRamsey数r(k,k)不小于2244 .对于连通图G,(1)G是Euler图的充要条件是G无奇度点。(2)G是Euler图的充要条彳是G可表示为无公共边的圈之并。45 .连通图G有Euler行迹当且仅当G中至多两个奇度点。46 .若G的每顶皆偶度，则G

6、中无割边。47 .G是Hamilton图的必要条件是VS仁V(G),S#巾，有切(GS)E|S|,其中切(,)是连通分支数。48.设|V(G)户3,G的任一对顶 u,vu,v 皆有d(u)+d(v)|V(G)|-1-1，则G有Hamilton轨；若d(u)+d(v)JV(G)|,则G是Hamilton图。注：由“设|V(G)上3,G的任一对顶 u,vu,v 皆有d(u)+d(v)之|V(G)|11可得G为连通图。49 .(1)阶至少为3的完全图是Hamilton图。(2)完全偶图Km,m(m至2)为Hamilton图。50 .Kmm中有 1 1m ml l 个两两无公共边的Hamilton圈。

7、251 .G是强连通有向图当且仅当G存在有向生成回路。52 .当且仅当无向图G是无桥连通图时，G可定向成强连通有向图。53 .G是单连通有向图当且仅当G中有含G的一切顶的有向道路。54 .竞赛图是定向的无向完全图。55 .若有向图的底图为G,则此图中有长为7(G)-1的有向轨。每个竞赛图皆有有向Hamilton轨。56 .G是无向图，则可对G的边定向，使得到的有向图中的最长有向轨长(G)-1o57 .竞赛图中得分最多的顶为王。反之不成立。58 .n阶竞赛图G有唯一王的充要条件是v得分n-1。59 .(泛圈定理)V至3的强连通竞赛图G的每个顶点都包含在有向k圈中，3k2,则G为Hamilton图

8、。63 .Heawood定理平面图的色数不超过5。64 .碳氢化合物中氢原子个数为偶数。65.大于7公斤的整公斤的重量都可以仅用一些3公斤和5公斤的两种祛码来称量.67.各边相异的道路称为行迹.68.各顶相异的道路称为轨道.69.图G是二分图当且仅当G中无奇圈.70.无零次与1次顶的单图中有圈.71 .设G是单图，若6(G)3,则G中有偶圈.75 .、M2.：.v76.任取n个人组成的人群，n22,至少有两位，他们在这个人群中的朋友一样多.77 .G连通的必要条件是名(G)v(G)-1.82.设G为平面图，59)=力/j,即是图6的面集合，氏9)|=名，则d(fi)=2;.i183 .若G是v

9、23的平面图，当u,vWV(G),而uWE(G)时，G+uv不再是平面图，则称G是极大平面图.84 .M M 是图G的边子集，且 M M 中任两边在G中不相邻，则称 M M 是G的一个匹配.85 .G中每个顶点皆被 M M 许配，则称 M M 为G的完备匹配或完美匹配.86.设 M M 是图G中的匹配，G中的一条轨P(u,v),u,v未被 M M 许配，但P(u,v)上边交替地不在 M M 中出现与在 M M 中出现，则称P(u,v)为 M M 的可增广轨.87 .无桥三次正则图有完备匹配.88 .k次正则图有完备匹配，kA0.89.匹配理论Berge定理 M M 是图G中的最大匹配当且仅当G

10、无 M M 的可增广轨.Hall定理设G是具有二分类(X,Y)的二分图，存在将 X X 中顶皆许配的匹配的充分必要条件是VS=X,|N(S)mS|.其中N(S)是S中每个顶的邻顶组成的S的邻集.K?nig定理若G为二分图，则其最大匹配的边数为G的覆盖数P(G).Tutte定理图G由完备匹配当且仅当VSCV(G),O(G-S)R满足(1)0f(e)c(e),eeE(G);f(e)=f(e),vwVs,t,其中覆(v)e：Xv)e：=|.：v)是以v为头的边的边集，P(v)是以v为尾的边的边集。称f为网络N上的流函数。91 .设N(G,s,t,c(e)是定义在有向图G上的网络，f为网络N上的流函数

11、，称F一f(e)-f(e)e；(t)eq(t)为流函数f的流量。92.设N(G,s,t,c(e)是定义在有向图G上的网络，SuV(G),sS,tV(G)S,则称C(S)=Zc(e)为截(S,S)的截量。e.(S,S)93.设N(G,s,t,c(e)是定义在有向图G上的网络，S=V(G),(S,S)为网络的截，则网络N上的流函数f的流量 F F 等于工f(e)-工f(e)。e.(S,S)e.(S,S)94.设N(G,s,t,c(e)是定义在有向图G上的网络，S=V(G),C(S)为(S,S)的截量，F F 为流函数的流量，则 F F 与C(S)满足不等式FC(S)。95.设N(G,s,t,c(e

12、)是定义在有向图G上的网络，S=V(G),C(S)为(S,S)的截量，F F 为流函数的流量。若F=C(S)。则 F F 是网络的最大流，C(S)是网络的最小截量。96.设N(G,s,t,c(e)是定义在有向图G上的网络，(S,S)为网络的截，f为网络的流函数。则f是最大流，(S,S)是最小截的充分必要条件为F=C(S)。第二部分(算法及应用)1、Kruskal算法的基本步骤及应用。设G是连通加权图，求G的最优树.(1)从E(G)中选一条权最小的边e1.(2)若e,e2,，e已选出，则从E(G)e,e2,，e中选e书,使得(a)Ge,q,，e,e书中无圈，(b)w(e+)=min.(3)反复执

13、行上述过程直至选出e止.2. huffman算法的基本步骤为：a(1)初始：令S=WI,W2,，wt;(2)从S中取出两个权值最小者w与w,画结点Vi,带权w，画结点Vj,带权Wj,画Vi与Vj的父亲V,连接Vi与V,连接Vj与V,令V带权W1十w2;令S=(S-w1,w2)=w+也;(4)判断S只含一个元素，若是，停止，否则转2).3. dijkstra算法(见课本)4、设G=Kn,n为加权完全二分图，且具有二分类(X,Y)。求G的最佳匹配的KM算法的步骤如下：(1)选定初始定标l,构造相等子图Gl,在Gl取定初始匹配M。(2)若X中顶皆被 M M 许配，止。M M 即为所求的最佳匹配；否则取Gl中未被 M M 许配的顶U,令S=u,T=弧若NGl(S)nT,转(4),若NGl(S)=T,取%=xm%a(