seminar matematika ( teori graph)

Menentukan Order dan Ukuran graf langkah Kuda pada papan

catur berukuran n x n .

M. Noviarsyah Dp – NIM 06111408003

Program Studi Pendidikan Matematika

Universitas Sriwijaya

Jl. Ogan Bukit Besar Palembang

E-mail : [email protected]

ABSTRAK

Permainan Catur adalah permainan pikiran yang dimainkan oleh dua orang. Pecatur adalah orang yang memainkan catur, dimasyarakat terdapat permainan yang hampir sama dengan permainan catur tetapi permainan tersebut hanya menggunakan sebuah kuda dan beberapa bidak/prajurit yaitu catur kuda. Catur Kuda merupakan permainan sederhana yang penuh dengan strategi langkah yang tepat untuk menyelesaikannya, catur kuda adalah salah satu buah catur yang memiliki langkah yang menarik dibandingkan dengan buah catur lainnya yaitu membentuk huruf (L). Pada pola pergerakan kuda untuk menentukan order dan ukuran menggunakan graf. Macam-macam graf yang digunakan adalah graf lengkap,graf lingkaran,graf teratur, sehingga dapat menentukan order dan ukuran graf langkah kuda pada papan catur berukuran n x n.

Kata Kunci : Permainan Catur Kuda, Graf, Graf lengkap, Graf lingkaran, dan Graf

teratur.

A. PENDAHULUAN

Konsep graf Eulerian yang diawali oleh karya Euler pada problem Jembatan Konigsberg

(1736) merupakan awal dari lahirnya teori graf. Meskipun umurnya yang relatif muda, teori

graf sebagai cabang dari matematika diskrit telah berkembang sangat pesat akhir-akhir ini,

baik dalam pengembangan teori maupun aplikasi di berbagai bidang. Di sadari atau tidak,

banyak aplikasi teori graf dalam kehidupan kita. Banyak sekali struktur yang bisa

direpresentasikan dengan graf dan banyak masalah yang bisa diselesaikan dengan bantuan

graf, bahkan dalam permainan catur pun ternyata ada aplikasi teori graf, tetapi sekarang akan

membuktikan bahwa aplikasi graf diterapkan pada permainan catur kuda.

mailto:[email protected]

Catur kuda adalah Turunan dari permainan Catur pada umum nya, pada permainan catur

biasa terdapat lebih dari 32 prajurit/pionnya, pada catur kuda hanya terdapat 2 buah pion,

yakni kuda dipihak Hitam dan kuda dipihak Putih. Yang paling membedakan catur kuda

dengan catur biasa selain Jumlah prajuritnya/pionnya adalah hasil atau kondisi akhir dalam

permainan. Pada catur biasa permainan akan berakhir ketika raja tim Hitam terbunuh oleh

Tim Putih maka pemenangnya Tim Hitam, sedangkan pada catur kuda permainan akan

berakhir ketika salah satu kuda tidak dapat melangkah lagi ( pada catur kuda, bidang yang

telah ditempati tidak boleh ditempati lagi oleh kedua belah pihak. ). Pada permainan Catur

kuda bidak/prajurit yang digunakan ialah Kuda sama seperti judul permainan nya

dikarenakan prajurit kuda langkah nya membentuk huruf ( L ), dan hanya satu kuda yang

digunakan pada permainan ini.

Secara informal, suatu graf adalah himpunan benda-benda yang disebut verteks (atau node)

yang terhubung oleh sisi (atau edge atau arc). Biasanya graf digambarkan sebagai kumpulan

titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).

Pada makalah ini difokuskan pada menentukan order dan size graf langkah kuda pada papan

berukuran n x n. Permasalahan yang diangkat pun dikhususkan pada bagaimana menentukan

order dan size graf pada langkah kuda.

B. MATERI PENDUKUNG

1. Graf

2.1.1 Definisi Graf

Definisi 1

Suatu graf G adalah suatu pasangan himpunan (V, E) ditulis dengan notasi G = (V, E),

dalam hal ini V adalah himpunan tak kosong dari simpul-simpul ( vertices atau node ) dan E

adalah Himpunan sisi ( edge atau arcs )yang menghubungkan sepasang simpul.

(Munir, Rinaldy ; 2005 ; 356)

Definisi 2

Banyaknya simpul ( anggota V ) disebut Order Graf G yang dilambangkan dengan

p(G), Sedangkan banyaknya ruas ( anggota E ) disebut ukuran Graf G dan dilambangkan

dengan q(G).

2.2 Macam-Macam Graf

2.2.1 Graf Lengkap (komplit)

Sebuah graf G adalah graf sederhana yang setiap simpulnya mempunyai

sisi ke semua simpul lainnya. (Munir, Rinald ; 2005 ; 377).

.2.2.2 Graf Lingkaran

Graf Lingkaran adalah Graf terhubung yang setiap simpulnya berderajat

dua. Graf Lingkaran dengan n titik dilambangkan dengan Cn.

(Munir, Rinald ; 2005 ; 377).

2.2.3 Graf Teratur ( Regular Graphs )

Graf teratur adalah graf yang setiap simpulnya mempunyai derajat yang

sama. Apabila Derajat setiap simpul adalah r, maka graf tersebut disebut sebagai

graf teratur derajat r. (Munir, Rinald ; 2005 ; 378).

C. Materi Pokok.

I. Menentukan Banyaknya Order dan ukuran dari Graf Langkah Kuda pada

Papan Catur Berukuran n x n

1. Papan Catur ukuran 3 x 3

Pada papan catur berukuran 3 x 3 dapat digambarkan sebagai berikut :

a b c

1

2

3

Langkah kuda yang terjadi pada papan catur ukuran 3 x 3 dapat

digambarkan dalam bentuk graf G sebagai berikut:

V ( G ) = { a1, a2, a3, b1, b2, b3, c1, c2, c3 }, jadi p(G) = 9

E ( G ) = {( a1, b3), (a1, c2), (a2, c2), (a2, c3), (a3, b1), (a3, c2), (b1, c3), (b3, c1)}, jadi

q(G) = 8

Bahwa p(G) = banyak nya titik yang ada di papan catur 3x3, sedangkan untuk

q(G) = adalah Banyaknya langkah kuda dalam menghabisi pion-pionnya tetapi

banyaknya langkah tersebut Minimal langkah untuk menghabisi Pion yang ada

atau tersedia.


Untuk papan catur berukuran 4 x 4 dapat digambarkan sebagai berikut :

Langkah kuda yang mungkin terjadi pada papan catur ukuran 4 x 4 dapat


V ( G ) = { a1, a2, a3, a4, b1, b2, b3, b4, c1, c2, c3, c4 }, jadi p(G) = 16

E ( G ) = {( a1, b3), (a1, c2), (a2, c1), (a2, c3), (a2, b4), (a3, b1), (a3, c2), (a4, c3),

(a4, b2), (a3, c4), (b1, d2), (b1, c3), (b2, d1), (b2, d3), (b2, c4), (b2, d1),

( b2, d3),( b3, c1),( b3, d2),( b3, d4),( b4, c2),( b4, d3),( c1, d3),( c2, d4),

( c3, d1),( c4, d2)}. Jadi q(G) = 24







V(G) = { a1, a2, a3, . . . , a8, b1, b2, b3, . . . , b8, c1, c2, c3, . . . , c8, d1, d2, d3, . . . ,

d8, e1, e2, e3, . . . , e8, f1, f2, f3, . . . , f8, g1, g2, g3, . . . , g8, h1, h2, h3, . . . , h8.}.

Jadi p(G) = 64

Berdasarkan contoh papan catur n x n di atas maka didapat dibuat tabel sebagai berikut:

No Ukuran P Q1 3 x 3 9 = 3 x 3 = 32 8 = 4 x 1 x22 4 x 4 16 = 4 x 4 = 42 24 = 4 x 2 x33 5 x 5 25 = 5 x 5 = 52 48 = 4 x 3 x44 6 x 6 36 = 6 x 6 = 62 80 = 4 x 4 x55 7 x 7 49 = 7 x 7 = 72 120 = 4 x 5 x66 8 x 8 64 = 8 x 8 = 82 168 = 4 x 6 x7::::

::::

::::

::::

i n x n n2 4 ( n – 2 )(n – 1 )

Maka Terlihat pola bahwa p = n2 dan q = 4(n-2) (n-1). Untuk n bilangan asli, dan

Menghasilkan p = n2 dan q = 4(n-2) (n-1), syarat untuk n ≥ 3 ( Nafiah:2009:47 )

Teorema :

Untuk papan catur n x n, maka graf langkah kuda mempunyai order

p = n2 dan size q = 4(n-2) (n-1), untuk n ≥ 3

Bukti :

Pada papn catur berukuran n x n terdapat sebanyak n2 kotak. Karena Pada

setiap Kotak mewakili titik, maka graf langkah kuda akan mempunyai sebanyak

n2 titik. Jadi graf langkah kuda pada papn catur n x n mempunyai order p = n2.

Untuk membuktikan Size, akan dilakukan dengan induksi matematika

1. Untuk n = 3 diperoleh graf langkah kuda sebagai berikut:

Graf tersebut mempunyai size 8 = 4·1·2. Jadi benar untuk n = 3.

2. Akan ditunjukkan jika untuk n = k ≥ 3 benar, maka untuk n = k + 1 juga

benar.

Asumsikan benar untuk n = k ≥ 3, artinya untuk papan catur berukuran k x k,

maka banyak sisinya adalah 4(k – 2)(k – 1). Papan catur (k + 1) x (k + 1)

diperoleh dari papan catur k x k dengan menambah masing-masing 1 Baris kotak

pada sisi horizontal dan 1 Baris kotak pada vertikal, seperti gambar berikut:

Sesuai asumsi sebelumnya, banyaknya sisi pada papan catur k x k sebanyak 4(k –

2)(k – 1). Pada papan catur (k + 1) x (k + 1), ada tambahan sisi yang dapat

dihitung sebagai berikut:

Untuk titik ai, i = 1, 2, . . . , k + 1 , maka diperoleh :

Pada a1 menambah 2 sisi

Pada a2 menambah 3 sisi

Pada a3 sampai ak-1 menambah 4 sisi [ sebanyak (k – 3) titik ]

Pada ak menambah 3 sisi

Pada ak+1 menambah 2 sisi

Karena semua sisi tersebut berbeda, maka ada tambahan sebanyak

4 x (k – 3 ) + 10 sisi.

Dengan cara yang sama. Untuk titik bi , 1 ≤ i ≤ k + 1 diperoleh tambahan

sebanyak 4 x ( k – 3 ) + 10. Karena titik ak+1 dan bk+1 sama, maka total sisi harus

dikurangi 2. Demikian juga sisi akbk-1 dan ak-1bk dihitung dua kali, jadi juga

dikurangi 2. Jadi sisi tambahan harus dikurangi 4, Jadi terdapat tambahan sisi

sebanyak :

((4(k – 3) + 10) + (4(k – 3) + 10)) – 4.

= [4(k – 3) + 4 . 2 + 2 ] + [4(k – 3 ) + 4 . 2 + 2 ] – 4

= [4(k – 1) + 2 ] + [4(k – 1 ) + 2 ] – 4

= 2 . 4 (k – 1)

Jadi Total sisi papan graf langkah kuda pada papn catur ( k + 1 ) x ( k + 1 ) adalah:

4(k – 2) ( k – 1 ) + 2 . 4 (k – 1)

= 4(k – 1 )[(k-2) + 2) ]

= 4(k – 1) (k )

= 4 ( ( K + 1) – 2) ((k + 1) – 1). Untuk Mengubah bentuk ke bentuk persamaan

Q.

Terbukti untuk papan catur ( k + 1) x (k + 1) mempunyai size sebesar :

Q = 4((k + 1) – 2)(( k + 1) – 1)

Sesuai induksi matematika dapat disimpulkan bahwa untuk papn catur n x n, maka

graf langkah kuda mempunyai size :

Q = 4(n – 2)(n – 1), n ≥ 3

D. Kesimpulan Teori Graf banyak memiliki aplikasi dalam kehidupan sehari-hari, salah satunya

yang sering kita jumpai dan sering kita mainkan ialah permainan catur, catur kuda

permainan yang membuat seorang pemainnya berfikir bagaimana caranya untuk

menghabiskan semua bidak/prajurit yang disediakan pada papan catur berukuran n

x n, maka dengan aplikasi teori graf ini kita dapat menentukan order dan ukuran

graf langkah kuda pada papn catur berukuran n x n. Dan yang didapatkan dalam

proses pencarian order dan Ukuran tersebut bahwa Order / titik (P) = n2 dan

Ukuran (Q) = 4 (n-2) (n-1) dengan syarat untuk n ≥ 3.

E. DAFTAR PUSTAKA

Munir, Rinaldi. 2005. Matematika Diskrit. Bandung: Informatika.

Lipschutz, Ph.D. , Seymour and Lars Lipson, Marc. 2002.Matematika

Diskrit.Singapore:Selemba Teknika.

Simangunsong,Sahat Nicholas., 2011, Aplikasi Graf Dalam Permainan

Catur. (http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2010-

2011/Makalah2010/MakalahStrukdis2010-029.pdf, diakses tanggal 30

January 2014 )

Prawira,Yudha Wastu.,2011, Penggunaan Graf dalam sistem Drainase

Perkotaan untuk Meminimalisasi Masalah banjir.(

http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2010-2011/

Makalah2010/MakalahStrukdis2010-078.pdf, diakses tanggal 13 Maret

2014 )

Nafiah, Dhurriyatun., 2009, Menentukan order dan size Graf langkah

kuda pada papan catur berukuran n x n. (

http://lib.uin-malang.ac.id/files/thesis/fullchapter/03510013.pdf, diakses

tanggal 30 January 2014 )

http://lib.uin-malang.ac.id/files/thesis/fullchapter/03510013.pdf

http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2010-2011/Makalah2010/MakalahStrukdis2010-078.pdf




LAMPIRAN

Revisi Makalah Seminar Matematika

Nama : M.Noviarsyah Dp

Nim : 06111408003

Tanggal Seminar :09 April 2014

NoNama Dosen

PengujiSaran atau Keritik Tindak Lanjut Keterangan

1. Dr. Somakim

M.Sc

1. Seharusnya untuk

menghabiskan Pion,

satu buah kuda

diajalnkan tanpa

kembali pada posisi

awal.

2. P(G) dan Q(G) itu

apakah,

1.Sudah di jawab ketika

presentasi berlangsung, dan

sudah di jelaskan secara

seksama bahwa dgn

menggunakan Graf untuk

mencari bnyaknya langkah

kuda.

2. Direvis dengan mencari

informasi apa itu p(G) dan

Q(G) dan yang mendapatkan

informasi bahwa p(G) dan

q(G) adalah Minimal Langkah

kuda dalam menghabisi Pion-

pion di papan catur.

Sudah

direvisi dan

sudah

dijelaskan

saat seminar

2. Dr. Yusuf

Hartono, M.Sc

Pada Judul Makalah

Seharusnya Langkah

Kuda menggunakan

Graf atau Graf

langkah Kuda.

Sudah Dijelaskan ketika

presentasi berlangsung, bahwa

untuk menentukan banyaknya

langkah kuda tersebut

menggunakan teori graf.

Sudah

direvisi dan

sudah

dijelaskan

saat seminar

seminar matematika ( teori graph)

Education