Desain Dan Analisis Algoritma Penentuan Sifat Isomorfisme Pada Grid Graph: Studi Kasus E-OLYMP 9067 Ancient Greek Isomorphism.

Pasya, Devi Hainun (2022) Desain Dan Analisis Algoritma Penentuan Sifat Isomorfisme Pada Grid Graph: Studi Kasus E-OLYMP 9067 Ancient Greek Isomorphism. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840000014-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (4MB)

Abstract

Isomorfisme merupakan teori graf yang menjelaskan mengenai bagaimana dua buah graf memiliki bentuk yang sama namun dengan penamaan vertex dan edge yang berbeda. Telah banyak algoritma terdahulu yang diciptakan untuk menyelesaikan permasalahan isomorfisme antara graf secara umum, beberapa di antaranya adalah VF2 dan Schmidt & Druffel fast backtracking. Namun permasalahan yang diselesaikan dalam tugas akhir ini adalah spesifik pada penentuan sifat isomorfisme pada graf berbentuk grid yang telah disederhanakan ke dalam bentuk soal pada situs online judge yaitu E-Olymp berjudul “9067 Ancient Greek isomorphism”. Secara umum, persoalan yang telah diselesaikan di sini adalah bagaimana menentukan sama atau tidaknya (isomorfis) dua buah graf berdasarkan rincian kedua graf yang diberikan. Metode penyelesaian yang dipilih adalah penggunaan properti-properti graf grid yang digunakan untuk membangun sebuah algoritma pengecekan sifat isomorfisme. Algoritma pengecekan tersebut diimplementasikan dengan menggunakan bahasa pemrograman C++. Kemudian dilakukan uji kebenaran pada hasil implementasi algoritma pengecekan. Dari uji coba yang telah dilakukan, didapatkan kesimpulan bahwa algoritma yang dirancang telah sesuai dengan permasalahan yang dibahas dan mendapatkan verdict “Accepted” pada situs online judge dengan rata-rata waktu penyelesaian 286,7 ms dan rata-rata memori 50969,6 kB.
==================================================================================================================================
Isomorphism is a graph theory that explains how two graphs have the same shape but with different orders of vertices and edges. Many previous algorithms have been developed to solve the isomorphism problem between graphs in general, some of them are VF2 and Schmidt & Druffel fast backtracking. However, the problem discussed in this undergraduate thesis is specific to the determination of isomorphism property in a grid-shaped graph that has been simplified into a form of the problem on an online judge site, namely, E Olymp entitled “9067 Ancient Greek isomorphism”. In general, the problem that has been solved in here is how to determine whether or not two graphs are isomorphic based on the details given of the two graphs. The method chosen for the solution is the usage of grid graph properties that are used to build an isomorphism-checking algorithm.The isomorphism-checking algorithm is implemented by using the C++ programming language. Then a correctness test has been conducted on the result of the implementation of the isomorphism-checking algorithm. From the experiments that have been carried out, it can be concluded that the algorithm designed was following the problem discussed and received an “Accepted” verdict on the online judge site with an average completion time of 286,7 ms and 50969,6 kB memory.

Item Type:	Thesis (Other)
Additional Information:	RSIf 004.015 1 Pas d-1 2022
Uncontrolled Keywords:	graf, graf grid, isomorfisme, properti graf. graph, graph properties, grid graph, isomorphism.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Mr. Marsudiyana -
Date Deposited:	25 May 2026 03:07
Last Modified:	25 May 2026 03:07
URI:	http://repository.its.ac.id/id/eprint/133383

Actions (login required)

View Item