1

SIKLUS HAMILTON DALAM LANGKAH KE -K PADA PERMAINAN

TRADISIONAL CONGKLAK

Oleh: Rukmono Budi Utomo (J2A 009 004)

Program Studi Matematika

Fakultas Sains dan Matematika Universitas Diponegoro, Semarang.

ABSTRAK

Paper ini mencoba membahas mengenai adanya Siklus Hamilton pada langkah ke-K

dalam permainan tradisional Congklak. Dimulai dengan mendeskripsikan mengenai apa

dan bagaiman cara memainkan permainan ini, selanjutnya ditentukan langkah perjalanan

yang tepat (langkah ke- K) untuk menghasilkan siklus Hamilton. Penentuan langkah ke-K

ini tidak dapat ditentukan secara sembarangan, namun harus melalui perhitungan cermat

dan trial and eror agar pengambilan biji congklak pada starting pole tepat habis (kembali)

pada starting pole tersebut dalam sekali putaran atau siklus.

Kata kunci: Permainan Congklak, Graf, Sklus Hamilton

PENDAHULUAN

Congklak adalah nama sebuah permainan tradisional yang cukup terkenal di

Indonesia. Permainan ini menggunakan papan dengan 12 lubang dan 2 lubang induk yang

ukurannya lebih besar serta biji congklak yang berjumlah 98 buah. Satu lubang induk

terletak pada ujung papan dan lubang induk lainnya terletak di ujung lainnya. Di antara

kedua lubang induk tersebut terdapat 2 baris yang tiap barisnya berisi 6 lubang yang

menjadi kepunyaan masing-masing pemain. Di Malaysia permainan ini juga dikenal

dengan nama congkak, namun di beberapa daerah di Indonesia, seperti di jawa, lampung

dan Sulawesi, permainan Ini lebih dikenal dengan nama dakon, dhakon atau dhakonan,

2

dentuman lamban dan Mokaotan. Dalam bahasa Inggris, permainan ini disebut Mancala[1]

.

Berikut adalah gambar permainan congklak

Gambar 1 : Congklak Gambar 2: 98 Buah biji congklak

PERMAINAN CONGKLAK

Secara umum, tiap-tiap daerah, dimanapun itu, baik di Indonesia maupun diluar

negeri dalam memainkan permainan congklak ini menggunakan aturan yang sama. Biji

congklak yang berjumlah 98 buah dibagikan secara merata ke 14 lubang papan, sehingga

setiap lubang tepat berisi 7 buah biji. Selanjutnya ditentukan mana pemain yang terlebih

dahulu untuk memulai permainan. Dalam bahasan paper ini dimisalkan pemain

digolongkan sebagai pemain A dan pemain B. Pemain A dan B seperti yang telah

diutarakan diatas masing-masing memiliki 6 buah lubang kecil dan 1 buah lubang induk.

Setiap pemain berhak memilih lubang yang berisi biji congklak untuk selanjutnya biji-biji

congklak tersebut disebarkan ke setiap lubang pada papan congklak kecuali lubang induk

milik lawan. Permainan ini terus berlangsung secara berganian apabila biji yang diputarkan

atau dijalankan tidak dapat diteruskan. Gambar dibawah menunjukan siklus perputaran

permainan congklak

Gambar 3: Mekanisme permainan congklak

B2 B3 B4B1 B5

A

A2 A3 A4 A5 A6

B

A1

B6

A RUN

B RUN

B RUN

A RUN

3

ISTILAH-ISTILAH PERMAINAN CONGKLAK DALAM PEMBAHASAN

Istilah-istilah disini merupakan ungkapan penulis untuk merepresentasikan keadaan-

keadaan atau kejadian yang umum terjadi dalam permainan congklak, misalnya :

a. Satu Jalan : Merupakan ungkapan yang digunakan untuk melukiskan proses

pengambilan 1 kali biji-biji congklak dalam suatu lubang dan

dilakukan perjalanan untuk menyebarkan tiap-tiap biji ke masing-

masing lubang pada papan congklak (kecuali lubang induk lawan)

sampai biji-biji tersebut habis. Misal: Pengambilan 7 buah biji

congklak pada lubang A4, kemudia habis pada lubang ke B3

b. Dua Jalan : Ungkapan ini identik untuk ungkapan-ungkapan lainnya seperti tiga

jalan, empat jalan dst yang menyatakan proses lanjutan dari satu

jalan dengan syarat jatunya lubang tempat biji terakhir mendarat ada

sekurang-kurangnya 1 biji yang mendiami sebelumnya.

c. Iterasi : Istilah ini digunakan untuk menggambarkan penentuan lubang baru

untuk mengambil biji-biji congklak baru apabila dalan perjalanan

penyebaran biji congklak, biji –biji tersebut habis pada lubang induk.

GRAF

Graf adalah kumpulan simpul / vertex yang dihubungkan satu sama lain melalui

sisi/ busur (edges)[2].

Simpul adalah objek sembarang yang dapat dijabarkan. Busur adalah

relasi yang menghubungkan antara objek-objek tersebut, sehingga objek-objek tersebut

mempunyai makna. Secara umum, sebuah graf dapat dirumuskan dengan G adalah Graph

sedangkan V adalah simpul dan E adalah busur. Berdasarkan arah busurnya, graph dibagi

menjadi dua, yaitu graph berarah / directed graph dan graph tidak berarah / undirected

graph. Graf berarah adalah graph yang setiap busurnya mempunyai arah.

<V1, V2> ≠ <V2, V1>

Sedangkan untuk yang tidak berarah

<V1, V2> = <V2, V1>

4

TERMINOLOGI DASAR GRAF [2]

Berikut akan diberikan beberapa terminologi dasar teori Graf

A. Bertetangga (Adjacent)

Dua buah simpul pada graf tak berarah G dikatakan bertetangga bila keduanya

terhubung langsung dengan sebuah sisi.

B. Bersisian (Incident)

Suatu sisi e dikatakan bersisian dengan simpul 𝑉𝑖 dan 𝑉𝑗 jika e = (𝑉𝑖 , 𝑉𝑗 ) atau e

menghubungkan simpul 𝑉𝑖 dan 𝑉𝑗

C. Derajat (Degree) Suatu simpul pada graf tak – berarah dikatakan berderajat n jika

jumlah sisi yang bersisian dengan simpul tersebut berjumlah n. Hal ini dilambangkan

dengan d (v). Derajat maksimum simpul yang terdapat pada suatu graf dilambangkan

dengan B(G).

D. Lintasan (Path)

Lintasan adalah barisan berselang – seling simpul–simpul dan sisi–sisi yang berbentuk

𝑉0, 𝑒1 , 𝑉1, 𝑒2,..., 𝑉𝑛−1, 𝑒𝑛 , 𝑉𝑛 yang menghubungkan simpul awal 𝑉0 dan simpul tujuan

vn. Untuk graf sederhana, biasanya lintasan ditulis sebagai barisan simpul– simpulnya

saja, yaitu 𝑉0, 𝑉1, 𝑉2.., 𝑉𝑛

JENIS GRAF

Graf dapat dikelompokkan menjadi beberapa kategori (jenis) bergantung pada sudut

pandang pengelompokkannya. Pengelompokkan graf dapat dipandang berdasarkan ada

tidaknya sisi ganda atau sisi kalang, berdasarkan jumlah simpul, atau berdasarkan orientasi

arah pada sisi. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka

secara umum graf dapat digolongkan menjadi 2 jenis:

1. Graf sederhana Graf sederhana merupakan graf yang tidak mengandung gelang

maupun sisi ganda

2. Graf tak-sederhana Graf tak-sederhana merupakan graf yang mengandung sisi

ganda atau gelang.

5

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:

1. Graf tak-berarah Graf tak-berarah merupakan graf yang sisinya tidak

mempunyai orientasi arah. Pada graf tak berarah, urutan pasangan simpul yang

dihubungkan oleh sisi tidak diperhatikan. Jadi (vj,vk) dan (vk,vj) adalah sisi

yang sama.

2. Graf berarah Graf berarah merupakan graf yang setiap sisinya diberikan

orientasi arah. Jadi (vj,vk) dan (vk,vj) merupakan dua sisi yang berbeda.

LINTASAN DAN SIRKUIT HAMILTON

Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graph tepat

satu kali

Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graph tepat satu

kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.

Graph yang memiliki sirkuit Hamilton dinamakan graph Hamilton, sedangkan

graph yang hanya memiliki lintasan Hamilton disebut graph semi-Hamilton

TEOREMA

Syarat cukup (bukan syarat perlu) agar graph sederhana G dengan n ( 3) buah

simpul adalah graph Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu,

d(v) n/2 untuk setiap simpul v di G).

Setiap graph lengkap adalah graph Hamilton

Di dalam graph lengkap G dengan n buah simpul (n 3), terdapat (n - 1)!/2 buah

sirkuit Hamilton

Di dalam graph lengkap G dengan n buah simpul (n 3 dan n ganjil), terdapat (n -

1) /2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n

genap dan n 4, maka di dalam G terdapat (n - 2)/2 buah sirkuit Hamilton yang

saling lepas.

6

MENCARI LANGKAH KE-K PADA PERMAINAN CONGKLAK UNTUK

MENDAPATKAN GRAF HAMILTON

Misal pemain kita notasikan dengan pemain A dan B. Dimana setiap pemain telah

mendapatkan jumlah biji yang sama untuk setiap lubang miliknya ( berjumlah 6 lubang).

Kita anggap pemain A adalah pemain yang terlebih dahulu melangkah, sehingga ia bebas

memilih lubang manapun yang menjadi miliknya untuk selanjutnya menjalankan biji yang

terdapat didalam setiap lubang. Kita beri notasi setiap lubang milik A dengan nama A1, A2,

A3, A4, A5 dan A6.

Gambar 4. Dua orang pemain congklak

Karena pemain A diberi kesempatan untuk melangkah terlebih dahulu maka ia

bebas memilih lubang mana (miliknya sendiri) yang berisi 7 buah biji congklak yang akan

dipilihnya untuk dijalankan ia memiliki kesempatan memilih lubang A1, A2, …., A6.

Karena pembahasan disini adalah menentukan terjadinya graf Hamilton, maka andaikan ia

memilih lubang A4. Lubang A4 yang berisi 7 buah biji ia ambil semua dan mulai

diputarkannya (dijatuhkan) biji dari lubang A5 ke masing-masing lubang dalam papan

congklak, kecuali lubang induk lawan (berada di sebelah kanannya). Perhitungan

perputaran biji yang ia mulai dari lubang A4 jika habis atau selesai di lubang besar

miliknya dianggap sebagai suatu iterasi untuk mewujudkan graf Hamilton. Perhitungannya

disajikan seperti dibawah ini.

B2 B3 B4B1 B5

A

A2 A3 A4 A5 A6

B

A1

B6

PEMAIN A

PEMAIN B

A RUN

B RUN

B RUN

A RUN

7

PEMAIN B

PEMAIN A

Gambar 5: Langkah-langkah dalam menemukan siklusHamilton

Keterangan:

: Batas antara pemain A dan B

Dengan bermacam-macam warna : Jalan atau langkah

Mula-mula pemain A mengambil Biji congklak pada lubang A4 ( yang ditunjukkan oleh

tanda “ I” pada batas pemain). Kemudian biji-biji tersebut diputarkan disebarkan ke

masing-masing lubang lainnya. Biji congklak yang ia ambil pada lunbang A4 habis atau

selesai disebarkan pada kotak B3. Akibatnya kotak B3 yang semula memiliki 7 biji, kini

menjadi 8 buah biji congklak akibat tambahan satu biji oleh pengambilan biji pada lubang

A4 tersebut. Tambahan satu biji ini juga berlaku pada lubang-lubang yang dilewati oleh

pengambilan biji pada lubang A4 tersbut. Pengambilan biji pada lubang A4 dan disebarkan

hingga habis pada kotak B3 dinamakan satu jalan.

3

1 2 2 3

0 1 1 13 2 13

12 0 0 12 1 12

11 11 2 11 0 11

10 10 1 10 10 10

9 9 0 9 9 9

8 8 8 8 8 8

7 7 7 7 7 7

∑=15 II III I

7 7 7 7 7 7

8 8 8 0 8 8

9 9 9 1 9 9

10 0 10 2 10 0

11 1 11 3 11 1

12 2 12 4 12 2

13 3 13 5 13 3

14 0 0 6 4

15 1 1

2

Jumlah biji Kotak

Induk pemain A

8

Karena lubang B3 menjadi lubang terakhir yang menjadi tempat mendarat biji

terakhir, maka lubang B3 menjadi lubang baru untuk semua biji yang ada didalamnya

diputarkan seperti langkah satu jalan sebelumnya. Delapan buah biji yang diambil dari

lubang B3 habis pada A2 atau dengan kata lain biji terakhir tepat habis pada lubang A2.

Perjananan pengambilan biji pada lubang B3 hingga biji habis disebar pada lubang A2

dinamakan dua jalan. Mekanisme ini terus berlanjut hingga ada kondisi dimana biji yang

disebarkan jatuh pada lubang induk yakni pada jalan ke 7. Pada jalan ke 6, pengmbilan biji

dilakukan pada lubang B5 dan biji habis pada lubang B2. Akibatnya biji pada lubang B2

yang semula berjumlah 10, kini akibat mendapat tambahan satu, menjadi 11 biji, dan

lubang B2 menjadi lubang baru untuk melanjutkan perjalanan penyebaran biji ( jalan 7).

Karena Biji dari lubang B2 habis pada lubang induk, maka terjadilah iterasi

pertama. Selanjutnya dipilih sembarang lubang baru yang dikehendaki. Misal, dipilih

lubang A2. Lubang A2 memiliki 3 buah biji. Kemudian disebarkan seperti mekanisme

sebelumnya, dan biji habis pada lubang B1 (Jalan 8). Karena lubang B1 menjadi lubang

terakhir pemberhentian biji, maka luabang B1 menjadi lubang lanjutan untuk penyebaran

biji yang berada didalamnya. Perhatikan perjalanan penyebaran Biji dari lubang B1 ini. Biji

yang diambil pada lubang B1 ternyata habis tepat pada lubang induk, sehingga timbullah

iterasi kedua. Dalam iterasi kedua ini, pengambilan biji pada lubang A3 mengakibatkan biji

jatuh atau habis pada lubang yang sama, sehinggga dapat dikatakan Siklus Hamilton terjadi

disini. Lihat ilustrasinya:

Gambar 6 : Siklus Hamilton Pada jalan ke 10, iterasi ke dua

B2 B3 B4B1 B5 B6

A0

A2 A3 A4A1 A5 A6

1212

8765

4

9

1113

3

10

9

Dalam Gambar dapat dilihat bahwa lubang yang baru, yakni lubang A3 adalah lubang

diman terjadi siklus Hamilton. Pada lubang ini, diambil 13 buah biji dan dijalankan atau

disebarkan seperti langkah-langkah atau mekanisme penjalanan biji sebelumnya. Biji

terakhir dari lubang A3 tepat habis pada lubang yang sama, sehingga jika direpresentasikan

dengan graf, maka terjadi Siklus Hamiton.

SARAN

Dalam hal pencarian Siklus Hamilton, sangatlah baik jika ditemukan rumus matematika

yang dapat mempresiksi jalan atau langkah tertentu yang menghasilkan siklus Hamilton.

REFERENSI

[1] Wikipedia, congklak

[2] Munir, Rinaldi, Diktat Kuliah IF 2153, Matematika Diskrit, Edisi Keempat, Program

Studi Teknik Informatika, STEI, ITB, 2006.

PERNYATAAN

Saya, Rukmono Budi Utomo

NIM: J2A 009 004

Menyatakan Bahwa Paper ” SIKLUS HAMILTON DALAM LANGKAH KE -K PADA

PERMAINAN TRADISIONAL CONGKLAK” adalah benar merupakan karya pribadi dan

bukan merupakan hasil jiplakan atau Plagiasi