Sijabat, Daniel Bintar (2017) Desain dan Analisis Algoritma Komputasi Cycle pada Turnamen Berbasis Strongly Connected dan Vertex Pancyclic: Studi Kasus Persoalan SPOJ Klasik Cyclerun - Riding In Cycles. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5113100145-Undergraduate_Thesis.pdf - Published Version Download (2MB) | Preview |
Abstract
Salah satu permasalahan pada turnamen yaitu mendeteksi
apakah terdapat cycle dengan jumlah verteks t, untuk setiap t
pada range
3
�
t
�
N
, dengan N adalah total vertex yang ada,
dan terdapat satu verteks yang diinginkan untuk ada pada semua
cycle tersebut. Jika semua cycle yang diharapkan ada,
permasalahannya lainnya adalah bagaimana mendapatkan
semua cycle tersebut. Salah satu solusi untuk mendapatkan
semua cycle tersebut bisa dilakukan dengan melakukan
traversing ke semua kemungkinan cycle, namun pendekatan
tersebut tentunya tidak efisien.
Pada Tugas Akhir ini dirancang penyelesaian permasalahan
di atas dengan melihat beberapa kondisi apakah suatu turnamen
merupakan strongly connected, karena jika memiliki cycle
dengan memakai semua verteks pada graf, pasti strongly
connected. Jika suatu graf tidak strongly connected, pasti tidak
memiliki cycle dengan
N
verteks. Spesialnya dari turnamen
adalah jika turnamen merupakan strongly connected, pasti
vertex pancyclic. Vertex pancyclic berarti tiap vertex memiliki
cycle dengan jumlah vertex t, untuk setiap t pada range 3
�
t
�
N
.
Hasil dari Tugas Akhir ini telah berhasil menyelesaikan
permasalahan di atas dengan cukup efisien dengan kompleksitas
waktu
O
(
N
2
)
.
==================================================================
One of tournament problem is to check if there are exist
cycles with the number of vertices t, for each t in range
3
�
t
�
N
, with N is the total vertices available, and there is one
desired vertex to be exist on all cycle. If cycles are exist, another
problem is how to get it. One of the solution is traversing to all
cycle possibilities, but this approach is certainly not efficient.
This Final Project is designed to solve the above problem by
looking at some conditions whether a tournament is strongly
connected or not, because if graph have cycle which using all
vertices in the graph, it must be strongly connected. If a graph is
not strongly connected, it certainly does not have cycle with
N
vertices. The special of the tournament is if it is strongly
connected, it definitely is vertex pancyclic. Vertex pancyclic
means each vertex has cycle with the number of vertices t, for
every t in range
3
�
t
�
N
.
The result of this Final Project has successfully solved the
above problem quite efficiently with the time complexity of
O
(
N
2
)
.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | turnamen, strongly connected, vertex pancyclic |
| Subjects: | T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.546 Computer algorithms |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Daniel Bintar . |
| Date Deposited: | 01 Feb 2018 07:55 |
| Last Modified: | 08 Mar 2019 03:53 |
| URI: | http://repository.its.ac.id/id/eprint/45910 |
Actions (login required)
 |
View Item |