定理3(可图化充要条件) 定理3非负整数列d=(d,d2,,d)是可图 化的,当且仅当d,+d2+,+dn=0md2 证明:(→)握手定理 (=)奇数度点两两之间连一边,剩余度用 环来实现.# 例2:(1)=543,3,2);(2d=(5,3,3,2,1) 《集合论与图论》第14讲 16
《集合论与图论》第14讲 16 定理3(可图化充要条件) 定理3:非负整数列d=(d1,d2,…,dn)是可图 化的, 当且仅当d1+d2+…+dn=0(mod 2). 证明: (⇒) 握手定理 (⇐) 奇数度点两两之间连一边, 剩余度用 环来实现. # 例2: (1)d=(5,4,4,3,3,2); (2)d=(5,3,3,2,1). 5 3 3 1 5 3 3 1
Hae定理(可简单图化充要条件) 定理5(V.Have,1955)设非负整数列 d=(d1d2…,d满足: d+d2+.+d=0mod2) n-1≥dd2≥.2dn20, d可简单图化当且仅当 d=(21,d31…,d+-1,d d1+2…yun 可简单图化 例:d=(4432,2),d=(3,2,2,1,2) 《集合论与图论》第14讲
《集合论与图论》第14讲 17 Havel定理(可简单图化充要条件) 定理5(V. Havel, 1955):设非负整数列 d=(d1,d2,…,dn)满足: d1+d2+…+dn=0(mod 2), n-1≥d1≥d2≥…≥dn≥0, 则d可简单图化当且仅当 d’=(d2-1,d3-1,…,dd1+1-1,dd1+2,…,dn) 可简单图化. 例: d=(4,4,3,3,2,2), d’=(3,2,2,1,2)
Hae定理(举例) 例4:判断下列非负整数列是否可简单图 化.(1)(5,54422)(244.3,2,2) 解:(1)(5544.22.、4.3311, (2,2,0,0),(1,10,不可简单图化 (2)(443322),(3,2,2,1,2),(32.2,2,1), (111110111可简单图化# 《集合论与图论》第14讲 8
《集合论与图论》第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), 可简单图化. #
Hae定理(证明示意) G d1+1Vd1+2 d=(d1,d2d3 G d1+1 41+11,ud1+2, 《集合论与图论》第14讲 19
《集合论与图论》第14讲 19 Havel定理(证明示意) v1 v2 v3 vd1+1 v v n d1+2 v2 v3 vd1+1 v v n d1+2 G’ G d = (d1, d2, d3, dd1+1, dd1+2, dn) d’ = (d2-1, d3-1, dd1+1-1,dd1+2, dn) …… …… …… ……
Hae定理(证明) 婚证明:(<)设 d=(21431…,d+-1,d61+2…,d) 可简单图化为G=<V,E>,其中 V=V2V3…, 则令G=<V,E>,V=VWv E=E∪{(W,V2),(W1V3),…,(1(+) 于是d可简单图化为G 《集合论与图论》第14讲
《集合论与图论》第14讲 20 Havel定理(证明) 证明: (⇐) 设 d’=(d2-1,d3-1,…,dd1+1-1, dd1+2, …, dn) 可简单图化为 G’=<V’,E’>, 其中 V’={v2,v3,…,vn}, 则令G=<V,E>, V=V’∪{v1}, E = E’ ∪ { (v1,v2), (v1,v3), …, (v1,vd1+1) }, 于是d可简单图化为G.