Sidang Tugas Akhir

Tri Susanto
g54130074

Cycle Hamilton Pada Graf Lengkap, Graf Regular, dan Graf 2-connected 4-regular

Suatu graf disebut graf Hamilton apabila graf tersebut memuat cycle Hamilton, yaitu cycle yang melewati setiap vertex tepat satu kali. Menentukan keberadaan cycle Hamilton pada suatu graf dapat menggunakan syarat cukup yang berupa teorema-teorema yang telah diperkenalkan sejak tahun 1950-an. Terdapat empat pembuktian teorema yang dibahas dalam karya ilmiah ini. Teorema pertama membuktikan bahwa graf lengkap memuat cycle Hamilton. Teorema kedua membuktikan bahwa suatu graf sederhana memuat cycle Hanilton apabila penjumlahan derajat vertex yang tidak saling adjacent lebih besar dari order graf tersebut. Teorema ketiga membuktikan bahwa suatu graf sederhana memiliki cycle Hamilton apabila δ(G)≥n/2. Teorema keempat membuktikan suatu graf sederhana r-regular dengan banyaknya vertex 2r+1 memuat cycle Hamilton dengan r bilangan genap positif. Selanjutnya teorema-teorema tersebut digunakan untuk menentukan keberadaan cycle Hamilton pada graf sederhana 2-connected 4-regular berorder kurang dari 10.