Penjadwalan Pertandingan Sepak Bola dengan Pewarnaan Graf – Penjadwalan yang efektif pada suatu kompetisi olahraga merupakan hal yang penting. Semakin efektif suatu jadwal pertandingan berarti semakin sedikit waktu yang dibutuhkan untuk menyelesaikan sebuah pertandingan olahraga sistem setengah kompetisi, penjadwalan yang efektif dapat dilakukan dengan menerapkan pewarnaan graf. Pewarnaan graf dapat menghasilkan jumlah hari dan lapangan minimum untuk melaksanakan kompetisi. Aplikasi pewarnaan graf yang digunakan adalah pewarnaan sisi, dimana titik menyatakan tim yang bertanding dan sisi menyatakan pertandingan yang GrafPewarnaan Graf terdiri dari 2 jenis, yaitu1. Pewarnaan TitikPewarnaan titik dilakukan dengan cara memberi warna pada titik-titik graf sedemikian sehingga dua titik bertetangga mempunyai warna Pewarnaan SisiPewarnaan sisi dilakukan dengan cara mewarnai setiap sisi sedemikian sehingga sisi yang bertetangga tidak memiliki warna yang sama. Banyaknya warna minimal yang dapat digunakan untuk mewarnai sisi-sisi dalam suatu graf disebut bilangan kromatik sisi G, yang dinotasikan χ’G.Ada dua teorema yang berkaitan dengan pewarnaan sisi, yaitu1. Teorema VizingJika G merupakan graf sederhana reguler, maka berlakuχ’G = ΔG atau χ’G = ΔG + 1dengan Δ adalah derajat titik graf Teorema pewarnaan sisi graf lengkapUntuk setiap graf lengkap Kn berlakuχ’Kn = n – 1, jika n genap danχ’Kn = n, jika n ganjilAlgoritma pewarnaan sisi graf lengkap untuk n ganjilBerilah warna pada sisi-sisi luar yang membentuk segi-n dengan warna berbeda untuk setiap yang tersisa diberi warna yang sama dangan sisi luar jika sisi tersebut sejajar dengan salah satu sisi pewarnaan sisi graf lengkap untuk n genapHapus salah satu titik sehingga graf menjadi graf lengkap dengan n langkah pewarnaan sisi pada graf lengkap dengan n ganjil hingga kembali titik yang dihapus dan hubungkan titik tersebut ke semua titik. Kemudian warnai sisi dengan warna yang berbeda dengan sisi yang insiden Pertandingan Setengah KompetisiSistem pertandingan setengah kompetisi adalah sistem pertandingan yang mempertemukan sebuah tim dengan seluruh tim lainnya sebanyak satu kali. Sistem setengah kompetisi biasanya diterapkan pada sebuah turnamen olahraga untuk babak penyisihan dan biasanya dilanjutkan dengan sistem gugur untuk menentukan Penerapan Pewarnaan Graf untuk Penjadwalan Pertandingan Sepak Bola Sistem Setengah KompetisiPada suatu universitas, terdapat 13 fakultas yang membentuk tim untuk bertanding dalam rektor cup tingkat universitas tersebut. Liga mahasiswa ini dilaksanakan dengan sistem setengah kompetisi. Liga mahasiswa dibagi menjadi dua grup, yaitu grup I dan grup II. Grup I terdiri atas 7 tim dan grup II terdiri dari 6 tim. Setiap harinya pertandingan dilakukan dalam 2 kloter, yaitu pagi dan sore. Hari pertandingan dalam satu grup harus berselang satu hari dan pertandingan grup II harus lebih dulu selesai dibandingkan dengan grup I. Keterbatasan ini membuat penjadwalan pertandingan menjadi sangat penting karena efektivitas penjadwalan memengaruhi lamanya kompetisi ini tim yang bertanding dan pembagian menjadi dua grup memungkinkan liga mahasiswa ini berlangsung lama. Semakin lama kompetisi berlangsung maka semakin banyak dana yang dibutuhkan. Dengan aturan aturan dan keterbatasan di atas, ketua pelaksana ingin mengetahui jumlah hari minimum yang mungkin untuk melaksanakan liga mahasiswa ini. Semakin sedikit hari pelaksanaan, maka semakin sedikit pula jumlah tersebut dapat diselesaikan dengan teori graf, khususnya pewarnaan graf. Hal pertama yang harus dilakukan adalah merepresentasikan sistem pertandingan setengah kompetisi dengan menggambar graf. Kita misalkan peserta grup I adalah fakultas A, B, C, D, E, F, dan G. Sedangkan peserta grup II adalah P, Q, R, S, T, dan U. Pertandingan sistem setengah kompetisi kedua grup tersebut dapat direpresentasikan sebagai berikut. Titik menandakan tim dan sisi menandakan pertandingan yang 1. Representasi sistem setengah kompetisi round-robin grup I dengan graf lengkapGambar 2. Representasi sistem setengah kompetisi round-robin grup II dengan graf lengkapSetelah direpresentasikan dalam bentuk graf, lakukan algoritma pewarnaan sisi pada graf. Dimulai dari pewarnaan graf pertandingan grup I. Berdasarkan teorema vizing dan teorema pewarnaan graf lengkap, karena peserta grup I berjumlah ganjil, yakni 7 peserta, maka jumlah warna yang dibutuhkan adalah χ’K7 = 7 banyaknya sisi graf lengkap Kn yang dapat diberi warna sama adalah jumlah sisi pada graf lengkap dibagi banyaknya titik atau dapat dituiskan nn-1/2n=n-1/ grup I ini, lakukan algoritma pewarnaan graf lengkap untuk n 3 Menunjukkan langkah pertama dalam pewarnaan graf lengkap dengan n ganjil, yaitu mewarnai seluruh sisi terluar graf dengan warna berbeda. Dalam hal ini karena ada 7 titik maka graf diwarnai dengan 7 warna yang berbeda selanjutnya adalah mewarnai sisi-sisi dalam graf lengkap dengan warna-warna yang sudah ada. Langkah awal pada tahap ini adalah memilih sisi dalam yang akan diwarnai. Pewarnaan sisi-sisi dalam graf lengkap ini dilakukan dengan mencari sisi yang sejajar dengan salah satu sisi terluar pada graf kasus ini, jumlah sisi yang memiliki warna sama dapat dihitung dengan 7-1/2 = 3, yang berarti terdapat 3 sisi yang memiliki warna 4. Pilih sisi yang sejejar dengan salah satu sisi terluar dan warnai dengan warna yang langkah-langkah tersebut hingga semua sisi diwarnai. Graf akan menghasilkan graf dengan sisi berwarna yang setiap warna yang sama berarti pertandingan dapat dilakukan dengan pada saat bersamaan. Graf yang lengkap diwarnai dapat dilihat pada gambar 5. Pewarnaan sisi graf lengkap dengan n = pewarnaan graf tersebut, dapat dibuat penjadwalan pertandingan dengan sisi yang berwarna sama dapat dilaksanakan dalam satu waktu di tempat yang berbeda. Jadwal yang diperoleh adalah sebagai grup II, jumlah peserta berjumlah genap, yaitu 6 tim. Maka menurut Teorema Vizing dan teorema pewarnaan sisi pada graf lengkap, jumlah warna yang dibutuhkan untuk mewarnai graf tersebut adalah χ’K6 = 6 – 1 = 5 pertama yang dilakukan dalam pewarnaan sisi graf lengkap dengan jumlah sisi genap adalah menghapus salah satu titik. Dalam kasus ini, misal kita menghapus titik T. Lalu lakukan pewarnaan sisi untuk graf lengkap dengan 5 6. Penghapusan titik T dan pewarnaan graf lengkap dengan n = itu, Tambahkan kembali titik yang dihapus dan hubungkan titik tersebut ke semua titik. Kemudian warnai sisi dengan warna yang berbeda dengan sisi yang insiden 7. Penambahan kembali titik T dan proses pewarnaan semua sisi diwarnai, graf yang dihasilkan adalah sebagai 8. Pewarnaan graf lengkap dengan n = 6Penjadwalan untuk grup II juga dilakukan dengan cara yang sama dengan grup I, yaitu dengan melihat warna yang sama pada penjadwalan pertandingan grup satu adalah sebagai pewarnaan kedua graf tersebut kita sudah memperoleh jadwal untuk pertandingan grup I dan jadwal untuk pertandingan grup II. Berdasarkan kondisi yang diberikan, yaitu satu hari pertandingan terdapat 2 kloter, yaitu pagi dan sore, sehingga diperlukan 3 buah lapangan. Hari pertandingan grup yang sama tidak boleh berturut-turut, serta pertandingan grup II harus selesai lebih dulu, jadwal pertandingan yang efektif adalah sebagai liga olahraga mahasiswaDari tabel tersebut dapat diketahui bahwa jumlah hari pelaksanaan kompetisi liga olahraga mahasiswa paling sedikit adalah 7 hari dengan 3 Teori graf sangat bermanfaat dalam menyelesaikan permasalahan sehari-hari. Salah satu permasalahan yang dapat diselesaikan dengan teori graf adalah masalah penjadwalan. Penjadwalan dilakukan agar tidak ada kegiatan yang berbenturan. Penjadwalan juga dapat dilakukan dengan jumlah hari yang minimum agar tidak memakan banyak waktu untuk sebuah penjadwalan dapat ditemui di kompetisi olahraga sistem setengah kompetisi. Permasalahan ini dapat diselesaikan dengan salah satu aplikasi pewarnaan graf, yaitu pewarnaan sisi graf lengkap. Jadwal dapat disusun berdasarkan warna yang terdapat pada graf lengkap. Pewarnaan sisi ini dapat digunakan untuk mendapatkan jumlah hari minimum pertandingan sistem setengah kompetisi. Pada kasus yang diberikan, jumlah minimum hari pelaksanaan pertandingan adalah 7 hari dengan 3 lapangan.

cara membuat jadwal pertandingan setengah kompetisi