Skripsi

Penerapan algoritma exact untuk pencarian pohon rentang dengan daun terbanyak (maximum leaf spanning tree) / Mukhamad Sihabudin

Abstrak
Sihabudin Mukhamad. 2013. Penerapan Algoritma Exact Untuk Pencarian Pohon Rentang Dengan Daun Terbanyak (Maximum Leaf Spanning Tree). Skripsi Jurusan Matematika FMIPA Universitas Negeri Malang. Pembimbing Prof. Drs. Purwanto Ph.D. Kata kunci pohon rentang daun terbanyak titik dalam (internal nodes) titik daun (leaf nodes) algoritma exact. 12288 12288 12288 Pohon rentang daun terbanyak (maximum leaf spanning tree) adalah salah satu permasalahan yang dibahas di dalam teori graph. Pohon rentang G terdiri dari dua himpunan titik yaitu titik dalam (titik internal) dan titik daun (leaf nodes). Suatu pohon rentang dari graph G dikatakan mempunyai daun terbanyak jika pohon rentang tersebut mempunyai titik daun terbanyak dan tidak ditemukan lagi pohon rentang yang lain yang mempunyai titik daun lebih banyak. 12288 12288 12288 Salah satu manfaat dari penggunaan pohon rentang daun terbanyak adalah untuk penentuan suatu sistem jaringan. Dengan tujuan mendapatkan user sebanyak mungkin dan membuat server sesedikit mungkin. Selain itu pohon rentang daun terbanyak juga dapat digunakan untuk penentuan posisi penyiar radio. Oleh karena itu studi mengenai pohon rentang daun terbanyak telah dilakukan sejak lama. Sudah banyak percobaan pencarian metode baru untuk menentukan penyelesaian dari permasalahan pohon rentang daun terbanyak yang lebih cepat. 12288 12288 12288 Metode dalam penentuan pohon rentang dengan daun terbanyak adalah membangun suatu pohon bagian T (subtree) yang memperluas graph G. Proses tersebut dilakukan berulang-ulang dengan menggunakan aturan reduksi dan algoritma exact. Dengan suatu kondisi awal yang tidak ditentukan maka harus dipilih titik awal dengan derajat terbesar sehingga bisa diperoleh suatu pohon rentang dengan daun terbanyak. Jika kondisi awal ditentukan maka kita bisa melanjutkan proses aturan reduksi dan algoritma exact dengan kondisi awal tersebut. Algoritma exact memberikan beberapa pilihan didalam iterasinya. Hal ini memungkinkan terbentuknya pohon rentang daun terbanyak tidak selalu tunggal.

Informasi Detail

DDC

Rs 511.8 SIH p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2013.

Deskripsi Fisik

vii, 63 lembar : il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

04821/KI/13

Edisi

Skripsi (Sarjana) -- Universitas Negeri Malang, 2013

Subjek

1. ALGORITMA
2. POHIN RENTANG

Pembimbing

1. Purwanto

Lampiran Berkas