Desain dan Analisis Algoritma untuk Mendapatkan Potongan Minimal pada Graf Tidak Berarah dan Berbobot dalam Penyelesaian Permasalahan Spoj Disgraph - Disconnected Country

Pradana, Findryan Kurnia (2019) Desain dan Analisis Algoritma untuk Mendapatkan Potongan Minimal pada Graf Tidak Berarah dan Berbobot dalam Penyelesaian Permasalahan Spoj Disgraph - Disconnected Country. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05111540000035-Undergraduated_Theses.pdf Restricted to Repository staff only Download (3MB) | Request a copy

Abstract

Permasalahan dalam buku Tugas Akhir ini diambil dari dunia nyata namun sudah disederhanakan ke dalam bentuk soal yang terdapat pada situs Sphere Online Judge “Disgraph - Disconnected Country”. Dalam permasalahan ini, diketahui bahwa kota-kota di negara kuno terhubung oleh jalan dua arah sehingga dari kota satu dapat menuju kota manapun. Namun seorang sultan ingin memisahkan negara tersebut menjadi dua bagian. Untuk menghancurkan jalan penghubung dengan jumlah minimal maka perlu dicari nilai potongan minimal. Tugas Akhir ini akan diimplementasikan dengan metode pencarian potongan minimal pada sebuah graf tak berarah dan berbobot. Metode pencarian potongan minimal yang digunakan adalah algoritma Stoer-Wagner. Dalam buku ini akan dibahas implementasi algoritma Stoer-Wagner untuk membagi dua negara tersebut dengan menggunakan bahasa pemograman C++. Dari serangkaian percobaan yang telah dilakukan, didapatkan kesimpulan bahwa algoritma yang dirancang adalah sesuai dengan permasalahan ini dan algoritma tersebut dipengaruhi secara kuadratik oleh jumlah simpul dan jumlah sisi. Secara umum algoritma ini memiliki kompleksitas O(|V||E| + |V| 2 log |V|).
==================================================================================================================================
The problem in this final project has been taken from the real world but it’s has been simplified into the form of questions which can be found on the Sphere Online Judge site "Disgraph - Disconnected Country". In this problem, it is known that cities in the ancient countries are connected by two-way roads so that one city can go to any city. But a sultan wants to separate the country into two parts. To destroy a connecting road with a minimal amount, it needs to find a minimum value to cut. This Final Project will implement a searching method for a minimum cut on an undirected and weighted graph, i.e., StoerWagner algorithm. In this book, the Stoer-Wagner algorithm will be discussed to divide the two countries which will be implemented by using the C++ programming language. From the experiment which have been done, it can be concluded that the algorithm designed in accordance with this problem and this algorithm has been influenced quadratically by the number of vertices and number of sides. In general, this algorithm has O(|V||E| + |V| 2 log |V|) complexity.

Item Type:	Thesis (Other)
Additional Information:	RSIf 005.73 Pra d-1 2019
Uncontrolled Keywords:	Potongan Minimal, Graf Tak Berarah, Graf Berbobot
Subjects:	Q Science > QA Mathematics > QA76.6 Computer programming. Q Science > QA Mathematics > QA76.758 Software engineering Q Science > QA Mathematics > QA76.76.A65 Application software. Enterprise application integration (Computer systems) Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis
Depositing User:	Findryan Kurnia Pradana
Date Deposited:	23 Jul 2026 03:47
Last Modified:	23 Jul 2026 03:47
URI:	http://repository.its.ac.id/id/eprint/68165

Actions (login required)

View Item