Gustama, Muhammad Firza (2019) Desain dan Analisis Algoritma Cycle Detection in Weighted Graph pada Studi Kasus URI Online Judge Electrical Pollution. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111540000170-Undergraduate_Theses.pdf Download (1MB) | Preview |
Abstract
Permasalahan dalam buku tugas akhir ini adalah permasalahan yang diambil dari dunia nyata namun sudah disederhanakan kedalam bentuk soal yang terdapat pada situs URI Online Judge “Electrical Pollution”. Dalam permasalahan ini, diketahui bahwas generator yang digunakan untuk tenaga listrik rumah dan gedung menyebabkan anomali medan magnet lokal pada titik – titik tertentu pada suatu kota. Pada soal ini diberikan sebuah koordinat x dan y yang memiliki anomali. Suatu graf dibentuk dari setiap koordinat x dan y dengan bobot adalah anomali tersebut. Dicari anomali yang dihasilkan oleh generator pada koordinat lain. Tugas akhir ini akan mengimplementasikan deteksi siklus ganjil pada graf menggunakan Breadth First Search dan struktur data graf bipartit dalam menyelesaikan permasalahan Electrical Pollution. Implementasi dalam tugas akhir ini menggunakan bahasa pemrograman C++. Hasil uji coba menunjukkan bahwa sistem mendapatkan anomali pada koordinat lain dengan benar dan memiliki pertumbuhan waktu dengan kompleksitas O(N + V + E) dimana V adalah jumlah vertex dan E adalah jumlah Edge.
================================================================================================
The problem in this final assignment book is taken from the real world problem but has been simplified into the form of the questions found on the URI Online Judge “Electrical Pollution” site. In this problem, it is known that generators used for home and building electric power cause anomalies of local magentic fields at certain points in a city. In this problem given an x and y coordinate which has an anomaly. A graph formed from each x and y coordinate with weight is the anomaly. Look for anomalies generated by the generator in other coordinates. This final project will implement odd cycle detection in graphs using Breadth First Search and bipartite graph data structure in solving Electrical Pollution problems. Implementation in this final project uses C ++ programming language. The test results show that the system gets anomalies at other coordinates correctly and has a time growth with complexity O (N + V + E) where V is the number of vertices and E is the number of Edge.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.1 Gus i-1 2019 |
| Uncontrolled Keywords: | Bipartite Graph, Breadth First Search, Odd Cycle Graph |
| Subjects: | Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA76.6 Computer programming. Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation. Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Muhammad Firza Gustama |
| Date Deposited: | 26 Jul 2021 15:08 |
| Last Modified: | 26 Jul 2021 15:08 |
| URI: | http://repository.its.ac.id/id/eprint/61030 |
Actions (login required)
 |
View Item |