运筹学讲义 §2.1.2图的基本概念(2) 子图 给定图G=(VE),G1=(V1E1),若VcV,E1E,则称G1为G的子图( subgraph),称G 为G1的母图( supergraph),记作:G三G 若G1∈G,但G1≠G,则称G1为G的真子图( proper subgraph),记作:G1cG 若G1是G的子图,且V1=V(E1sE),则称G1为G的支撑(生成)子图(s ubgraph) 注:(1)二分图的任一子图也均为二分图.(2)边数为E的图的所有(同构或不同构)支撑子图 的个数为C+C+C+…+C=2 例1画出K,的所有不同构的支撑子图 解:K4的不同构的支撑子图共有11个,分别为 C2=6 E=0 E =4
运 筹 学 讲 义 1 §2.1.2 图的基本概念(2) 子图 给定图 G = (V, E)， ( , ) G1 = V1 E1 ，若 V1 V,E1 E ，则称 G1 为 G 的子图（subgraph），称 G 为 G1 的母图（supergraph），记作： G1 G . 若 G1 G ，但 G1 G ，则称 G1 为 G 的真子图（proper subgraph），记作： G1 G . 若 G1 是 G 的子图，且 ( ) V1 =V E1 E ，则称 G1 为 G 的支撑（生成）子图（spanning subgraph）. 注：（1）二分图的任一子图也均为二分图.（2）边数为 的图的所有（同构或不同构）支撑子图 的个数为 2 0 1 2 C + C + C ++ C = . 例 1 画出 K4 的所有不同构的支撑子图. 解： K4 的不同构的支撑子图共有 11 个，分别为 6 2 = C4 = = 0 =1 = 2 = 3 = 4
运筹学讲义 E=5 注:(1)K4的支撑子图共有2=26=64个,但不同构的支撑子图仅有11个 (2)K4的所有不同构的支撑子图的个数与顶点数为4的所有不同构的简单图的个数是相同的的 (都是11个).为什么? 点导出子图( vertex- induced subgraph):([]=(V1,辆两个端点均在V中的G的边}), 规定:G-H=G[V(去掉顶点及与顶点相关联的边);特别地,G-v=Gv v1 1 3 v3 显然,完全图的任一点导出子图必定也是完全图 在图G的所有以ScV为顶点集的子图中,以点导出子图G[S]含有的边数为最多 边导出子图( edge-induced subgraph):OE1]=({E中的边的端点},E1) 规定:G-E1=GE\E1](仅去掉边);特别地,G-e=Gv{e门 e1,e2,6]G-{e3,e4,es} 注:图的去点导出子图和去边导出子图可类比“皮”与“毛”的关系去解释 显然,若G是简单图,则v∈V,有E(G-v)=E(G)-d(v) 定义图G1=(1,E1)和G2=(2,E2)的和(并, union):G1+G2=(V1UV2,E1∪E2) 联(join):G1VG2=G1+G2+{nvu∈V1,∈H2}
运 筹 学 讲 义 2 = 5 = 6 注：（1） K4 的支撑子图共有 2 2 64 6 2 4 = = C 个，但不同构的支撑子图仅有 11 个. （2） K4 的所有不同构的支撑子图的个数与顶点数为 4 的所有不同构的简单图的个数是相同的的 （都是 11 个）.为什么？ 点导出子图（vertex-induced subgraph）： [ ] ( ,{ }) G V1 = V1 两个端点均在V1中的G的边 ， 规定： [ \ ] G V1 G V V1 − = （去掉顶点及与顶点相关联的边）；特别地， G v G[V \{v}] − = . 如 显然，完全图的任一点．导出子图必定也是完全图. 在图 G 的所有以 S V 为顶点集的子图中，以点导出子图 G[S] 含有的边数为最多. 边导出子图（edge-induced subgraph）： [ ] ({ }, ) G E1 = E1中的边的端点 E1 . 规定： [ \ ] G E1 G E E1 − = （仅去掉边）；特别地， G e G[V \{e}] − = . 注：图的去点导出子图和去边导出子图可类比“皮”与“毛”的关系去解释. 显然，若 G 是简单图，则 v V ，有 (G − v) = (G) − d(v) . 定义 图 ( , ) G1 = V1 E1 和 ( , ) G2 = V2 E2 的和（并，union）： ( , ) G1 +G2 = V1 V2 E1 E2 . 联（join）： G1 G2 = G1 +G2 + { | , } 1 V2 uv uV v
运筹学讲义 GVG 轮(whe):W=CK1(n≥3) 轮辐:Wn中的Cn和K1之间的边 轮辐 we W 补图( complementary graph:G=((G)E(K,)\E(G) (The complement G of a simple graph G is the simple graph with the vertex set v(G),two vertices being adjacent in G if and only if they are not adjacent in G.) G 注:(1)G+G=K( unl on),GnG=V(G)( intersection),E(O∩E(G)=Φ 1(G)=v(GC)=v,(G)+(G)=E(K,)=C2;(2)K=v个顶点的空图,KCn=Kn+Kn (3)+,-用于图之间的运算,∪,∩用于集合之间的运算.(4)(对称性)G与GC互为补图 自补图(self- complementary graph): a simple graph g is self- complementary if C≡G
运 筹 学 讲 义 3 轮（wheel）： ( 3) Wn = Cn K1 n . 轮辐： Wn 中的 Cn 和 K1 之间的边. 补图（complementary graph）： G (V(G),E(K ) \ E(G)) p C = （The complement C G of a simple graph G is the simple graph with the vertex set V (G) ,two vertices being adjacent in C G if and only if they are not adjacent in G .） 如 注：（1） p C G +G = K （union）， G G V(G) C = （intersection）， ( ) ( ) = C E G E G ， ( ) =( ) = C G G ， 2 ( ) ( ) ( ) G G K C C + = = ；（2） = C K 个顶点的空图， m n C Km,n = K + K . （3） + ，- 用于图之间的运算， ， 用于集合之间的运算.（4）（对称性） G 与 C G 互为补图. 自补图（self-complementary graph）：a simple graph G is self-complementary if C G G
运筹学讲义 命题若G是自补图,则(1)c(G)=c(G)==;(2)v(G)=0,l(mod4) 证明:(1)由自补图,同构图的定义及补图的定义的注(1)易见 (2)由(1)得,(G)= (整数!) 但vv-1仅能其一为奇数,∴v≡0,l(mod4).■ 例2(比赛顺序的排定)有甲、乙、丙、丁、戊、己6名运动员报名参加A、B、C、D、E、F6 个项目的比赛各运动员的比赛项目见下表中√所示 A 甲 √ √ √√√ √ 问应如何安排六个项目的比赛顺序,以使得每个运动员都不连续参加两项比赛? 比:以顶点表示比赛项目,两个顶点之间有一条边相连当且仅当有同一名运动员参加对应的两个 项目,作图G A SOD AO D 由G的补图GC知,合乎要求的比赛顺序为A→C→B→F→E→D.■ 链,路,圈 WE (walk): a finite none-null sequence whose term are alternatively vertices and edges 。992 链 origin VR: interval vertices: V1,V2 the length (kR) of a walk: k= the number of edges of a walk
运 筹 学 讲 义 4 命题 若 G 是自补图，则（1） 2 ( ) ( ) 2 C G G C = = ；（2） (G) 0,1(mod 4) . 证明：（1）由自补图，同构图的定义及补图的定义的注（1）易见； （2）由（1）得， 4 ( 1) 2 ( ) 2 − = = C G （整数！）. 但 , −1 仅能其一为奇数， 0,1(mod 4) .▌ 例 2（比赛顺序的排定）有甲、乙、丙、丁、戊、己 6 名运动员报名参加 A、B、C、D、E、F 6 个项目的比赛.各运动员的比赛项目见下表中√所示. A B C D E F 甲 √ √ √ 乙 √ √ √ 丙 √ √ 丁 √ √ 戊 √ √ √ 己 √ √ √ 问应如何安排六个项目的比赛顺序，以使得每个运动员都不连续参加两项比赛？ 解：以顶点表示比赛项目，两个顶点之间有一条边相连当且仅当有同一名运动员参加对应的两个 比赛项目，作图 G . 由 G 的补图 C G 知，合乎要求的比赛顺序为 A→C → B → F → E → D.▌ 链，路，圈 链（walk）：a finite none-null sequence whose term are alternatively vertices and edges. origin： 0 v ；terminus： k v ；interval vertices： 1 v ， 2 v ，…， k−1 v . the length（长度） of a walk： k = the number of edges of a walk
运筹学讲义 a closed walk is a walk which has positive length and whose origin and terminus are the same. vE (trail): a walk whose edges are distinct i(path): a walk whose vertices are distinct (certainly, its edges are also distinct!) Obviously, a path is a trail 路的表示:a(u,v)path, where u, v are respectively the origin and terminus of a path G(GE)(cycle ) a closed trail whose origin(terminus) and interval vertices are distinct, i.e. a closed path. vs v2 vs v2 s 1 链2yy4迹v2yy42路5 圈1v23yy1 #esE: A loop is also a cycle; the length of cycle is the number of vertices (or edges) f a cycle (every cycle has the same number of vertices and edges ! length n C is a loop, c is multiedges According to the odevity (odd even of n, is divided into odd cycle (a)and even cycle(偶圈) Th1 a graph is bipartite if and only if it contains no odd cycle Proof
运 筹 学 讲 义 5 A closed walk is a walk which has positive length and whose origin and terminus are the same. 迹（trail）：a walk whose edges are distinct. 路（path）：a walk whose vertices are distinct（certainly，its edges are also distinct！）. Obviously，a path is a trail. 路的表示：a (u,v) -path，where u, v are respectively the origin and terminus of a path. 圈（回路）（cycle）：a closed trail whose origin（terminus） and interval vertices are distinct，i.e. a closed path. 规定：A loop is also a cycle；the length of cycle is the number of vertices（or edges） of a cycle（Every cycle has the same number of vertices and edges！）. n −圈（ n −cycle） Cn ：a cycle of length n . C1 is a loop，C2 is multiedges. According to the odevity （odd even） of n ，Cn is divided into odd cycle（奇圈） and even cycle（偶圈）. Th1 A graph is bipartite if and only if it contains no odd cycle. Proof: