In graph theory, Vizing’s theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree ‘d’ of the graph. In simple meaning this theorem states that the chromatic index of the simple graph can be either ‘d’ or ‘d’ +1. The minimum number of colors needed for the edge coloring of the graph is called chromatic index.
There are 5 vertices in the above graph G. Highest Degree is 4, but we need 5 colors, so that no edge shares the same color with any edge of the adjacent vertices, as you can see in the above graph. Therefore the required number of valid colors for this graph is equal to 5, which is ( ‘highest degree’ + 1 ).
Note: c1, c2, c3, c4 and c5 in the above diagram implies distinct colors.
Examples :
Input :
v = 3, e = 3
{{ 1, 2, -1 },
{ 2, 3, -1 },
{ 3, 1, -1 }};
Output :
3 colors needs to generate a valid edge coloring :
color between v(1): 1 and v(2): 2 is: color 1
color between v(1): 2 and v(2): 3 is: color 2
color between v(1): 3 and v(2): 1 is: color 3
Algorithm:
- After initializing the number of edges, assign the vertex pair of every edge
- Color the graph edges according to the theorem
- Assign a color and then check its validity
- Check if any two adjacent edges have the same color, then increment the Color, goto flag and try next color
- Repeat till all the edges get it’s color according to the theorem
- Once done print the color of all the edges between the vertices
Below is the implementation of the above approach:
C++
// C++ program to illustrate// Vizing's Theorem#include <iostream>using namespace std;// Function to print the color of the edgevoid colorEdge(int edges[][3], int e){ int color; // Assign a color to every edge 'i'. for (int i = 0; i < e; i++) { color = 1; flag: // Assign a color and // then check its validity. edges[i][2] = color; for (int j = 0; j < e; j++) { if (j == i) continue; // If the color of edges // is adjacent to edge i if ((edges[i][0] == edges[j][0]) || (edges[i][1] == edges[j][0]) || (edges[i][0] == edges[j][1]) || (edges[i][1] == edges[j][1])) { // If the color matches if (edges[i][2] == edges[j][2]) { // Increment the color, // denotes the change in color. color++; // goes back, and assigns // the next color. goto flag; } } } } // Check the maximum color from all the edge colors int maxColor = -1; for (int i = 0; i < e; i++) { maxColor = max(maxColor, edges[i][2]); } cout << maxColor << " colors needs to generate a valid edge " "coloring:" << endl; for (int i = 0; i < e; i++) { cout << "color between v(1): " << edges[i][0] << " and v(2): " << edges[i][1] << " is: color " << edges[i][2] << endl; }}// Driver Codeint main(){ // initialize the number // of edges of the graph int e = 5; // initialize the vertex // pair of every edge in a graph int edges[e][3] = { { 1, 2, -1 }, { 2, 3, -1 }, { 3, 4, -1 }, { 4, 1, -1 }, { 1, 3, -1 } }; colorEdge(edges, e); return 0;} |
Java
// Java program to illustrate// Vizing's Theoremimport java.util.*;public class VizingsTheorem { // Function to find the chromatic index public void colorEdge(int[][] edges, int e) { // Initialize edge to first edge and // color to color 1 int i = 0, color = 1; // Repeat until all edges are done coloring while (i < e) { // Give the selected edge a color edges[i][2] = color; boolean flag = false; // Iterate through all others edges to check for (int j = 0; j < e; j++) { // Ignore if same edge if (j == i) continue; // Check if one vertex is similar if ((edges[i][0] == edges[j][0]) || (edges[i][1] == edges[j][0]) || (edges[i][0] == edges[j][1]) || (edges[i][1] == edges[j][1])) { // Check if color is similar if (edges[i][2] == edges[j][2]) { // Increment the color by 1 color++; flag = true; break; } } } // If same color faced then repeat again if (flag == true) { continue; } // Or else proceed to a // new vertex with color 1 color = 1; i++; } // Check the maximum color from all the edge colors int maxColor = -1; for (i = 0; i < e; i++) { maxColor = Math.max(maxColor, edges[i][2]); } System.out.println( maxColor + " colors needs to generate" +" a valid edge coloring:"); for (i = 0; i < e; i++) { System.out.println( "color between v(1): " + edges[i][0] + " and v(2): " + edges[i][1] + " is: color " + edges[i][2]); } } // Driver code public static void main(String[] args) { // Number of edges int e = 5; // Edge list int[][] edges = new int[e][3]; // Initialize all edge colors to 0 for (int i = 0; i < e; i++) { edges[i][2] = -1; } // Edges edges[0][0] = 1; edges[0][1] = 2; edges[1][0] = 2; edges[1][1] = 3; edges[2][0] = 3; edges[2][1] = 4; edges[3][0] = 4; edges[3][1] = 1; edges[4][0] = 1; edges[4][1] = 3; // Run the function VizingsTheorem c = new VizingsTheorem(); c.colorEdge(edges, e); }} |
Python3
def colorEdge(edges, e): # Initialize edge to first edge and # color to color 1 i = 0 color = 1 # Repeat until all edges are done coloring while(i < e): # Give the selected edge a color edges[i][2] = color flag = False # Iterate through all others edges to check for j in range(e): # Ignore if same edge if (j == i): continue # Check if one vertex is similar if ((edges[i][0] == edges[j][0])or (edges[i][1] == edges[j][0]) or (edges[i][0] == edges[j][1]) or (edges[i][1] == edges[j][1])): # Check if color is similar if (edges[i][2] == edges[j][2]): # Increment the color by 1 color += 1 flag = True break # If same color faced then repeat again if (flag == True): continue # Or else proceed to a new vertex with color 1 color = 1 i += 1 # Check the maximum color from all the edge colors maxColor = -1 for i in range(e): maxColor = max(maxColor, edges[i][2]) print(str(maxColor)+" colors needs to generate a valid edge coloring:") for i in range(e): print("color between v(1): "+str(edges[i][0])+" and v(2): " + str(edges[i][1])+" is: color "+str(edges[i][2]))# Driver codeif __name__ == "__main__": # Number of edges e = 5 # Edge list edges = [[0 for _ in range(3)] for _ in range(e)] # Initialize all edge colors to 0 for i in range(e): edges[i][2] = -1 # Edges edges[0][0] = 1 edges[0][1] = 2 edges[1][0] = 2 edges[1][1] = 3 edges[2][0] = 3 edges[2][1] = 4 edges[3][0] = 4 edges[3][1] = 1 edges[4][0] = 1 edges[4][1] = 3 # Run the function colorEdge(edges, e) |
C#
using System;public class VizingsTheorem{ // Function to find the chromatic index public void colorEdge(int[,] edges, int e) { // Initialize edge to first edge and color to color 1 int i = 0, color = 1; // Repeat until all edges are done coloring while (i < e) { // Give the selected edge a color edges[i, 2] = color; bool flag = false; // Iterate through all others edges to check for (int j = 0; j < e; j++) { // Ignore if same edge if (j == i) continue; // Check if one vertex is similar if ((edges[i, 0] == edges[j, 0]) || (edges[i, 1] == edges[j, 0]) || (edges[i, 0] == edges[j, 1]) || (edges[i, 1] == edges[j, 1])) { // Check if color is similar if (edges[i, 2] == edges[j, 2]) { // Increment the color by 1 color++; flag = true; break; } } } // If same color faced then repeat again if (flag == true) continue; // Or else proceed to a new vertex with color 1 color = 1; i++; } // Check the maximum color from all the edge colors int maxColor = -1; for (i = 0; i < e; i++) { maxColor = Math.Max(maxColor, edges[i, 2]); } Console.WriteLine(maxColor + " colors needs to generate a valid edge coloring:"); for (i = 0; i < e; i++) { Console.WriteLine("color between v(1): " + edges[i, 0] + " and v(2): " + edges[i, 1] + " is: color " + edges[i, 2]); } } // Driver code public static void Main(string[] args) { // Number of edges int e = 5; // Edge list int[,] edges = new int[e, 3]; // Initialize all edge colors to 0 for (int i = 0; i < e; i++) edges[i, 2] = -1; // Edges edges[0, 0] = 1; edges[0, 1] = 2; edges[1, 0] = 2; edges[1, 1] = 3; edges[2, 0] = 3; edges[2, 1] = 4; edges[3, 0] = 4; edges[3, 1] = 1; edges[4, 0] = 1; edges[4, 1] = 3; // Run the function VizingsTheorem c = new VizingsTheorem(); c.colorEdge(edges, e); }} |
Javascript
<script>// JavaScript program to illustrate// Vizing's Theorem// Function to find the chromatic indexfunction colorEdge(edges, e){ // Initialize edge to first edge and // color to color 1 var i = 0, color = 1; // Repeat until all edges are done coloring while (i < e) { // Give the selected edge a color edges[i][2] = color; var flag = false; // Iterate through all others edges to check for (var j = 0; j < e; j++) { // Ignore if same edge if (j == i) continue; // Check if one vertex is similar if ((edges[i][0] == edges[j][0]) || (edges[i][1] == edges[j][0]) || (edges[i][0] == edges[j][1]) || (edges[i][1] == edges[j][1])) { // Check if color is similar if (edges[i][2] == edges[j][2]) { // Increment the color by 1 color++; flag = true; break; } } } // If same color faced then repeat again if (flag == true) { continue; } // Or else proceed to a // new vertex with color 1 color = 1; i++; } // Check the maximum color from all the edge colors var maxColor = -1; for (i = 0; i < e; i++) { maxColor = Math.max(maxColor, edges[i][2]); } document.write( maxColor + " colors needs to generate" +" a valid edge coloring:<br>"); for (i = 0; i < e; i++) { document.write( "color between v(1): " + edges[i][0] + " and v(2): " + edges[i][1] + " is: color " + edges[i][2] + "<br>"); }}// Driver code// Number of edgesvar e = 5;// Edge listvar edges = Array.from(Array(e), ()=>Array(3));// Initialize all edge colors to 0for (var i = 0; i < e; i++) { edges[i][2] = -1;}// Edgesedges[0][0] = 1;edges[0][1] = 2;edges[1][0] = 2;edges[1][1] = 3;edges[2][0] = 3;edges[2][1] = 4;edges[3][0] = 4;edges[3][1] = 1;edges[4][0] = 1;edges[4][1] = 3;// Run the functioncolorEdge(edges, e);</script> |
Output
3 colors needs to generate a valid edge coloring: color between v(1): 1 and v(2): 2 is: color 1 color between v(1): 2 and v(2): 3 is: color 2 color between v(1): 3 and v(2): 4 is: color 1 color between v(1): 4 and v(2): 1 is: color 2 color between v(1): 1 and v(2): 3 is: color 3
Time Complexity: O(e2)
Auxiliary Space: O(1)
As constant extra space is used.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
