PENGGUNAAN METODE CUTTING PLANE UNTUK MENYELESAIKAN MINIMUM SPANNING TREE DENGAN KENDALA BOBOT PADA GRAF K_n

Abstract

This study aims to determine the minimum spanning tree of a complete graph K_n with weight constraints and completion using the cutting plane method. The cutting plane method is one of the algorithms included in the exact method. This algorithm works by reducing the solution area so that it becomes narrower. As a result, the feasible solutions that will be investigated become less and less. This is because the cutting plane method works based on the optimal linear programming solution of relaxation solved by the simplex method. In this paper we give illustration of the algorithm applied for two cases, one for K_4 and one for K_5.

Keywords

• complete graph
• cutting plane method
• minimum spanning tree
• tree