第一节 Ramsey定理在网络规划中的应用一、基础知识定义1. 给定正整数n，r和图H1，H2，Hr，用r种颜色对完全图Kn的所有边进行着色，由第i色边构成的子图记为Gi.如果存在一种着色方法，使得对所有的i(1ir)都有HiGi，则称Kn对于(H1，H2，Hr)可r着色.如果HlH2HrH，则简称Kn对于H可r着色.定义2. 使得Kn对于(, )不能r着色的最小正整数n称为(经典)Ramsey数R().如果=，则把R()简写为Rr(p).定义3. 使得Kn对于(H1，H2，Hr)不能r着色的最小正整数n称为广义Ramsey数R(H1，H2，Hr).如果HlH2HrH，则把R(Hl，H2，Hr)简写为Rr(H).定理1. R(C4,C4)=6定理2. R(C4,C4,C4)=11定理3.若一个n个顶点的图至少有条边，则它总包含C4。二、分组交换网的设计 分组交换网是采用分组交换技术的网络，它从终端或计算机接收报文，把报文分割成分组，并按某种策略选择最佳路径在网中传输，到达目的地后再将分组合并成报文交给
