Ramsey定理的应用[共6页]

第一节Ramsey定理在网络规划中的应用一、基础知识定义1.给定正整数n，r和图H1，H2，，Hr，用r种颜色对完全图Kn的所有边进行着色，由第i色边构成的子图记为Gi.如果存在一种着色方法，使得对所有的i(1≤i≤r)都有HiGi，则称Kn对于(H1，H2，，Hr)可r－着色.如果HlH2HrH，则简称Kn对于H可r－着色.定义2.使得Kn对于(,,,)不能r－着色的最小正整数n称为(经典)Ramsey数R().如果====，则把R()简写为Rr(p).定义3.使得Kn对于(H1，H2，，Hr)...