Teorema de Vizing

En la teoría de grafos, el teorema de Vizing establece que cada gráfico simple no dirigido puede tener bordes coloreados usando una cantidad de colores que es como máximo uno más grande que el grado máximo ‘d’ del gráfico. En sentido simple, este teorema establece que el índice cromático del gráfico simple puede ser ‘d’ o ‘d’ +1 . El número mínimo de colores necesarios para la coloración de los bordes del gráfico se denomina índice cromático. 
 

Hay 5 vértices en el gráfico anterior G. El grado más alto es 4, pero necesitamos 5 colores, para que ningún borde comparta el mismo color con ningún borde de los vértices adyacentes, como puede ver en el gráfico anterior. Por lo tanto, el número requerido de colores válidos para este gráfico es igual a 5, que es (‘grado más alto’ + 1). 
Nota: c1, c2, c3, c4 y c5 en el diagrama anterior implica colores distintos.
 

Ejemplos:

Entrada: 
v = 3, e = 3 
{{ 1, 2, -1 }, 
{ 2, 3, -1 }, 
{ 3, 1, -1 }}; 
Salida: 
3 colores necesitan generar una coloración de borde válida:
color entre v(1): 1 y v(2): 2 es: color 1 
color entre v(1): 2 y v(2): 3 es: color 2 
color entre v(1): 3 y v(2): 1 es: color 3

Algoritmo: 

• Después de inicializar el número de aristas, asigne el par de vértices de cada arista
• Colorea los bordes del gráfico según el teorema
• Asigne un color y luego verifique su validez
• Verifique si dos bordes adyacentes tienen el mismo color, luego incremente el Color, vaya a la bandera e intente con el siguiente color
• Repita hasta que todos los bordes obtengan su color de acuerdo con el teorema.
• Una vez hecho, imprima el color de todos los bordes entre los vértices.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to illustrate
// Vizing's Theorem
#include <iostream>
using namespace std;
 
// Function to print the color of the edge
void 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 Code
int 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 program to illustrate
// Vizing's Theorem
import 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);
    }
}

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 code
 
if __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)

<script>
 
// JavaScript program to illustrate
// Vizing's Theorem
// Function to find the chromatic index
function 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 edges
var e = 5;
// Edge list
var edges = Array.from(Array(e), ()=>Array(3));
// Initialize all edge colors to 0
for (var 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
colorEdge(edges, e);
 
 
</script>

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