MENCARI MINIMUM SPANNING TREE DENGAN KONSTREN

Abstract

Misalkan G = (V, E) adalah graf tak berarah terhubung yang bukan tree, berarti di G terdapat cycle. Dengan cyclic interchange maka diperoleh subgraf T yang tidak memuat cycle. Subgraf T inilah yang dinamakan dengan spanning tree. Minimum spanning tree adalah spanning tree dengan jumlah bobot terkecil. Pada skripsi ini akan dibahas tentang bagaimana menentukan minimum spanning tree dengan konstren dari suatu graf terhubung sederhana.

Kata Kunci: Spanning tree, Minimum spanning tree, Spanning tree dengan konstren