โปรแกรม C++ เพื่อค้นหาดัชนีรงค์ของกราฟวัฏจักร

ดัชนีสีคือจำนวนสีสูงสุดที่จำเป็นสำหรับการระบายสีขอบของกราฟที่กำหนด นี่คือโปรแกรม C++ เพื่อค้นหาดัชนีรงค์ของกราฟวัฏจักร

อัลกอริทึม

Begin
   Take the input of the number of vertices ‘n’ and number of edges ‘e’.
   Take the input of ‘e’ vertex pairs for the ‘e’ edges in the graph in edge[][].
   Function ChromaticIndex(), Color the graph edges:
   A) assign color to current edge as c.
   B) If any of the adjacent edges have the same color then discard this color and go to flag again and try with next color.
   C) Print the chromatic index of the cyclic graph.
   Print the color of each edge.
End

ตัวอย่าง

#include<iostream>
using namespace std;
int ChromaticIndex(int ed[][3], int e) {
   int i, c, j, max = -1;
   //to assign a valid color to every edge 'i'.
   for(i = 0; i < e; i++) {
      c = 1;
      flag:
         //assign color to current edge
         ed[i][2] = c;
         for(j = 0; j < e; j++) {
            if(j == i)
               continue;
               //Check the colors of the edges adjacent to the edge i.
               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;
                  }
               }
         }
   }
   // Find the coloring index and return it
   for(i = 0; i < e; i++) {
      if(max < ed[i][2])
         max = ed[i][2];
   }
   return max;
}
int main() {
   int i, v, e, j, max = -1;
   cout<<"Enter the number of vertices of the graph: ";
   cin>>v;
   cout<<"Enter the number of edges of the graph: ";
   cin>>e;
   int ed[e][3];
   for(i = 0; i < e; i++) {
      cout<<"\nEnter the vertex pair for edge "<<i+1;
      cout<<"\nV(1): ";
      cin>>ed[i][0];
      cout<<"V(2): ";
      cin>>ed[i][1];
      ed[i][2] = -1;
   }
   cout<<"\n\nThe chromatic index of the given graph is: "<<ChromaticIndex(ed , e);
   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: 5
Enter the vertex pair for edge 1
V(1): 2
V(2):1
Enter the vertex pair for edge 2
V(1): 3
V(2): 2
Enter the vertex pair for edge 3
V(1): 3
V(2): 1
Enter the vertex pair for edge 4
V(1): 4
V(2): 2
Enter the vertex pair for edge 5
V(1):1
V(2): 3
The chromatic index of the given graph is: 4
The color of the edge between vertex n(1):2 and n(2):1 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):3 and n(2):1 is: color3.
The color of the edge between vertex n(1):4 and n(2):2 is: color3.
The color of the edge between vertex n(1):1 and n(2):3 is: color4.