PENDEKATAN EUCLIDEAN STEINER MINIMUM TREE PADA POLIGON KONVEKS MENGGUNAKAN STEINER INSERTION HEURISTIC

Abstract

Permasalahan pendekatan Euclidean Steiner Minimum tree merupakan pengembangan dari spanning tree problem yaitu menentukan panjang total sisi minimum dari suatu graf, dengan menyisipkan titik-titik baru yang disebut Steiner point sesuai dengan karakteristiknya pada sudut-sudut interior yang kurang dari atau sama dengan 120 ο . Dalam pembahasan skripsi ini, Euclidean Steiner Minimum tree diaplikasikan pada poligon khususnya poligon konveks. Langkahlangkah pengkonstruksian Euclidean Steiner Minimum tree menggunakan Steiner

Insertion

Heuristic setelah penyisipan Steiner point pada bagian interior poligon konveks, yang selanjutnya memodifikasi sisi sehingga dihasilkan panjang total sisi yang lebih minimum daripada minimal spanning tree.