PEWARNAAN SIS GRAF DENGAN MENGGUNAKAN ALGORITMA VIZING

The development of knowledge for finishing a problem which can be

handled by an efficient algorithm is getting wider. The kind of problem can be

from easy until complicated problem, like graph coloring. Related to the

complication of that problem, from many kind of algorithms, it needs to know

which one of algorithms that is more efficient.

Graph coloring problem is one of the concept in undirected graph, how to

colour at every edge of undirected graph so that every edge connected with the

two vertex that giving a different color. Proper coloring with the minimum

number of color, in general, is a difficult task, this problem is one problem in

class of NP-complete that is hard to be solved.

One method to solve the graph coloring problem is using vizing

algorithm. Implementation of vizing algorithm where edge colored in either

maximum degree of the graph and maximum degree + 1 and complex time of

vizing algorithm is O(mn). For this goal give solution to graph coloring problem.