《图论及其应用.doc》由会员分享，可在线阅读，更多相关《图论及其应用.doc（58页珍藏版）》请在金锄头文库上搜索。
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，selfloop）：如边 l。棱（link）：如边ae。重边：如边p及边q
2、。简单图：（simple graph）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：。习题1.1.1 若G为简单图，则 。1.1.2 n ( 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)之间各存在一一对应关系，且这二对应关系保持关联关系。 记为 G F。注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。注 判定两个图是否同构是NP-hard问题。完全
3、图(complete graph) Kn空图（empty g.） E = 。V ( V) 为独立集 V中任二顶点都互不相邻。二部图（偶图，bipartite g.） 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-部 图等。例。用标号法判定二部图。习题1.2.1 G H n(G) = n(H) , e(G) = e(H) 。 并证明其逆命题不成立。1.2.2 证明
4、下面两个图不同构：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). e(Tm,n) = 其中 k =n/m . (b)*. 对任意的n顶点完全m-部图G，一定有 e(G) e(Tm,n)，且仅当G Tm,n时等式才成立。1.2.7 所谓k-方体是这样的图
5、：其顶点是由0与1组成的有序k-元组，其二顶点相邻当且仅当它们恰有一个坐标不同。证明k-方体有个顶点，k*2 k-1条边，且是一偶图。1.2.8 简单图G的补图G c 是指和G有相同顶点集V的一个简单图，在G c中两个顶点相邻当且仅当它们在G不相邻。 (a). 画出Kcn和 Kcm,n。 (b). 如果G G c则称简单图G为自补的。证明：若G是自补的，则 n 0, 1 (mod 4) 关联矩阵M(G)与邻接矩阵A(G)M(G)=mi,jn*e,A(G)=ai,jn*n ,其中 mi,j = 顶点vi与边ej 的关联次数= 0, 1, 2. ai,j = 连接顶点vi 与 vj 的边数 。 例
6、。 子图子图(subgraph) H G V(H) V(G) , E(H) E(G) 。真子图 H G。母图（super graph）。生成子图（spanning subg.） H G 且V(H) = V(G) 。生成母图。基础简单图 （underlying simple g.）。导出子图（induced subg.）GV, (非空V V ) 以V为顶点集，以G中两端都在V上的边全体为边集构成的G的子图。边导出子图 GE 非空E E 以E为边集，以E中所有边的端点为顶点集的的子图。例。以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算：G - V 去掉V及与V相关联的
7、一切边所得的剩余子图。 即 GV VG - E 从中去掉E 后所得的生成子图例。G - b, d, g, ( = GE b, d, g ) G - b, c, d, g, ( GE b, c, d, g ) G - a, e, f, g. ( GE a, e, f, g )注意 GE E 与G - E 虽有相同的边集，但两者不一定相等 ： 后者一定是生成子图，而前者则不然。上述四种运算是最基本取子图运算，今后老要遇到，一定要认真掌握好。关于子图的一些定义还有：G + E 往G上加新边集E 所得的（G的母）图。为简单计，今后将G e 简计为 G e ； G - v 简计为 G - v 。设 G1
8、, G2 G ，称G1与G2为不相交的（disjiont） V(G1) V(G2) = ( E(G1) E(G2) = ) 边不相交 （edge-distjiont） E(G1) E(G2 ) = 。( 但这时G1与G2仍可能为相交的）。并图 G1G2 , 当不相交时可简记为 G1+G2. 交图 G1G2 .习题1.4.1 证明：完全图的每个导出子图是完全图；偶图的每个导出子图是偶图。1.4.2 设G为一 完全图，1 n 0)的2-划分为 (X, Y),则 |X| = |Y|。1.5.3 在人数 1的人群中，总有二人在该人群中有相同的朋友数。1.5.4 设V(G) = ，则称 ( d(v1),
9、 d(v2), . , d(vn) ) 为G的度序列。证明：非负整数序列 ( d1 ,d 2, ., d n) 为某一图的度序列 是偶数。 1.5.5 证明：任一 无环图G都包含一 偶生成子图H，使得 dH(v) dG(v)/2 对所有v V 成立。1.5.6* 设平面上有n个点，其中任二点间的距离 1，证明：最多有 3n对点的 距离 = 1 。 路和连通性途径 （walk) 例如 （u，x）-途径 W = ueyfvgyhwbvgydxdydx (有限非空序列） = uyvywvyxyx (简写法-当不引起混淆时）起点（origin） u 。终点（terminus） x。内部顶点（inter
10、nal vertex） y, v, w, x。 （注意，中间出现的x也叫内部顶点。）长 边数（重复计算）。节（段，section）。 例如W的(y, w)-节=yvw 。W-1 （逆途径）, WW（两条途径W与W相衔接）。迹( trail) 边各不相同的途径。 例如，yvwyx 。路 (path) 顶点各不相同的途径。（可当作一个图或子图)。例如， yvwx 。d(u, v) = u与v之间最短路的长。例。（命题）G中存在(u, v)-途径 G中存在(u, v)-路。G中顶点u与v为连通的(connected) G中存在(u, v)-路 ( G中存在(u, v)-途径。)V上的连通性是V上的等
11、价关系，它将V划分为（等价类）：V1,.,Vw使每个Vi中的任二顶点u及v都连通（即存在(u, v)-路）。 称每个GVi i=1,2,.w为G的一个分支（component）; 称w(G）为G的分支数。G为连通图 w(G) = 1 G中任两点间都有一 条路相连。G为非连通图 w(G) 1。记号 对任一非空 SV ，令 = VS, 记（称为边割） S, = G中 一 端在S中，另一 端在中 的一切边的集合。例。（命题）G连通 对任 S V 都有 S, 例。（命题） 简单图G中， d k G中有 长 k 的路。习题1.6.1 证明：G中长k为的(vi ,vj )-途径的数目, 就是A k中的(I, j)元素。1.6.2 证明：对简单图G有， G连通。对于n 1，试给出的不连通简单图。1.6.3 简单图G中， d n/2 - 1 G连通。 当n是偶数时，试给出一个不连通的(n/2-1)正则简单
