《组合数学课件第三章容斥原理和鸽巢原理》课件.pptVIP

§３.8　鸽巢原理之二 设　B＝｛b1 , ··· , b16}，B [ 1 , 65 ]。 由反证法假设B∩P1 = ф。因而 B ( P2∪ P3∪ P4 )。 因为 ＝6，不妨设{b1 , ··· , b6} P2 ， 令Ci－1=bi－b1，I = 2， ···，6 设C＝{ C1 , ··· , C5 }，C [ 1 , 65 ] 由反证法假设C∩( P1∪P2 ) =ф，故有 C (P3∪P4 ) 因为 ＝3，不妨设{C1 , C2 , C3 } P3 16 3 5 2 §３.8　鸽巢原理之二 令　di－1= Ci－C1，I = 2 , 3 设　D＝{ d1 , d2 } , D [ 1 , 65]。 由反证法假设 D∩( P1∪P2∪P3 )=ф，因而 　D P4　。 由反证法假设 d2－d1∈ P1∪P2∪P3 且d2－d1∈ P4 ， 故 d2－d1 ∈ [ 1 , 65 ]，但显然 d2－d1 ∈ [ 1 , 65 ]， 矛盾。 §３.9　Ramsey 问题 １．Ramsey问题 Ramsey问题可以看成是鸽巢原理的推 广．下面举例说明Ramsey问题． 例　6 个人中至少存在３人相互认识或者 相互不认识． 证　这个问题与K6的边２着色存在同色三 角形等价．假定用红蓝着色． §３.9　Ramsey 问题 设K6的顶点集为{v1 , v2 , ··· , v6 }，dr(v)表 示与顶点 v 关联的红色边的条数，db(v)表 示与 v 关联的蓝色边的条数．在K6 中，有 dr(v)＋ db(v)＝５，由鸽巢原理可知，至少 有３条边同色． 　　现将证明过程用判断树表示如下： §３.9　Ramsey 问题 dr(v1)≥3? db(v1)≥3 设(v1v2) (v1v3) (v1v4)为红边 设(v1v2) (v1v3) (v1v4)为蓝边 △v2v3v4是红△ ? △v2v3v4是蓝△ ? 设( v2v3 )是蓝边 设( v2v3 )是红边 △v1v2v3是蓝△ △v1v2v3是红△ √ √ Y N N N Y Y §３.9　Ramsey 问题 ２．若干推论 ( a )　K6的边用红蓝任意着色，则至少有 两个同色的三角形． 证　由前定理知，有同色三角形，不妨设 △v1v2v3是红色三角形 可由如下判断树证明． §３.9　Ramsey 问题 △v1v4v5是蓝△ 设 (v4v5)为蓝边 △v4v5v6是红△? 设(v1v4) (v1v5) (v1v6)为蓝边 db(v1)≥3 dr(v1)≥3? 设 (v1v4)为红边 (v4v2) (v4v3) 为蓝边? 设 (v4v2)为红边 db(v4)≥3? △v1v2v4是红△ dr(v4)≥3 设 (v4v5)为蓝边 (v4v5) (v4v6) 为红边 △v2v3v5是红△? 设 (v2v5)为蓝边 △v2v4v5是蓝△ △v4v5v6是红△ △v1v5v6是蓝△? 设 (v5v6)为红边 √ √ √ y y y y y y n n n n n §３.9　Ramsey 问题 ( b )　K9 的边红蓝两色任意着色，则必 有红K4或蓝色三角形(蓝K4或红色三角形)． 证　设９个顶点为 v1 , v2 , ··· , v9．对９个 顶点的完全图的边的红、蓝２着色图中， 必然存在 vi ，使得 dr(vi)≠3 ．否则， 红边数＝　∑ dr(vi)＝ ，这是不可能的． 不妨设 dr(v1)≠3，可得如下判断树证明结 论． 1 2 27 2 §３.9　Ramsey 问题 dr(v1)≥4? db(v1)≥6 设(v1v2) (v1v3) (v1v4)(v1v5)是4红边 设(v1v2) ··· (v1v7)是6条蓝边 K4(v2v3v4v5)是蓝K4 ? K6(v2···v7)中有红△ ? 设(v2v3)是红边 △v1v2v3是红△ 设△v2v3v4是红△ K4(v2v3v4v5)是蓝K4 √ √ Y Y Y N N N §３.9　Ramsey 问题 ∴　K9的边红、蓝２着色，必有红色三角 形或蓝色K4． 同理可证 K9的红、蓝２着色，必有蓝色三 角形或红色K4 ． (红△ ∨ 蓝K4) ∧ (蓝△∨ 红K4) ＝存在同色K4或红△及蓝 △ ＝同色K4 ∨(红△ ∧ 蓝△ )　 §３.9　Ramsey 问题 ( c )　K18的边红，蓝２着色，存在红K4 或蓝K4 ． 证　设18个顶点为v1 , v2 , ··· , v18 ．从v