📄 3_11.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§11 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>§11 Ramsey数</b></font></p><p> 将上一节的问题一般化：给定一对正整数a、b，存在一个最小的正整数 r ,对 r 个顶 点的完全图的边任意红、蓝２着色，存在a个顶点的红边完全图或 b 个顶点的蓝边完全图。记为 r ( a , b )。比如：<br> r ( 3 , 3 )＝6，r ( 3 , 4 )＝9，r ( 4 , 4 )＝18</p><p><b>1.Ramsey数的简单性质</b></p><p><b>[定理]</b> r ( a , b )＝ r ( b , a )；r ( a , 2 )＝a<br><b>[证]</b> K<sub>r</sub>(a , b )的边红蓝２着色，有红K<sub>a</sub>或蓝 K<sub>b</sub>．将红蓝２色对换，就有红K<sub>b</sub>或蓝K<sub>a</sub>．<br> 设r( a , b )＝r ，K<sub>r</sub>的边任意红蓝２着色红蓝互换后仍是K<sub>r</sub>的边的２着色，由r(a,b) 的定义，有红K<sub>a</sub>或蓝K<sub>b</sub>．再红蓝对换恢复原图有红K<sub>b</sub>或蓝K<sub>a</sub>． </p><p>] </p><p><b>[例]</b> K<sub>9</sub>的边任意红蓝２着色，有红三角形或蓝K<sub>4</sub>． 红蓝对换后，仍有红三角形或蓝K<sub>4</sub>，再对换一次，回到原来的着色方案， 有蓝三角形或红K<sub>4</sub>．<br> 第二个等式容易看出．K<sub>a</sub>红蓝２着色若不全红(红K<sub>a</sub>)， 则必有一条蓝边．</p><p><b>[定理]</b> 当a , b ≥２时， r ( a , b )≤ r ( a －1 , b )＋ r ( a , b－1 )<br><b>证</b> 对r ( a －1 , b )＋ r ( a , b－1 ) 个顶点 的完全图红蓝２着色．任取其中一点 v，有<br>d<sub>r</sub>(v) + d<sub>b</sub>(v) = r( a －1 , b ) + r( a , b－1 )－1,从而可得判断树如下．<br><img src="3_11_1.gif" width="554" height="209"> </p><p><img src="3_11_2.gif" width="248" height="173"></p><p><b>[定理]</b> <img src="3_11_3.gif" align="middle" width="149" height="38"> <br><img src="3_11_4.gif" width="460" height="486"></p><p><b>2.Ramsey数的推广</b></p><p> 若将２着色改为k 着色，同色K<sub>a</sub>或同色K<sub>b</sub>改为同色 <img src="3_11_5.gif" align="middle" width="30" height="28">, i = 1 , 2 , … , k．即得Ramsey数r( a<sub>1</sub> ,a<sub>2</sub> ,… ,a<sub>k</sub>)． 对于给定的正整数 a<sub>i</sub> ( a<sub>i</sub>≥2) ，i = 1 , 2 , … , k．存在最小正整数r． 对K<sub>r</sub>的边用k中颜色C<sub>i</sub>( i = 1 , 2 , … , k)任意着色． 则存在 i ，出现全C<sub>i</sub>色的<imgsrc="3_11_5.gif" align="middle" width="30" height="28"> ．(即边都是C<sub>i</sub>色的a<sub>i</sub>个顶点的完全图）； 这个最小正整数 r 用 r (a<sub>1</sub> , … , a<sub>k</sub>)表示．</p><p><font color="#0000FF">有 r(a<sub>1</sub> , a<sub>2</sub> , … , a<sub>k</sub>)≤ r(a<sub>1</sub> , r( a<sub>2</sub> , … , a<sub>k</sub>) ) </font></p><p><b>[证]</b> 设r(a<sub>1</sub> ,r(a<sub>2</sub> , … ,a<sub>k</sub>))=p， r(a<sub>2</sub> , … , a<sub>k</sub>)=q；<br>对K<sub>p</sub>的边２着色，出现第一色<img src="3_11_6.gif" align="middle"width="30" height="29">或第二色K<sub>q</sub>， 用n－1中色对K<sub>q</sub>的边着色，至少出现i色的a<sub>i</sub>点完全图， i = 2 , … , n．对K<sub>p</sub>的边n 着色，将后n－1中色看作同一种色， 出现第一色<img src="3_11_6.gif" align="middle" width="30" height="29">或另一色(n－1种色看作另一色）的K<sub>q</sub>．即出现第i色 <img src="3_11_5.gif" align="middle" width="30" height="28"> ，i = 2 , … , n. 故 r(a<sub>1</sub> , a<sub>2</sub> , … ,a<sub>k</sub>)≤p</p><p><b>[例]</b> r(3 ,3 ,3)=17<br><b>[证]</b> 设三色为r ,b ,g．则对K<sub>17</sub>的任一顶点v ,有<br> d<sub>r</sub>(v) + d<sub>b</sub>(v) + d<sub>g</sub>(v) = 16；<br>因<img src="3_11_7.gif" align="middle" width="61" height="45"><br>故任一顶点与其他顶点的连线中，至少有６条同色．不妨设d<sub>r</sub>(v<sub>1</sub>)≥6, (v<sub>1</sub>v<sub>2</sub>)…(v<sub>1</sub>v<sub>7</sub>)都是红边．<br>从而可得如下判断树．<br><img src="3_11_8.gif"></p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -