A list of edges of an acyclic undirected graph is given. It is necessary to find the optimal coloring (i.e. use the minimum number of colors) of the graph edges such that no two adjacent edges have the same color. Prompt the optimal or effective algorithm for solving.

  • one
    Bring to the coloring of the vertices (ie, build a graph, the vertices of which correspond to the edges of the original, and the edges - connect adjacent edges of the original graph), and the solutions are full of internet :) - Harry

1 answer 1

My solution (low efficiency): Set up an array of sets that will contain the colors of the edges of the corresponding vertices. For each edge we pass in a cycle from 1 to the maximum degree of the graph, if we see that the vertex can be colored in the i-th color, then we paint, immediately output the result and exit the cycle.