运筹学讲义 §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:
运筹学讲义 A人 二分图 非二分图1 注:当n为偶数时,Cn是二分图;当n为奇数时,Cn不是二分图 例3试在K,(v≥3)中,求:(1)任两顶点之间的路的条数;(2)圈的个数;(3)含有某条边的 圈的个数 此两顶点之间的路的条数为C2+C2+C2+…+C2=2心列为C,C1,C2 解:(1)∵任两顶点之间的长度为1,2,3,…,V-1的路的条数分别 +v+2 (2)C+C+…+C"=2-(C+C+C)=2 (3)C2+C2+…+CH=2=2"-2-CD2=22-1.■ 注:(1)可借助K5来分析.(2)K,(v≥3)中任两顶点之间的路的长度的最小,大值分别为 1,v-1,圈的长度最小,大值分别为3,v 例4求证:若G是简单图,且O≥k,则G中必存在长度为k的路
运 筹 学 讲 义 6 ▌ 注：当 n 为偶数时， Cn 是二分图；当 n 为奇数时， Cn 不是二分图. 例 3 试在 ( 3) K 中，求：（1）任两顶点之间的路的条数；（2）圈的个数；（3）含有某条边的 圈的个数. 解：（1） 任两顶点之间的长度为 1，2，3，…， −1 的路的条数分别为 2 2 2 2 1 2 0 2 , , , , − − − − − C C C C ， 此两顶点之间的路的条数为 2 2 2 2 2 1 2 0 2 2 − − − + − + − + + − = C C C C . （2） 2 2 2 ( ) 2 2 3 4 0 1 2 + + + + + = − + + = − C C C C C C . （3） 2 2 1 0 2 2 2 2 2 2 2 1 2 + + + = − = − − − − − − − − C C C C .▌ 注：（1）可借助 K5 来分析.（2） ( 3) K 中任两顶点之间的路的长度的最小，大值分别为 1, −1 ，圈的长度最小，大值分别为 3, . 例 4 求证：若 G 是简单图，且 k ，则 G 中必存在长度为 k 的路
运筹学讲义 证明:(反证法)假设P=v"2v3…VV是G中的一条最长路,且l1≤ll≥1.于是,彐vo∈,v≠V,i=1,2,…,l,l+1,使v得v1与相邻 令Q=0V12V3…Vn,则Q也是G中的一条路,且其长度为l+1>1,这与假设矛盾.■ 例5(1)求证:若(G)=2,则图G中必含有圈 (2)求证:若G是简单图,且δ≥2,则G中必含有长度不小于为δ+1的圈 (3)若E≥v,则图G中含有圈 证明:(1)Vv1∈V,则d(v1)≥=2,∴彐v2∈ 使得v与V,相连;同理,彐v3∈V,使得v2与V3相 连;…彐vk∈V,使得v-与vk相连但由G是有 限图知,P<+∞,V必与v1,V2,…,V=中的某 个相连不妨设vk与v2相连,则v2v3…-"2即 为G的一个圈 (2)由(1)知,G中含有圈 设G中的最长路为P=vv1v2v3…vk,显然v0的所有 邻接顶点都在P上(否则,若彐v∈V,v与v邻接 但vgP,则vvvV2v3…Vk仍为一条路,且其长度为 k+1,这与P是最长路矛盾).令v为v0的所有邻接顶 点中下标最大者,显然l=d(v)≥δ.令 C=vovv2v3…vV,则C是一个圈,且其长度 ≥l+1≥+1.l
运 筹 学 讲 义 7 证 明 ：（ 反 证 法 ） 假 设 = 1 2 3 l l+1 P v v v v v 是 G 中 的 一 条 最 长 路 ， 且 1 l k ， 则 d(v1 ) k l 1.于是， v0 V ，v0 vi ,i =1,2, ,l,l +1 ，使 0 v 得 1 v 与相邻. 令 = 0 1 2 3 l l+1 Q v v v v v v ，则 Q 也是 G 中的一条路，且其长度为 l +1 l ，这与假设矛盾.▍ 例 5（1）求证：若 (G) = 2 ，则图 G 中必含有圈． （2）求证：若 G 是简单图，且 2 ，则 G 中必含有长度不小于为 +1 的圈. （3）若 ，则图 G 中含有圈． 证明：（1） v1 V ,则 d(v1 ) = 2 ， v2 V ， 使得 1 v 与 2 v 相连；同理， v3 V ，使得 2 v 与 3 v 相 连；…； vk V ，使得 k−1 v 与 k v 相连.但由 G 是有 限图知， p + ， k v 必与 1 2 1 , , , k− v v v 中的某一 个相连.不妨设 k v 与 2 v 相连，则 2 3 1 2 v v v v v k− k 即 为 G 的一个圈. （2）由（1）知， G 中含有圈. 设 G 中的最长路为 k P v v v v v = 0 1 2 3 ，显然 0 v 的所有 邻接顶点都在 P 上(否则，若 v V ，v 与 0 v 邻接， 但 v P ，则 k vv v v v v 0 1 2 3 仍为一条路，且其长度为 k +1 ，这与 P 是最长路矛盾).令 l v 为 0 v 的所有邻接顶 点 中 下 标 最 大 者 ， 显 然 l = d(v0 ) . 令 0 1 2 3 0 C v v v v v v = l ， 则 C 是 一 个 圈 ，且 其 长 度 l +1 +1.▍
运筹学讲义 (3)若G含有环或重边,则G中含有圈;否则,则G为简单图 若δ(G)=2,则由(1)知,G中含有圈;否则,则从G中去掉所有度为1的顶点(悬 挂点),设得图G1·若(G1)=2,则由(1)知,G1中含有圈:否则,则从G1中去掉悬 挂点,设得图G2 显然,当V=1或2时,G不满足E≥v,故上述过程进行到某一个图G时即可终止 显然,(Gm)=2,故由(1)知,Gm中含有圈,当然G中也含有圈 另证:(反证法)假设G中不含有圈,则G是森林.∴E=-≤ψ-1<ν,矛盾.L 注:(1)(1)的逆否命题:若有限图G中不含有圈,则G的顶点或是孤立点,或是悬挂点 等价命题”:若δ(G)≥2,则有限图G中至少含有一个圈 (2)(3)的逆否命题:若图G中不含有圈,则E≤v 例6求证:(1)若C1,C2是图G的两个圈,则C△C2是G的若干不相交的圈的并 (2)若C1,C2是图G的两个圈,则ye∈E,(C1+C2)-e含有G的一个圈 证明:(1)分C1∩C2=①和C1∩C2≠Φ讨论 (2)分e∈C1∩C2和e∈C1∩C2讨论
运 筹 学 讲 义 8 （3）若 G 含有环或重边，则 G 中含有圈；否则，则 G 为简单图. 若 (G) = 2 ，则由（1）知， G 中含有圈；否则，则从 G 中去掉所有度为 1 的顶点（悬 挂点），设得图 G1 .若 (G1 ) = 2 ，则由（1）知， G1 中含有圈；否则，则从 G1 中去掉悬 挂点，设得图 G2 . 显然，当 =1 或 2 时， G 不满足 ，故上述过程进行到某一个图 Gm 时即可终止. 显然， (Gm ) = 2 ，故由（1）知， Gm 中含有圈，当然 G 中也含有圈. 另证：（反证法）假设 G 中不含有圈，则 G 是森林. = − − 1 1 ，矛盾.▍ 注：（1）（1）的逆否命题：若有限图 G 中不含有圈，则 G 的顶点或是孤立点，或是悬挂点． “等价命题”：若 (G) 2 ，则有限图 G 中至少含有一个圈． （2）（3）的逆否命题：若图 G 中不含有圈，则 −1. 例 6 求证：（1）若 1 2 C ,C 是图 G 的两个圈，则 C1C2 是 G 的若干不相交的圈的并． （2）若 1 2 C ,C 是图 G 的两个圈，则 e E ，(C +C ) − e 1 2 含有 G 的一个圈. 证明：（1）分 C1 C2 = 和 C1 C2 讨论. （2）分 C1 C2 e 和 C1 C2 e 讨论
运筹学讲义 注:对称差( symmetric difference):A△AB=(A∪B)\(A∩B) 连通图 顶点u,v连通:u, v are connected if there exists a(u,v) path in a graph 顶点u,v不连通: otherwise 注:显然,顶点的连通性是一种等价关系,具有反身性,对称性和传递性 连通图( a connected graph): a graph any two vertices of which are connected 非连通图( a disconnected graph): otherwise. 连通分支( connected component): connected components of a graph Obviously, a connected component is a maximal connected subgraph of a graph 应当指出,极大( maximal)不同于最大( maxImum).最大连通子图指含有顶点数和边数最多的 连通子图;极大连通子图指本身是连通子图,如再增加顶点或边,就不再连通的子图.由此,图的任 连通分支都是极大连通子图,但只有其中顶点数和边数最多的才是最大连通子图 连通分支数:O(G)= the number of all connected components of a graph G Evidently, a graph G is connected分o(G)=1; g is disconnected分(G)≥2 连通图 非连通图 命题ve∈E(G),有)(G)≤O(G-e)≤o(G)+1 证明:由O的定义,显然有c(G)≤O(G-e) 又去掉一条边e至多将G的一个连通分支分割为两个连通分支,故o(G-e)≤o(G)+1.l 注:此命题对去点未必成立,即去点比去边对图的连通性的破坏性小. 例7求证:若图G中恰含有两个奇顶点,则它们必连通 证明:设图G的两个奇顶点为u,v,若G为连通图,则由连通图的定义知,u,v必连通 否则,u,v必存在于G的同一个连通分支中(∵任一图的奇顶点的个数必为偶数:而连通分支本 身也是图,且是连通图!),当然也连通l
运 筹 学 讲 义 9 ▍ 注：对称差（symmetric difference）： AB = (A B) \ (A B) . 连通图 顶点 u, v 连通： u, v are connected if there exists a (u,v) -path in a graph； 顶点 u, v 不连通：otherwise. 注：显然，顶点的连通性是一种等价关系，具有反身性，对称性和传递性. 连通图（a connected graph）：a graph any two vertices of which are connected； 非连通图（a disconnected graph）：otherwise. 连通分支（connected component）：connected components of a graph. Obviously，a connected component is a maximal connected subgraph of a graph. 应当指出，极大（maximal）不同于最大（maximum）.最大连通子图指含有顶点数和边数最多的 连通子图；极大连通子图指本身是连通子图，如再增加顶点或边，就不再连通的子图.由此，图的任 一连通分支都是极大连通子图，但只有其中顶点数和边数最多的才是最大连通子图. 连通分支数： (G) = the number of all connected components of a graph G . Evidently, a graph G is connected (G) = 1 ； G is disconnected (G) 2 . 命题 e E(G) ，有 (G) (G − e) (G) +1 . 证明：由 的定义，显然有 (G) (G − e) ； 又去掉一条边 e 至多将 G 的一个连通分支分割为两个连通分支，故 (G − e) (G) +1.▍ 注：此命题对去点未必成立，即去点比去边对图的连通性的破坏性小. 例 7 求证：若图 G 中恰含有两个奇顶点，则它们必连通． 证明：设图 G 的两个奇顶点为 u, v ，若 G 为连通图，则由连通图的定义知， u, v 必连通； 否则， u, v 必存在于 G 的同一个连通分支中（ 任一图的奇顶点的个数必为偶数；而连通分支本 身也是图，且是连通图!），当然也连通.▍
运筹学讲义 例8(1)求证:若G是简单图,且E>C2,则G必为连通图 (2)找一个顶点数为v的不连通的简单图G,使得E=C21,其中v≥2 (3)找一个顶点数为v,且含有的边数最多的不连通图 证明:(1)(反证法)假设G不连通,O(G)=≥2,G的所有连通分支为G1G2,…,G。,则 G)21=12,…m,∑vG)=v由此,v(G)≤v-1i=12,…,0.于是, E(G)=∑e(G)≤∑(Km)=∑Cc,= ∑ Gv(G)-sy(-(G)-1) (v(G1)-1) (-1 QV(G)-O)= 2(v-1) 2)=C 矛盾 (2)∵E(K,-1)=C 令G=K+K1即可 (3)令G=K,1+K1即可l 例9(1)求证:若G是简单图,且δ>-1,则G必为连通图 (2)找一个不连通的简单图G,使得G是(=-1)-正则的,其中v为偶数,且v≥2 证明:(1)(反证法)假设G不连通,W.L.0.G.设O(G)=2,G的两个连通分支分别为G1,G2 且(G)=v1,(G2)=2,则必有5或"25不妨设v5|,又G是简单图,则 vEG),有d()s2|-1,这与6>-1矛盾 (2)令G=K,+K,即可l 22 注:[x表示不超过x的最大整数 例10(1)求证:若G是不连通图,则GC为连通图 证明:为证G为连通图,只需证明:Vu,v∈I(G),u,y在G中连通分两种情况讨论
运 筹 学 讲 义 10 例 8（1）求证：若 G 是简单图，且 2 −1 C ，则 G 必为连通图. （2）找一个顶点数为 的不连通的简单图 G ，使得 2 = −1 C ，其中 2 . （3）找一个顶点数为 ，且含有的边数最多的不连通图. 证明：（1）（反证法）假设 G 不连通， (G) = 2 ，G 的所有连通分支为 G G G , , , 1 2 ，则 (Gi ) 1,i =1,2, , ， = =1 ( ) i Gi .由此， (Gi ) −1,i =1,2, , .于是， ( 2) , 2 ( 1) ( ) 2 ( 1) ( ( ) ) 2 ( 1) ( ( ) 1) 2 ( 1) 2 ( 1)( ( ) 1) 2 ( )( ( ) 1) ( ) ( ) ( ) 2 1 2 1 1 1 1 1 2 ( ) 1 ( ) 1 − = = = = = = = − = − − − − = − − = − = − − − = = = G G C G G G G G K C i i i i i i i i i i G i G i i i i 矛盾. （2） 2 1 1 ( ) − = − K C ， 令 G = K −1 + K1 即可. （3）令 G = K −1 + K1 即可.▍ 例 9（1）求证：若 G 是简单图，且 1 2 − ，则 G 必为连通图. （2）找一个不连通的简单图 G ，使得 G 是 −1) − 2 ( 正则的，其中 为偶数，且 2 . 证明：（1）（反证法）假设 G 不连通，W.L.O.G.设 (G) = 2 ，G 的两个连通分支分别为 1 2 G ,G ， 且 1 1 2 2 (G ) = ,(G ) = ，则必有 2 1 或 2 2 .不妨设 2 1 ，又 G 是简单图，则 ( ) V G1 v ，有 1 2 ( ) − d v ，这与 1 2 − 矛盾. （2）令 2 2 G = K + K 即可.▍ 注： [x] 表示不超过 x 的最大整数. 例 10（1）求证：若 G 是不连通图，则 C G 为连通图. 证明：为证 C G 为连通图，只需证明： , ( ) C u v V G ，u, v 在 C G 中连通.分两种情况讨论：