Perancangan dan Analisis Algoritma Pembangkit Struktur Graf Kaktus pada Permasalahan: Studi Kasus E-Olymp 9582 - Cactus Revenge

Maheswari, Hana (2025) Perancangan dan Analisis Algoritma Pembangkit Struktur Graf Kaktus pada Permasalahan: Studi Kasus E-Olymp 9582 - Cactus Revenge. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211182-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (7MB) | Request a copy

Abstract

E-Olymp merupakan situs penilaian kode daring yang menyediakan berbagai soal algoritma dan struktur data dengan beragam tingkat kesulitan. Pengguna dapat mengirimkan solusi dalam bentuk program untuk dievaluasi secara otomatis. Tugas akhir ini mengkaji studi kasus dari soal E-Olymp dengan kode 9582 berjudul “Cactus Revenge”.
Permasalahan ini berfokus pada graf kaktus, yaitu graf di mana setiap dua siklus sederhana berbagi paling banyak satu vertex. Dalam kasus ini, masukan berupa jumlah vertex dan konfigurasi derajat masing-masing vertex. Tujuannya adalah membentuk graf yang memenuhi properti graf kaktus sesuai dengan derajat yang telah ditentukan. Penyelesaian dilakukan dengan pendekatan yang merujuk pada sifat dasar graf kaktus. Strategi disusun secara iteratif melalui tahapan validasi derajat, pemisahan antara kasus tanpa siklus dan dengan siklus, serta konstruksi graf secara bertahap.
Metode pengujian pada tugas akhir ini dilakukan untuk mengevaluasi kebenaran solusi, yaitu dengan mengirimkan kode sumber dari implementasi algoritma ke sistem penilaian daring E-Olymp. Berdasarkan hasil pengujian, algoritma yang dirancang berhasil menyelesaikan seluruh uji kasus dengan waktu rata-rata eksekusi 1 milidetik dan penggunaan memori sebesar 0,49 MB pada sepuluh pengujian. Hasil ini menunjukkan bahwa pendekatan berbasis properti graf kaktus dapat menyelesaikan studi kasus secara tepat dan efisien sesuai dengan batasan sistem.
======================================================================================================================================
E-Olymp is an online code judge site that offers various algorithm and data structure problems with different levels of difficulty, which users can solve by submitting code. This undergraduate thesis examines a case study based on problem 9582 titled “Cactus Revenge”.
The problem focuses on the cactus graph, a graph in which any two cycles share at most one vertex. Given the number of vertices and desired degrees for each vertex. The goal of this case study is to generate a graph that adheres to the properties of a cactus graph and satisfies the specified degree constraints. The solution is done with an approach that refers to the basic properties of cactus graphs. The strategy is developed iteratively through the stages of degree validation, separation between cases without cycle and with cycle, and gradual graph construction.
The testing method was conducted to evaluate the correctness of the solution by sending the source code of the algorithm implementation to the E-Olymp online assessment system. Based on test result, the solution successfully completed the problem within 1 millisecond and used 0.49 MB of memory in ten tests, complying with the constraints set by the E-Olymp online judge.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	derajat vertex, graf kaktus, properti graf kaktus, cactus graph, cactus graph properties, vertex degree
Subjects:	Q Science > QA Mathematics > QA166 Graph theory T Technology > T Technology (General) > T11 Technical writing. Scientific Writing
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Hana Maheswari
Date Deposited:	10 Jul 2025 04:29
Last Modified:	10 Jul 2025 04:29
URI:	http://repository.its.ac.id/id/eprint/119461

Actions (login required)

View Item