Answer to Question #140767 in Discrete Mathematics for Joseph Se

Question

A. Give a summary of the Greedy Algorithm.
B. Give a summary of the Edge-Picking Algorithm.
C. What is a graph coloring, and how is it applied?

Answer 1

A. summary of the Greedy Algorithm

A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem.

B. summary of the Edge-Picking Algorithm.

The edge-picking algorithm states to mark the edge that has the smallest weight in the complete graph. Then, the edge with the next smallest weight is marked as long as it does not complete a circuit and does not add a third marked edge to a single vertex. This process continues till no longer an edge can be marked.

C. A graph coloring

Graph coloring problem is to assign colors to certain elements of a graph subject to certain constraints. The problem is, given m colors, find a way of coloring the vertices of a graph such that no two adjacent vertices are colored using same color.