Astutik, Elly (2011) Menentukan lintasan terpendek (shortest path) menggunakan algoritma perfect matching minimum / Elly Astutik. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
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.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 27 Sep 2011 04:29 |
| Last Modified: | 09 Sep 2011 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17071 |
Actions (login required)
 |
View Item |