ทฤษฎีของ Vizing ระบุว่า Chromatic Index ของกราฟแบบง่าย (Simple Graph) สามารถเป็นได้เพียง Max Degree หรือ Max Degree + 1 เท่านั้น โดย Chromatic Index หมายถึงจำนวนสีสูงสุดที่จำเป็นสำหรับการระบายสีขอบ (Edge Coloring) ของกราฟ
นี่คือโปรแกรม C++ ที่นำทฤษฎีของ Vizing มาใช้งาน
อัลกอริทึม
เริ่มต้น รับจำนวนจุด (Vertices) และขอบ (Edges) เป็นอินพุต รับคู่จุดสำหรับขอบต่างๆ ฟังก์ชัน EdgeColor() : ระบายสีขอบของกราฟ 1) กำหนดสีให้ขอบปัจจุบันเป็น c คือ 1 เริ่มต้น 2) ถ้าสีเดียวกันถูกครอบครองโดยขอบที่อยู่ติดกันใดๆ แล้วทิ้งสีนี้และกลับไปที่ flag อีกครั้ง ลองกับสีถัดไป จบ
ตัวอย่างโค้ด
#include<iostream> using namespace std; void EdgeColor(int ed[][3], int e) { int i, c, j; for(i = 0; i < e; i++) { c = 1; //กำหนดสีให้ขอบปัจจุบัน 1 เริ่มต้น // ถ้าสีเดียวกันถูกครอบครองโดยขอบที่อยู่ติดกัน // แล้วทิ้งสีนี้และกลับไปที่ flag อีกครั้ง ลองสีถัดไป flag: ed[i][2] = c; for(j = 0; j < e; j++) { if(j == i) continue; if(ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] || ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) { if(ed[j][2] == ed[i][2]) { c++; goto flag; } } } } } int main() { int i, n, e, j, max = -1; cout<<"Enter the number of vertices of the graph: "; cin>>n; cout<<"Enter the number of edges of the graph: "; cin>>e; int ed[e][3], deg[n+1] = {0}; for(i = 0; i < e; i++) { cout<<"\nEnter the vertex pair for edge "<<i+1; cout<<"\nN(1): "; cin>>ed[i][0]; cout<<"N(2): "; cin>>ed[i][1]; //คำนวณ degree ของแต่ละจุด ed[i][2] = -1; deg[ed[i][0]]++; deg[ed[i][1]]++; } //หา maximum degree for(i = 1; i <= n; i++) { if(max < deg[i]) max = deg[i]; } EdgeColor(ed , e); cout<<"\nAccording to Vizing's theorem this graph can use maximum of "<<max+1<<" colors to generate a valid edge coloring.\n\n"; for(i = 0; i < e; i++) cout<<"\nThe color of the edge between vertex N(1):"<<ed[i][0]<<" and N(2):"<<ed[i][1]<<" is: color"<<ed[i][2]<<"."; }
ผลลัพธ์
Enter the number of vertices of the graph: 4 Enter the number of edges of the graph: 3 Enter the vertex pair for edge 1 N(1): 1 N(2): 2 Enter the vertex pair for edge 2 N(1): 3 N(2): 2 Enter the vertex pair for edge 3 N(1): 4 N(2): 1 According to Vizing's theorem this graph can use maximum of 3 colors to generate a valid edge coloring. The color of the edge between vertex N(1):1 and N(2):2 is: color1. The color of the edge between vertex N(1):3 and N(2):2 is: color2. The color of the edge between vertex N(1):4 and N(2):1 is: color2.
