Skripsi

Menentukan lintasan terpendek (shortest path) menggunakan algoritma perfect matching minimum / Elly Astutik

Abstrak
Kata Kunci Shortest Path Perfect Matching Minimum Lintasan terpendek (Shortest Path) merupakan salah satu cabang yang ada dalam konsep graph. Permasalahan lintasan terpendek adalah permasalahan menentukan lintasan minimum dari suatu titik s ke titik t yang digambarkan dalam bentuk graph baik graph berbobot maupun graph tidak berbobot. Permasalahan lintasan terpendek dapat diselesaikan dengan algoritma yang digunakan untuk menentukan perfect matching minimum. Dalam graph matching didefinisikan sebagai himpunan sisi 119872 8838 119864 sedemikian hingga tidak ada 2 sisi yang terkait dengan 1 titik yang sama sedangkan perfect matching minimum adalah matching M dengan setiap titik di 119881 dengan terkait tepat satu sisi di M dengan bobot minimum. Menyelesaikan permasalahan lintasan terpendek pada graph G menggunakan algoritma perfect matching minimum dilakukan dengan mentransformasi graph G menjadi graph H yang merupakan graph pengganti kemudian menentukan perfect matching minimum pada graph pengganti H. Terdapat beberapa algoritma yang digunakan dalam menentukan perfect matching minimum salah satunya adalah algoritma Mulmuley Vazirani. Algoritma Mulmuley Vazirani merupakan algoritma yang dikerjakan dalambentuk matriks dan matriks yang digunakan adalah matriks Tutte. Algoritma inidapat diterapkan pada graph bipartisi maupun graph non bipartisi. Pada dasarnyalangkah langkah algoritma ini sama untuk graph bipartisi maupun graph nonbipartisi perbedaannya terletak pada ukuran matriks yang digunakan. Jika jumlahtitik suatu graph adalah n dan graph tersebut merupakan graph bipartisi maka ukuran matriks yang digunakan adalah n/2 x n/2 jika graph tersebut merupakan graph non bipartisi maka ukuran matriks yang digunakan adalah n x n.

Informasi Detail

DDC

Rs 511.5 AST m

Prodi

Universitas Negeri Malang. Jurusan Matematika, 2011.

Deskripsi Fisik

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

Bahasa

Indonesia

No Reg

04116/KI/11

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2011

Subjek

1. GRAPH
2. ALGORITMA
3. LINTASAN TERPENDEK

Pembimbing

1. PURWANTO ; 2. SUSY KUSPAMBUDI ANDAINI

Lampiran Berkas