Many other resource allocation prob

Many other resource allocation problems boil down to coloring some graph. In general, a graph G is k­colorable if each vertex can be assigned one of k colors so that adjacent ver­tices get different colors. The smallest sufficient number of colors is called the chromatic number of G. The chromatic number of a graph is generally difficult to compute, but the following theorem provides an upper bound:

ผลลัพธ์ (ไทย) 1:

ในทรัพยากรการปันส่วนปัญหาอื่น ๆ ต้มลงการระบายสีกราฟบาง โดยทั่วไป กราฟ G คือ kcolorable ถ้าแต่ละจุดสามารถกำหนด k สีอย่างใดอย่างหนึ่งเพื่อให้ข้าง ๆ สีแตกต่างกัน หมายเลข sufficient น้อยที่สุดของสีคือจำนวนกรัมเครื่องตั้งสาย หมายเลขเครื่องตั้งสายของกราฟโดยทั่วไปจะ difficult การคำนวณ แต่ทฤษฎีบทต่อไปนี้ให้เป็นขอบเขตบน:

ผลลัพธ์ (ไทย) 2:

หลายปัญหาการจัดสรรทรัพยากรอื่น ๆ ต้มลงไปสีกราฟบาง โดยทั่วไปกราฟ G เป็น kcolorable ถ้าแต่ละจุดสุดยอดสามารถกำหนดสีใดสีหนึ่ง k เพื่อให้จุดที่อยู่ติดกันได้สีที่แตกต่างกัน พอเพียงสายที่เล็กที่สุดจำนวนเพียงพอของสีที่เรียกว่าสีจำนวนของ G. สีจำนวนของกราฟโดยทั่วไปยากที่จะคำนวณ แต่ทฤษฎีบทต่อไปนี้ให้ขอบเขตบน:

ผลลัพธ์ (ไทย) 3:

ปัญหาการจัดสรรทรัพยากรหลายๆสีบางลงต้มกับกราฟ โดยทั่วไปกราฟ G รึเปล่าคือ K องหน้าแดงถ้าแต่ละแผนกสามารถกำหนด K สีไหมที่ติดกัน Ver อง tices ได้รับสีที่แตกต่าง ที่เล็กที่สุดซุฟจึง cient จำนวนสี เรียกว่า จํานวนโครมาติกของกรัม หมายเลขรงค์ของกราฟโดยทั่วไปจึงแยกศาสนาเพื่อคํานวณแต่ทฤษฎีบทต่อไปนี้ให้ไว้ด้านบน :