C++ प्रोग्राम: Vizing's Theorem का कार्यान्वयन

Vizing's Theorem के अनुसार, किसी सिंपल ग्राफ का क्रोमैटिक इंडेक्स (एज कलरिंग के लिए आवश्यक अधिकतम रंग) या तो अधिकतम डिग्री (Δ) होता है या Δ+1। यह C++ प्रोग्राम इस थ्योरम को दर्शाता हुआ ग्राफ के एजेज को कलर करता है।

एल्गोरिदम

शुरुआत
  1. वर्टेक्स और एज की संख्या इनपुट लें।
  2. प्रत्येक एज के लिए वर्टेक्स जोड़ी लें।
  3. फंक्शन EdgeColor(): ग्राफ के एजेज को कलर करें।
     - वर्तमान एज को कलर c असाइन करें (प्रारंभ में 1)।
     - यदि वही कलर किसी आसन्न एज द्वारा उपयोग किया गया है,
       तो इस कलर को छोड़ें और अगले कलर के साथ पुनः प्रयास करें।
समाप्ति

उदाहरण कोड

#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:
        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, maxDeg = -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];
        
        ed[i][2] = -1; // कलर इनिशियलाइज़ करें
        deg[ed[i][0]]++;
        deg[ed[i][1]]++;
    }
    
    // अधिकतम डिग्री खोजें
    for (i = 1; i <= n; i++) {
        if (maxDeg < deg[i]) maxDeg = deg[i];
    }
    
    EdgeColor(ed, e);
    
    cout << "\nAccording to Vizing's theorem this graph can use maximum of "
         << maxDeg + 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] << ".";
    
    return 0;
}

आउटपुट

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.

व्याख्या: इस उदाहरण में ग्राफ में 4 वर्टेक्स और 3 एज हैं। अधिकतम डिग्री 2 है (वर्टेक्स 2 की डिग्री 2 है), इसलिए Vizing's Theorem के अनुसार अधिकतम 3 रंगों (Δ+1) की आवश्यकता होगी। प्रोग्राम लालची दृष्टिकोण (greedy approach) का उपयोग करके एजेज को कलर करता है।