《集合论与图论》第14讲1 第14讲图的基本概念 ?1.预备知识,无向图,有向图,相邻,关联 ?2.度,握手定理,度数列,可(简单)图化 ?3.图同构 ?4.图族 《集合论与图论》第14讲2 图论参考书 ?Graph Theory, R.Diestel,Springer,1997, (O157.5/D566) (有只读电子版) ?现代图论(影印版),科学出版社-Springer, 2001, (O157.5/B638m/2001) ?离散数学及其应用, 机械工业出版社, 2002, 2004 《集合论与图论》第14讲3 预备知识 ?有序积: A×B={ <x,y> |x∈A∧y∈B} 有序对: <x,y>≠<y,x> ?无序积: A&B={ (x,y) |x∈A∧y∈B} 无序对: (x,y)=(y,x) ?多重集: {a,a,a,b,b,c}≠{a,b,c} 重复度: a的重复度为3, b的为2, c的为1 《集合论与图论》第14讲4 无向图(undirected graph) ?无向图(graph): G=<V,E>, (1) V≠?, 顶点,结点(vertex / node) (2) 多重集E?V&V, 边(edge / link) ?例: G=<V,E>,V={a,b,c,d,e}, E={(a,a),(a,b),(a,b),(b,c),(c,d),(b,d)}. a b c d e u v (u,v) 《集合论与图论》第14讲5 有向图(directed graph) ?有向图(digraph): D=<V,E>, (1) V≠?, 顶点,结点(vertex / node) (2) 多重集E?V×V, 边(edge / link / arc) ?例: D=<V,E>,V={a,b,c,d,e}, E={ <a,a>, <a,b>,<a,b>,<b,a>,<b,c>,<c,d>,(d,b) }. a b c d e u(起点) v(终点) <u,v> 《集合论与图论》第14讲6 n阶图,零图,平凡图,空图 ?若G=<V,E>, 则V(G)=V, E(G)=E ?若D=<V,E>, 则V(D)=V, E(D)=E ?n阶图(order-n graph): |V(G)|=n ?有限图(finite graph): |V(G)|<∞ ?零图(null graph): E=?, N n ?平凡图(trival graph): 1阶零图, N 1 ?空图(empty graph): V=E=?, ? 《集合论与图论》第14讲7 标定图,非标定图,基图 ?标定图(labeled graph): 顶点或边带标记 ?非标定图(unlabeled graph): 顶点或边不 带标记 ?基图(底图): 有向图去掉边的方向后得到 的无向图 a bc d 《集合论与图论》第14讲8 相邻(adjacent),关联(incident) ?相邻(邻接)(adjacent): 点与点,边与边 ?邻接到,邻接于: u邻接到v, v邻接于u ?关联(incident):点与边 ?关联次数: ?环(loop):只与一个顶点关联的边 ?孤立点(isolated vertex): ?平行边(parallel edge): ? 21+1-11 uv 《集合论与图论》第14讲9 邻域(neighborhood) ?邻域: N G (v)={u|u∈V(G)∧(u,v)∈E(G)∧u≠v} ?闭(closed)邻域: ?关联集: I G (v) = { e | e与v关联} ?后继:Γ D + (v)={u|u∈V(D)∧<v,u>∈E(D)∧u≠v} ?前驱:Γ D - (v)={u|u∈V(D)∧<u,v>∈E(D)∧u≠v} ?邻域: N G (v)=Γ D + (v)∪Γ D - (v) ?闭邻域: {v}(v)N(v)N GG ∪= }{)()( vvNvN DD ∪= 《集合论与图论》第14讲10 顶点的度数(degree/valence) ?度d G (v): 与v关联的边的次数之和 ?出度d D + (v): 与v关联的出边的次数之和 ?入度d D - (v): 与v关联的入边的次数之和 ?度d D (v) = d D + (v) + d D - (v) 0 3 3 4 0,0 1,2 (d + ,d - ) 2,1 2,2 《集合论与图论》第14讲11 最大(出/入)度,最小(出/入)度 ?最大度: Δ(G) = max{ d G (v) | v∈V(G) } ?最小度: δ(G) = min{ d G (v) | v∈V(G) } ?最大出度: Δ + (D) = max{ d D + (v) | v∈V(D) } ?最小出度: δ + (D) = min{ d D + (v) | v∈V(D) } ?最大入度: Δ - (D) = max{ d D - (v) | v∈V(D) } ?最小入度: δ - (D) = min{ d D - (v) | v∈V(D) } ?简记为Δ, δ, Δ + , δ + , Δ - , δ - 《集合论与图论》第14讲12 握手定理(图论基本定理) ?定理1:设G=<V,E>是无向图, V={v 1 ,v 2 ,…,v n }, |E|=m, 则 d(v 1 )+d(v 2 )+…+d(v n )=2m. # ?定理2:设D=<V,E>是有向图, V={v 1 ,v 2 ,…,v n }, |E|=m, 则 d + (v 1 )+d + (v 2 )+…+d + (v n ) = d - (v 1 )+d - (v 2 ) +…+d - (v n ) = m. # ?推论:任何图中,奇数度顶点的个数是偶数. # 《集合论与图论》第14讲13 简单图(simple graph),正则图 ?简单图(simple graph): 无环,无平行边 ?若G是简单图, 则0 ≤Δ(G) ≤ n-1 ?k-正则图(regular graph): ?v, d(v)≡k 《集合论与图论》第14讲14 度数列 ?度数列: 设G=<V,E>,V={v 1 ,v 2 ,…,v n }, 称 d = ( d(v 1 ),d(v 2 ),…, d(v n ) ) 为G的度数列 ?例: d = ( 5, 1, 2, 3, 3 ) v 2 v 3 v 4 v 5 v 1 《集合论与图论》第14讲15 可图化,可简单图化 ?可图化:设非负整数列d=( d 1 ,d 2 , …, d n ), 若存在图G, 使得G的度数列是d, 则称d 为可图化的 ?可简单图化:设非负整数列d=( d 1 , d 2 , …, d n ), 若存在简单图G, 使得G的度数列是d, 则称d为可简单图化的 ?例: d = ( 5, 3, 3, 2, 1 ) 《集合论与图论》第14讲16 定理3(可图化充要条件) ?定理3:非负整数列d=(d 1 ,d 2 ,…,d n )是可图 化的, 当且仅当d 1 +d 2 +…+d n =0(mod 2). ?证明: (?) 握手定理 (?) 奇数度点两两之间连一边, 剩余度用 环来实现. # ?例2: (1)d=(5,4,4,3,3,2); (2)d=(5,3,3,2,1). 53 31 53 31 《集合论与图论》第14讲17 Havel定理(可简单图化充要条件) ?定理5(V. Havel, 1955):设非负整数列 d=(d 1 ,d 2 ,…,d n )满足: d 1 +d 2 +…+d n =0(mod 2), n-1≥d 1 ≥d 2 ≥…≥d n ≥0, 则d可简单图化当且仅当 d’=(d 2 -1,d 3 -1,…,d d1+1 -1,d d1+2 ,…,d n ) 可简单图化. ?例: d=(4,4,3,3,2,2), d’=(3,2,2,1,2) 《集合论与图论》第14讲18 Havel定理(举例) ?例4: 判断下列非负整数列是否可简单图 化. (1) (5,5,4,4,2,2) (2)(4,4,3,3,2,2) ?解: (1) (5,5,4,4,2,2), (4,3,3,1,1), (2,2,0,0), (1,-1,0), 不可简单图化. (2) (4,4,3,3,2,2), (3,2,2,1,2), (3,2,2,2,1), (1,1,1,1), (0,1,1), (1,1), 可简单图化. # 《集合论与图论》第14讲19 Havel定理(证明示意) v 1 v 2 v 3 v d1+1 v nv d1+2 v 2 v 3 v d1+1 v nv d1+2 G’ G d = (d 1 ,d 2 ,d 3 ,d d1+1 ,d d1+2 ,d n ) d’ = (d 2 -1, d 3 -1, d d1+1 -1,d d1+2 ,d n ) …… …… …… …… 《集合论与图论》第14讲20 Havel定理(证明) ?证明: (?) 设 d’=(d 2 -1,d 3 -1,…,d d1+1 -1, d d1+2 , …, d n ) 可简单图化为G’=<V’,E’>, 其中 V’={v 2 ,v 3 ,…,v n }, 则令G=<V,E>, V=V’∪{v 1 }, E = E’ ∪ { (v 1 ,v 2 ), (v 1 ,v 3 ), …, (v 1 ,v d1+1 ) }, 于是d可简单图化为G. 《集合论与图论》第14讲21 Havel定理(证明,续) ?证明: (?) 设d可简单图化为G=<V,E>, 其 中V={v 1 ,v 2 ,…,v n }, d(v 1 )≥d(v 2 )≥…≥d(v n ). (1) 若N G (v 1 )={v 2 ,v 3 , …,v d1+1 }, 则令 G’=<V’,E’>, V’=V-{v 1 }, E’=E-{ (v 1 ,v 2 ), (v 1 ,v 3 ), …, (v 1 ,v d1+1 ) }, 于是d’可简单图化为G’. (2) 若?i?j( i<j ∧ v i ?N G (v 1 ) ∧ v j ∈N G (v 1 ) ), 《集合论与图论》第14讲22 Havel定理(证明示意) v 1 v 2 v i v d1+1 v nv k G d = (d 1 ,d 2 ,d 3 ,d d1+1 ,d d1+2 ,d n ) …… …… v j v 1 v 2 v i v d1+1 v nv k G 1 d = (d 1 ,d 2 ,d 3 ,d d1+1 ,d d1+2 ,d n ) …… …… v j v 1 ?N G (v i )∧v 1 ∈N G (v j )∧d i ≥d j ??v k (v k ∈N G (v i )∧v k ?N G (v j ) 《集合论与图论》第14讲23 Havel定理(证明,续) ?证明: (?) (2)若?i?j(1≤i<j≤n∧v i ?N G (v 1 )∧v j ∈N G (v 1 )), 则由d i ≥d j 可得 ?k(1≤k≤n∧v k ?N G (v j )∧v k ∈N G (v i )), 令G 1 =<V,E∪{(v 1 ,v i ),(v k ,v j )}-{(v 1 ,v j ),(v k ,v i )}>, 则G 1 与G的度数列都还是d,重复这个步骤, 直到化为(1)中情形为止. # 《集合论与图论》第14讲24 Havel定理(证明中包含的思想) ?构造性证明: 给出具体构造方法 ?先处理“简单,好的”情形, 再把“复杂,坏的”情形化为前者来处理 《集合论与图论》第14讲25 定理4 (可简单图化充要条件) ?定理4(P.Erd?s,T.Gallai,1960):设非负整 数列d=(d 1 ,d 2 ,…,d n )满足: n-1≥d 1 ≥d 2 ≥…≥d n ≥0, 则d可简单图化当且仅当 d 1 +d 2 +…+d n =0(mod 2) 并且对r=1,2,…,n-1有 d 1 +d 2 +…+d r ≤ r(r-1)+min{r,d r+1 }+ min{r,d r+2 }+…+min{r,d n }. # 《集合论与图论》第14讲26 定理4’(等价形式) ?定理4’(P.Erd?s,T.Gallai,1960):非负整数 列d=(d 1 ,d 2 ,…,d n )可简单图化当且仅当 d 1 +d 2 +…+d n =0(mod 2) 并且对r=1,2,…,n有 d 1 +d 2 +…+d r ≤ r(r-1)+min{r,d r+1 }+ min{r,d r+2 }+…+min{r,d n }. # ?说明: n-1≥d 1 ≥d 2 ≥…≥d n ≥0 ? d 1 +d 2 +…+d n ≤ n(n-1). 《集合论与图论》第14讲27 定理4(举例) ?例3: 判断下列非负整数列是否可简单图 化. (1) (5,4,3,2,2,1) (2)(5,4,4,3,2) (3) (3,3,3,1) (4)(6,6,5,4,3,3,1) (5) (5,5,3,3,2,2,2) (6) (d 1 ,d 2 ,…,d n ), d 1 >d 2 >…>d n ≥1, ?解: (1) 5+4+3+2+2+1=17≠0(mod 2). 不可(简单)图化. 《集合论与图论》第14讲28 定理4(举例) ?例3: 判断下列非负整数列是否可简单图 化. (2)(5,4,4,3,2) ?解: (2) 5+4+4+3+2=18=0(mod 2). 但是d 1 =5>n-1=4,不满足n-1≥d 1 , 不可简 单图化. ( 或者: 但是r=1时, d 1 =5>1(1-1)+min{1,4} +min{1,4}+min{1,3} +min{1,2}=4, 不可简 单图化.) 《集合论与图论》第14讲29 定理4(举例) ?例3: 判断下列非负整数列是否可简单图 化. (3) (3,3,3,1) ?解: (3) 3+3+3+1=10=0(mod 2). d 1 =3=n-1,满足n-1≥d 1 , 但是r=2时, d 1 +d 2 =6>2(2-1)+min{2,3}+min{2,1}=5, 不可简单图化. 《集合论与图论》第14讲30 定理4(举例) ?例3: 判断下列非负整数列是否可简单图 化. (4)(6,6,5,4,3,3,1) ?解: (4) 6+6+5+4+3+3+1=28=0(mod 2). d 1 =6=n-1,满足n-1≥d 1 . r=1,2时, d 1 =6≤1(1-1)+min{1,6}+min{1,5}+ …=6, d 1 +d 2 =12>2(2-1)+min{2,5}+…=11, 不可简单图化. ?或:6,6,*,*,*,*,1不可简单图化 《集合论与图论》第14讲31 定理4(举例) ?例3: (5) (5,5,3,3,2,2,2) ?解: (5) 5+5+3+3+2+2+2=22=0(mod 2). d 1 =5<n-1,满足n-1≥d 1 . r=1,2,…,7时, d 1 =5<1(1-1)+min{1,5}+min{1,5}+ …=6, d 1 +d 2 =10<2(2-1)+min{2,3}+…=12, d 1 +d 2 +d 3 =13<3(3-1)+min{3,3}+…=15, d 1 +d 2 +d 3 +d 4 =16<4(4-1)+min{4,2}+…=18, 《集合论与图论》第14讲32 定理4(举例) ?例3: (5) (5,5,3,3,2,2,2) ?解: (5) d 1 +d 2 +d 3 +d 4 =16<4(4-1)+min{4,2}+…=18, d 1 +d 2 +…+d 5 =18<5(5-1)+min{5,2}+…=24, d 1 +d 2 +…+d 6 =20<6(6-1)+min{6,2}=32, d 1 +d 2 +…+d 7 =22<7(7-1)=42, 可简单图化. 《集合论与图论》第14讲33 定理4(举例) ?例3: (5) (5,5,3,3,2,2,2) ?解: (5)可简单图化. (5,5,3,3,2,2,2), (4,2,2,1,1,2), (4,2,2,2,1,1), (1,1,1,0,1),(1,1,1,1), (0,1,1),(1,1) 《集合论与图论》第14讲34 定理4(举例) ?例3: 判断下列非负整数列是否可简单图 化. (6) (d 1 ,d 2 ,…,d n ), d 1 >d 2 >…>d n ≥1, ?解: (6) d 1 >d 2 >…>d n ≥1, d n-1 ≥2, d n-2 ≥3,…, d 1 ≥n,不满足n-1≥d 1 , 不可简单图化. # 《集合论与图论》第14讲35 Paul Erd?s(1913-1996) ?保罗?爱尔特希, 匈牙利人 ?廿世纪数学界的传奇人物 ?“Another roof, another proof.” 《集合论与图论》第14讲36 Paul Erd?s(1913-1996) “My mother said, ‘Even you, Paul, can be in only one place at one time.’ Maybe soon I will be relieved of this disadvantage. Maybe, once I've left, I'll be able to be in many places at the same time. Maybe then I'll be able to collaborate with Archimedes and Euclid.” 《集合论与图论》第14讲37 图同构(graph isomorphism) ?图同构: 设(有向)图G 1 =<V 1 ,E 1 >, G 2 =<V 2 ,E 2 >, 若存在双射f:V 1 →V 2 , 满足 ?u∈V 1 ,?v∈V 1 , (u,v)∈E 1 ? (f(u),f(v))∈E 2 ( <u,v>∈E 1 ? <f(u),f(v)>∈E 2 ) 则称G 1 与G 2 同构, 记作G 1 ?G 2 ?说明: 同构的图,其图论性质完全一样 ?算法：NAUTY 《集合论与图论》第14讲38 图同构(举例) G 1 G 2 G 3 G 1 ?G 3 , G 1 ?G 2 《集合论与图论》第14讲39 图同构(举例) G 1 G 2 G 3 G 1 ?G 3 , G 1 ?G 2 《集合论与图论》第14讲40 图同构(举例) G 1 G 2 G 3 G 1 ?G 2 ?G 3 《集合论与图论》第14讲41 图同构(举例) D 1 D 2 D 3 D 1 ?D 2 , D 2 ?D 3 《集合论与图论》第14讲42 图族(graph class) ?花束,两极 ?完全图,有向完全图,竞赛图 ?正则图,柏拉图图,彼德森图,库拉图斯基 图 ?r部图,二部图(偶图),完全r部图 ?路径,圈,轮,超立方体 ?树 《集合论与图论》第14讲43 花束(bouquets) B 1 B 2 B 3 B 4 B 5 《集合论与图论》第14讲44 两极(dipoles) D 1 D 2 D 3 D 4 D 5 《集合论与图论》第14讲45 完全图(complete graphs) K 1 K 2 K 3 K 4 K 5 《集合论与图论》第14讲46 有向完全图 《集合论与图论》第14讲47 竞赛图(tournament) 《集合论与图论》第14讲48 正则图(regular graph) ?r正则图: ?v∈V, d(v)=r, r=0,1,2,… ?例: K n 是n-1正则图(n=1,2,3,…) 《集合论与图论》第14讲49 柏拉图图(Platonic graphs) 正四面体图正六面体图 正八面体图 正十二面体图正二十面体图 《集合论与图论》第14讲50 彼德森图(Pertersen graph) 《集合论与图论》第14讲51 库拉图斯基图(Kuratowski graph) K 3,3 K 5 《集合论与图论》第14讲52 r部图(r-partite graphs) ?r部图: G=<V,E>,V=V 1 ∪V 2 ∪…∪V r , V i ∩V j =? (i≠j), E?U(V i &V j ), i≠j ?也记作G=<V 1 ,V 2 ,…,V r ; E>. 《集合论与图论》第14讲53 二部图(偶图)(bipartite graphs) ?二部图: G=<V 1 ,V 2 ; E>, 也称为偶图 《集合论与图论》第14讲54 完全r部图(complete r-partite graphs) K 3,3 K 2,3 K r,s K 1,1,1 K 1,1,2 K 1,2,2 K 1,2,3 r个 s个 《集合论与图论》第14讲55 路径(paths) P 1 P 2 P 3 P 4 P 5 《集合论与图论》第14讲56 圈(cycles) C 1 C 2 C 3 C 4 C 5 《集合论与图论》第14讲57 轮(wheels) W 1 W 2 W 3 W 4 W 5 《集合论与图论》第14讲58 超立方体(hypercubes) Q 0 Q 1 Q 2 Q 3 Q 4 《集合论与图论》第14讲59 树(trees) ?树: 连通无回图 《集合论与图论》第14讲60 总结 ?预备知识,无向图,有向图,相邻,关联 ?度,握手定理,度数列,可(简单)图化 ?图同构 ?图族 《集合论与图论》第14讲61 作业(#10) ?p213, 习题七, 1,2,3,4,5,7