1. LATAR BELAKANG MASALAH

Terdapat berbagai macam permasalahan dalam kehidupan nyata yang dapat dimodelkan dalam bentuk graph. Contohnya, pada permasalahan menentukan pelamar kerja yang sesuai dengan bidang keahliannya. Tetapi, tidak semua permasalahan dapat dimodelkan dengan graph misalnya pada pembuatan peta jalan satu arah. Untuk itu, digunakan digraph (directed graph atau graph berarah). Digraph tidak hanya digunakan pada masalah transportasi saja, tetapi dapat juga digunakan pada pemodelan Turnamen Robin. Dalam pertandingan ini, setiap dua tim yang bertanding dalam turnamen tersebut, hanya boleh bertanding satu kali dan tidak boleh seri. Permasalahan Turnamen Robin ini dapat dimodelkan dengan salah satu kelas pada digraph yang disebut dengan tournament. Di mana setiap vertex v1, v2, ..., vn dalam digraph dapat direpresentasikan sebagai tim yang bertanding. Sedangkan, setiap arc (v1,v2) direpresentasikan sebagai tim v1 melawan tim v2. Kemudian jumlah outdegree dan indegree pada digraph dapat direpresentasikan sebagai jumlah kemenangan dan kekalahan pada masing masing tim.Makalah ini akan membahas tentang konsep tournament. Dimulai dari pembahasan mengenai pengertian tournament, isomorphic, transmitter, receiver, transitif, Hamiltonian path, dan teorema tentang tournament. Kemudian dalam makalah ini juga akan dibahas tentang penerapan tournament pada suatu kasus Turnamen Robin..2. RUMUSAN MASALAH

Berdasarkan latar belakang masalah, dapat dirumuskan dua permasalahan yaitu,1.bagaimana konsep dari tournament, dan2.bagaimana menerapkan tournament pada kasus Turnamen Robin.

3. TUJUAN

Tujuan dari makalah ini adalah1. dapat mengetahui konsep dari tournament, dan2. dapat menerapkan tournament pada kasus Turnament Robin.

4. PEMBAHASAN

4.1. PengertianMengacu pada Chartrand [1], tournament T adalah sebuah digraph di mana setiap dua vertex yang berbeda misal u dan v mempunyai tepat satu arc (u,v) atau (v,u) pada T. Dengan kata lain, sebuah tournament adalah digraph yang diperoleh dari pemberian arah pada edge dari complete graph.Jika sebuah tournament T mempunyai vertex p, maka T dikatakan complete ketika mempunyai edge , sehingga dapat dinyatakan dengan

4.2. IsomorphicTournament T1 dan T2 dikatakan isomorphic jika T2 dapat diperoleh dari pelabelan kembali vertex-vertex T1, sehingga arc yang menghubungkan setiap pasangan vertex di T1 mempunyai jumlah dan arah yang sama dengan arc yang menghubungkan pasangan vertex di T2. Contoh isomorphic yaitu pada tournament berorder satu dan dua.vopouopo

Gambar 1. Tournament berorder satuu1v1v2u2

Gambar 2. Tournament berorder dua Contoh tournament yang tidak isomorfik misal pada tournament berorder tiga.

Gambar 3. Tournament berorder tigaPada Gambar 3, jumlah indegree dan outdegree pada T1 adalah sama, sedangkan pada T2 mempunyai jumlah indegree dan outdegree sebagai berikut.od u2 = id w2 = 2 , od v2 = id v2 = 1, od w2 = id u2 = 0karena pada kedua tournament tidak mempunyai jumlah indegree dan outdegree yang sama, maka T1 dan T2 tidak isomorphic.4.3. Transmitter dan receiverTransmitter adalah sebuah vertex yang mempunyai outdegree positif dan indegree nol. Pada Gambar 2 terdapat transmitter yaitu vertex u1.Receiver adalah sebuah vertex yang mempunyai outdegree nol dan indegree positif. Pada Gambar 2 terdapat receiver yaitu vertex v1.4.4. TransitifMenurut Nurul [4] sifat transitif adalah .Mengacu pada Chartrand [2] sebuah tournament T dikatakan transitif jika arc (u,v) dan (v,w) merupakan arc di T maka arc (u,w) juga merupakan arc di T. Pada Gambar 3, terdapat tournament transitif yaitu tournament T2.4.5. Hamiltonian path Hamiltonia path adalah path yang memuat semua vertex tepat satu kali. Contoh dari hamiltonian path dapat dilihat pada Gambar 4.

Gambar 4. Tournament berorder 4Dari Gambar 4 dapat ditunjukkan adanya hamiltonian path yaitu path .4.6. Length Length dari suatu path adalah jumlah atau banyaknya arc pada suatu path. Pada Gambar 4, misalkan diambil : mempunyai length sebanyak dua.4.7. Jarak Untuk setiap vertex dan dalam digraph, jarak (distance) dari ke merupakan length dari path terpendek dalam D. Pada Gambar 4, misalkan diambil maka dapat ditemukan path terpendek yaitu melalui vertex sehingga jarak = 1.4.8. Teorema dan buktiBerikut akan dibahas beberapa teorema yang berkaitan dengan tournament. Teorema 1Jika T adalah tournament, v adalah vertex dari T yang mempunyai maksimum outdegree maka jarak dari vertex v ke vertex yang lain dari T tournament adalah satu atau dua.Bukti

Dimisalkan od v = n, dan v adjacent ke . Jika order dari T adalah p, maka v adjacent dari setiap vertex p-n-1, sebut . Untuk setiap vertex dimana (), mempunyai = 1. Kemudian ditunjukkan untuk setiap vertex , dimana , = 2. Untuk setiap adalah adjacent dari beberapa , jelas bahwa = 2. Andaikan ada sebuah vertex , dimana , tidak adjacent dari vertex (), maka adjacent ke setiap vertex (). Demikian juga adjacent ke v, dan mengakibatkan od . Pengandaian ini kontradiksi dengan kebenarannya bahwa v mempunyai maksimum outdegree dan od v = n. Jadi, setiap vertex adjacent dari beberapa vertex .

Gambar 5. TournamentTeorema 2Tournament dikatakan transitif jika dan hanya jika asiklikBuktii. Jika tournament asiklik maka transitifT merupakan tournament asiklik, sedangkan (u, v) dan (v, w) adalah arc dari T.Karena asiklik, (w, u) E(T) , Sehingga (u,w) E(T) dan T adalah transitif ii. Jika tournament transitif maka asiklik

Andaikan T adalah tournament transitif dan T memuat cycle, katakanlah (dimana karena T adalah asimetrik). Karena () dan () adalah arc dari tournament transitif T, maka () adalah arc dari T. Hal ini sama untuk () ,( ), ..,() adalah arc dari T. Hal ini kontradiksi dengan faktanya bahwa () adalah arc dari T. Jadi, T adalah asiklik.

Teorema 3Setiap tournament memuat hamiltonian pathBuktiDengan induksi pada jumlah vertex p dalam tournament. Dapat diselidiki tournament dengan 1,2,3 atau 4 vertex dan dapat diperiksa masing-masing memuat hamiltonian path (Gambar 6). Sehingga dapat diasumsikan bahwa tournament berorder , memuat hamiltonian path, dan juga untuk tournament berorder . Akan ditunjukkan bahwa memuat hamiltonian path.Misal adalah vertex dari dan adalah tournament dengan order n. Dengan hipotesa induksi, memuat hamiltonian path, sebut saja . Jika adalah arc dari , maka memuat hamiltonian path (Gambar 7). Begitu juga, jika adalah arc dari , maka memuat hamiltonian path (Gambar 8).Anggap adalah arc dari . Jika semua vertex adjacent ke , maka memuat hamiltonian path karena adalah arc dari . Jika tidak semua vertex adjacent ke , maka harus ada sebuah vertex , dimana , sedemikian sehingga dan adalah arc dari (Gambar 9). Jadi adalah hamiltonian path.

Gambar 6. Tournament masing-masing berorder 1, 2, 3 dan 4

Gambar 7. Tournament T (a)

Gambar 8. Tournament T (b)

Gambar 9. Tournament berorder n+1

Teorema 4

Setiap vertex dari tournament yang strongly connected berorder termuat di dalam suatu cycle dengan length n untuk setiap .Bukti

Dengan induksi pada . Jika T merupakan tournament strongly connected berorder p, dan v merupakan vertex dari T. Pertama akan ditunjukkan bahwa v termasuk ke cycle dengan length 3. Karena T strongly connected , od v > 0 dan id v > 0, sehingga himpunan dan adalah tidak kosong. Dengan alasan yang sama, terdapat vertex u dari yang adjacent ke suatu vertex w dari yang terlihat pada gambar _. Jadi v, u, w ,v merupakan cycle dengan lenght 3 yang memuat v.

Gambar 10. Konstruksi 3-cycle pada tournament strongly connected

Anggap bahwa , dan v termasuk ke dalam cycle dengan length k untuk setiap k dengan . Akan ditunjukkan bahwa v termasuk ke cycle dengan length .

Misalkan adalah cycle dengan length n yang memuat v, anggap terdapat vertex u di sedemikian sehingga u adjacent dari suatu vertex dari C dan adjacent ke suatu vertex yang lain dari C. Maka terdapat pasangan vertex adjacent dari C, katakan dan, sedemikian sehingga dan keduanya arc dari T. Sehingga pada kasus ini, adalah cycle dengan length n+1 yang memuat v.

Asumsikan sekarang setiap vertex dari V(T)-V(C) adjacent ke semua vertex di C dan adjacent dari semua vertex di C. merupakan himpunan semua vertex dari V(T)-V(C) yang adjacent dari semua vertex dari C dan merupakan himpunan semua vertex dari V(T)-V(C) yang adjacent ke semua vertex dari C. Karena T strongly connected, terdapat vertex u dari yang adjacent ke vertex w dari . Jadi, merupakan cycle dengan length n+1 yang memuat v.

Gambar 11. Konstruksi Cycle yang lebih panjang yang memuat vertex tertentuAkibat 1 Tournament berorde minimal 3 adalah strongly connected jika dan hanya jika hamiltonian.Buktii. Jika T tournament strongly connencted maka hamiltonian

Jika T tournament strongly connected berorder . Dengan Teorema 4, setiap vertex dari T termasuk ke dalam cycle dengan length n, untuk setiap . Pada khususnya setiap vertex termuat di cycle dengan length p, sehingga menyebabkan T hamiltonian.ii. Jika T hamiltonian, maka T strongly connected..

5. PENERAPAN KASUS

1. Jika terdapat 3 tim bermain pada ronde tournament Robin, tunjukan bahwa ada kemungkinana. Ketiga tim menang 1 kali dan kalah 1 kalib. 1 tim ada yang menang mutlak, 1 tim menang 1 kali dan kalah 1 kali dan tim lain yang kalah mutlak (kalah 2 kali)Jawab :Kemenangan tiap tim direpresentasikan dengan outdegree pada tiap vertex, sedangkan kekalahan tiap tim direpresentasikan dengan indegree pada tiap vertex.a.1

2 3 Dari skema tournamnet di atas terlihat bahwa bannyaknya outdegree dan indegree masing-masing vertex sama yaitu 1 sehingga dapat disimpulakan ketiga tim menang 1 kali dan kalah 1 kalib. 1

23Dari skema tournament di atas terlihat bahwa outdegree pada vertex 1 adalah 2 berarti tim 1 dinyatakan menang mutlak karena menang 2 kali, sementara pada vertex 2 outdegree dan indegree nya berjumlah sama yaitu 1 berarti tim 2 menang 1 kali dan kalah 1 kali, kemudian untuk vertex 3 indegree berjumlah 2 berarti tim 3 kalah mutlak karena 2 kali kalah.

6. KESIMPULAN

1. Tournament adalah sebuah digraph di mana setiap dua vertex yang berbeda misal u dan v mempunyai tepat satu arc (u,v) atau (v,u) pada T. Tournament dikatakan transitif jika dan hanya jika asiklik. Setiap tournament memuat hamiltonian path. Dan setiap tournament yang hamiltonian adalah strongly connected.2. Tournament dapat diterapkan dalam kasus salah satunya adalah pada kasus Turnamen Robin.

7. DAFTAR PUSTAKA

[1]Chartrand, Gary, 1977, Introductory Graph Theory, Dover Publications, Inc : New York.[2]Chartrand G. and Lesniak L., 1996, Graph & Digraph 3rd edition, Chapman and Hall.[3]Chartrand G. and Ortrud R. O., 1993, Applied and Algorithmic Graph Theory, Inc: McGraw-Hill.[4]Nurul M. dkk, 2005, Teori Grup dan Terapannya, UNS PRESS: Surakarta.

MAKALAH TEORI GRAF LANJUTTOURNAMENTS

Oleh kelompok 31. Muhammad Sidiq(M0108095)2. Kristanti(M0109042)3. Tri Endah P(M0109070)4. Dwi Suraningsih(M0110021)5. Nisa Karunia(M0110061)

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS SEBELAS MARET SURAKARTA201212