图论及其应用图论及其应用图论及其应用.doc

图和子图图和简单图 图G=(V,E),其中 V={}V---顶点集,---顶点数 E={}E---边集,---边数例。左图中, V={a,b,......,f}, E={p,q,ae,af,......,ce,cf} 注意,左图仅仅是图G的几何实现(代表),它们有无穷多个。真正的图G是上面所给出式子,它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。 称边ad与顶点a(及d)相关联。也称顶点b(及f)与边bf相关联。 称顶点a与e相邻。称有公共端点的一些边彼此相邻,例如p与af。 环(loop,selfloop):如边l。 棱(link):如边ae。 重边:如边p及边q。 简单图:(simplegraph)无环,无重边平凡图:仅有一个顶点的图(可有多条环)。一条边的端点:它的两个顶点。记号:。,则。(³4)个人中,若每4人中一定有一人认识其他3人,则一定有一人认识其他n-1人。同构在下图中, 图G恒等于图H,记为G=HÛV(G)=V(H),E(G)=E(H)。 图G同构于图FÛV(G)与V(F),E(G)与E(F)之间各存在一一对应关系,且这二对应关系保持关联关系。记为GF。注往往将同构慨念引伸到非标号图中,以表达两个图在结构上是否相同。注判定两个图是否同构是NP-hard问题。pletegraph)Kn空图(emptyg.)ÛE=Æ。V’(ÍV)为独立集ÛV’中任二顶点都互不相邻。二部图(偶图,bipartiteg.)G=(X,Y;E)Û存在V(G)的一个2-划分(X,Y),使X与Y都是独立集。完全二部图Km,nÛ二部图G=(X,Y),其中X和Y之间的每对顶点都相邻,且|X|=m,|Y|=n。类似地可定义,完全三部图(例如Km,n,p),完全n-部图等。例。用标号法判定二部图。.******@HÞn(G)=n(H),e(G)=e(H)。并证明其逆命题不成立。1..::Û存在一一映射f:V(G)®V(H),使得uvÎE(G)当且仅当f(u)f(v)ÎE(H)。:(a).e(Km,n)=mn;(b).对简单二部图有e£n2/,n为这样的一个完全m-部图:其顶点数为n,每个部分的顶点数为[n/m]或{n/m}个。证明:(a).e(Tm,n)=其中k=[n/m].(b)*.对任意的n顶点完全m-部图G,一定有e(G)£e(Tm,n),且仅当******@Tm,n时等式才成立。-方体是这样的图:其顶点是由0与1组成的有序k-元组,其二顶点相邻当且仅当它们恰有一个坐标不同。证明k-方体有个顶点,k*2k-1条边,且是一偶图。,在Gc中两个顶点相邻当且仅当它们在G不相邻。(a).和Kcm,n。(b).如果******@Gc则称简单图G为自补的。证明:若G是自补的,则nº0,1(mod4)关联矩阵M(G)与邻接矩阵A(G)M(G)=[mi,j]n*e,A(G)=[ai,j]n*n, 其中mi,j=顶点vi与边ej的关联次数=0,1,2. ai,j=连接顶点vi与vj的边数。例。子图子图(subgraph)HÍGÛV(H)ÍV(G),E(H)ÍE(G)。真子图HÌG。母图(supergraph)。生成子图(spanningsubg.)ÛHÍG且V(H)=V(G)。生成母图。基础简单图(underlyingsimpleg.)。导出子图(inducedsubg.)G[V’],(非空V’ÍV) Û以V’为顶点集,以G中两端都在V’上的边全体为边集构成的G的子图。边导出子图G[E’]非空E’ÍE Û以E’为边集,以E’中所有边的端点为顶点集的的子图。例。以上两种子图,其实,对应于取子图的两种基本运算。下面是取子图的另两种基本运算:G-V’Û去掉V’及与V’相关联的一切边所得的剩余子图。Û即G[V\V’]G-E’Û从中去掉E’后所得的生成子图例。G-{b,d,g},(=G[E\{b,d,g}]) G-{b,c,d,g},(¹G[E\{b,c,d,g}]) G-{a,e,f,g}.(¹G[E\{a,e,f,g}])注意G[E\E’]与G-E’虽有相同的边集,但两者不一定相等:后者一定是生成子图,而前者则不然。上述四种运算是最基本取子图运算,今后老要遇到,一定要认真掌握好。关于子图的一些定义还有:G+E’Û往G上加新边集E’所得的(G的母)图。为简单计,今后将 G±{e}简计为G±e;G-{v}简计为G-v。设G1,G2ÍG,称G1与G2为不相交的(disjiont)ÛV(G1)ÇV(G2)=Æ (\E(G1)ÇE(G2)