Perancangan dan Analisis Algoritma untuk Mencari Clique Bobot Maksimum pada Kasus Good graph Menggunakan Metode Disjoint Set Union: Studi Kasus Eolymp 3417 Good Graphs

Amari, Luthfiyyah (2024) Perancangan dan Analisis Algoritma untuk Mencari Clique Bobot Maksimum pada Kasus Good graph Menggunakan Metode Disjoint Set Union: Studi Kasus Eolymp 3417 Good Graphs. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201090_Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (3MB)

Abstract

Salah satu permasalahan pada teori graf ialah permasalahan mencari maximum weight clique dalam sebuah graf. Permasalahan ini menjadi fokus penelitian. Dalam permasalahan ini, setiap vertex dalam maximum weight clique memiliki bobot atau nilai tertentu. Clique adalah subgraf lengkap, yakni subgraf yang setiap vertex di dalamnya terhubung dengan semua vertex lain. Pada suatu graf, bisa terdapat banyak Clique yang terbentuk. Maximum weight clique adalah Clique yang memiliki total nilai bobot tertinggi. Fokus utama dalam penelitian ini adalah pada permasalahan 3417 Good Graphs yang terdapat di situs Eolymp. Soal ini meminta mencari bobot maksimal clique pada kasus good graph. Good graph adalah graf khusus yang didefinisikan pada persoalan.
Secara umum, permasalahan Maximum weight clique diklasifikasikan ke dalam NP. Namun, dalam kasus ini, karakteristik khusus pada good graph dapat dimanfaatkan untuk mengembangkan algoritma yang efisien dan berbentuk polinomial. Permasalahan tersebut akan diselesaikan dengan memanfaatkan prinsip teori graf dan mengembangkan algoritma khusus yang dirancang untuk menangani karakteristik unik dari good graph. Tugas akhir ini mengusung pengembangan algoritma dengan pendekatan rekursif atau divide and conquer dan menerapkan struktur data disjoint set union untuk memeriksa konektivitas graf dan mengidentifikasi komponen terhubung.
Berdasarkan hasil uji coba pada studi kasus yang diberikan, solusi menggunakan metode disjoint set membutuhkan waktu sebesar 0,003 detik dan rata-rata memori sebesar 1,260 MiB. Solusi ini berhasil mendapat grade A+, yang berarti solusi lulus semua tes dan menggunakan lebih sedikit sumber daya dibandingkan 99% solusi lainnya.
========================================================================================================================
One of the problems in graph theory is finding the maximum weight clique in a graph. This problem has become a focus of research. In this problem, each node in the maximum weight clique has a certain weight or value. A clique is a complete subgraph, meaning every node within it is connected to all other nodes. In a given graph, multiple cliques can be formed. The maximum weight clique is the clique with the highest total weight. The main focus of this research is on the problem of 3417 Good Graphs found on the Eolymp website. This problem requires finding the maximum weight of a clique in the case of a good graph. Good graph is a special graph that is defined in the problem.
In general, the maximum weight clique problem is classified as NP. However, in this case, the unique characteristics of good graphs can be leveraged to develop an efficient polynomial-time algorithm. This problem will be solved by utilizing graph theory principles and developing a specific algorithm designed to handle the unique characteristics of good graphs. This final project focuses on developing an algorithm using a recursive or divide-and-conquer approach and implementing the disjoint set union data structure to check graph connectivity and identify connected components.
Based on the test results on the provided case study, the solution using the disjoint set method took 0.003 seconds and an average memory usage of 1.260 MiB. This solution received a grade of A+, meaning it passed all tests and used fewer resources than 99% of other solutions.

Item Type:	Thesis (Other)
Subjects:	Q Science > QA Mathematics > QA76.F56 Data structures (Computer science)
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	luthfiyyah hanifah amari
Date Deposited:	01 Aug 2024 05:32
Last Modified:	01 Aug 2024 05:32
URI:	http://repository.its.ac.id/id/eprint/109754

Actions (login required)

View Item