📄 3_10.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§10 Ramsey问题</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"><link rel="stylesheet" href="../style.css"></head><body><p align="center"><font size="5"><b>§10 Ramsey问题</b></font></p><p><b>1.Ramsey问题</b></p><p> Ramsey问题可以看成是鸽巢原理的推广．下面举例说明Ramsey问题．</p><p><b>[例]</b> 6 个人中至少存在３人相互认识或者相互不认识．<br><b>[证]</b> 这个问题与K<sub>6</sub>的边２着色存在同色三角形等价．假定用红蓝着色． 设K<sub>6</sub>的顶点集为{v<sub>1</sub> , v<sub>2</sub> , ··· , v<sub>6</sub> }，d<sub>r</sub>(v)表 示与顶点 v 关联的红色边的条数，d<sub>b</sub>(v)表示与 v 关联的蓝色边的条数．在K<sub>6</sub>中，有 d<sub>r</sub>(v)＋ d<sub>b</sub>(v)＝５，由鸽巢原理可知，至少有３条边同色．<br> 现将证明过程用判断树表示如下：<br><img src="3_10_1.gif" width="530" height="439"> </p><p><b>2.若干推论</b></p><p><font color="#0000FF">( a ) K<sub>6</sub>的边用红蓝任意着色，则至少有两个同色的三角形．</font> </p><p><b>[证]</b> 由前定理知，有同色三角形，不妨设 △v<sub>1</sub>v<sub>2</sub>v<sub>3</sub>是红色三角形 可由如下判断树证明．<br><img src="3_10_2.gif" width="602" height="617"></p><p><b>( b )</b><font color="#0000FF"> K<sub>9</sub> 的边红蓝两色任意着色，则必有红K<sub>4</sub>或蓝色三角形(蓝K<sub>4</sub>或红色三角形)．<br></font><b>[证]</b> 设９个顶点为 v<sub>1</sub> , v<sub>2</sub> , ··· , v<sub>9</sub>．对９个 顶点的完全图的边的红、蓝２着色图中， 必然存在 v<sub>i</sub> ，使得 d<sub>r</sub>(v<sub>i</sub>)≠3 ．否则， 红边数＝<img src="3_10_3.gif"align="middle" width="113" height="45">，这是不可能的．<br>不妨设 d<sub>r</sub>(v<sub>1</sub>)≠3，可得如下判断树证明结论．<br><img src="3_10_4.gif" width="518" height="408"><br><br>∴ K<sub>9</sub>的边红、蓝２着色，必有红色三角形或蓝色K<sub>4</sub>．<br>同理可证 K<sub>9</sub>的红、蓝２着色，必有蓝色三角形或红色K<sub>4</sub> ．<br> (红△ ∨ 蓝K<sub>4</sub>) ∧ (蓝△∨ 红K<sub>4</sub>)<br>＝存在同色K<sub>4</sub>或红△及蓝△<br>＝同色K<sub>4</sub>∨(红△∧蓝△) </p><p><b>( c )</b> <font color="#0000FF">K<sub>18</sub>的边红，蓝２着色，存在红K<sub>4</sub>或蓝K<sub>4</sub> </font>．<br><b>[证]</b> 设18个顶点为v<sub>1</sub> , v<sub>2</sub> , ··· , v<sub>18</sub> ．从v<sub>1</sub>引出的17条边 至少有９条是同色的，不妨先假定为红色．从而可得下面的判断树证明命题．<br><img src="3_10_5.gif" width="542" height="356"></p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -