资源描述：
《图论及其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图和子图图和简单图图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，selfl
2、oop）：如边l。棱（link）：如边ae。重边：如边p及边q。简单图：（simplegraph）无环，无重边平凡图：仅有一个顶点的图（可有多条环）。一条边的端点：它的两个顶点。记号：。习题1.1.1若G为简单图，则。1.1.2n(³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
3、。注往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。58注判定两个图是否同构是NP-hard问题。完全图(completegraph)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之间的每对顶点都相邻，且
4、X
5、=m,
6、Y
7、=n。类似地可定义，完全三部图（例如Km,n,p），完全n-部图
8、等。例。用标号法判定二部图。习题1.2.1G@HÞn(G)=n(H),e(G)=e(H)。并证明其逆命题不成立。1..2.2证明下面两个图不同构：1.2.3证明下面两个图是同构的：1.2.4证明两个简单图G和H同构Û存在一一映射f:V(G)®V(H)，使得uvÎE(G)当且仅当f(u)f(v)ÎE(H)。1.2.5证明：(a).e(Km,n)=mn;(b).对简单二部图有e£n2/4.1.2.6记Tm,n为这样的一个完全m-部图：其顶点数为n，每个部分的顶点数为[n/m]或{n/m}个。证明：(a).
9、e(Tm,n)=其中k=[n/m].(b)*.对任意的n顶点完全m-部图G，一定有e(G)£e(Tm,n)，且仅当G@Tm,n时等式才成立。1.2.7所谓k-方体是这样的图：其顶点是由0与1组成的有序k-元组，其二顶点相邻当且仅当它们恰有一个坐标不同。证明k-方体有个顶点，k*2k-1条边，且是一偶图。581.2.8简单图G的补图Gc是指和G有相同顶点集V的一个简单图，在Gc中两个顶点相邻当且仅当它们在G不相邻。(a).画出Kcn和Kcm,n。(b).如果G@Gc则称简单图G为自补的。证明：若G是自补
10、的，则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[
11、V’],(非空V’ÍV)Û以V’为顶点集，以G中两端都在V’上的边全体为边集构成的G的子图。边导出子图G[E’]非空E’ÍEÛ以E’为边集，以E’中所有边的端点为顶点集的的子图。例。58以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算：G-V’Û去掉V’及与V’相关联的一切边所得的剩余子图。Û即G[VV’]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,
12、g}.(¹G[E{a,e,f,g}])注意G[EE’]与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)=Æ)边
