Olahraga

Cara Penjadwalan Pertandingan Sepak Bola dengan Pewarnaan Graf

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 kompetisi.

Pada 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 terjadi.

Pewarnaan Graf

Pewarnaan Graf terdiri dari 2 jenis, yaitu:

1. Pewarnaan Titik

Pewarnaan titik dilakukan dengan cara memberi warna pada titik-titik graf sedemikian sehingga dua titik bertetangga mempunyai warna berbeda.

2. Pewarnaan Sisi

Pewarnaan 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, yaitu:

1. Teorema Vizing

Jika G merupakan graf sederhana reguler, maka berlaku

χ’(G) = Δ(G) atau χ’(G) = Δ(G) + 1

dengan Δ adalah derajat titik graf reguler.

2. Teorema pewarnaan sisi graf lengkap

Untuk setiap graf lengkap Kn berlaku

χ’(Kn) = n – 1, jika n genap dan

χ’(Kn) = n, jika n ganjil

Algoritma pewarnaan sisi graf lengkap untuk n ganjil:

  1. Berilah warna pada sisi-sisi luar yang membentuk segi-n dengan warna berbeda untuk setiap sisinya.
  2. Sisi-sisi yang tersisa diberi warna yang sama dangan sisi luar jika sisi tersebut sejajar dengan salah satu sisi luar.

Algoritma pewarnaan sisi graf lengkap untuk n genap:

  1. Hapus salah satu titik sehingga graf menjadi graf lengkap dengan n ganjil.
  2. Lakukan langkah pewarnaan sisi pada graf lengkap dengan n ganjil hingga tuntas.
  3. Tambahkan kembali titik yang dihapus dan hubungkan titik tersebut ke semua titik. Kemudian warnai sisi dengan warna yang berbeda dengan sisi yang insiden dengannya.
  4. Sistem Pertandingan Setengah Kompetisi

Sistem 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 pemenang.

1. Penerapan Pewarnaan Graf untuk Penjadwalan Pertandingan Sepak Bola Sistem Setengah Kompetisi

Pada 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 berlangsung.

Banyaknya 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 pengeluaran.

Permasalahan 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 terjadi.

Gambar 1. Representasi sistem setengah kompetisi (round-robin) grup I dengan graf lengkap

Penjadwalan Pertandingan Sepak Bola dengan Pewarnaan Graf

Gambar 2. Representasi sistem setengah kompetisi (round-robin) grup II dengan graf lengkap

Penjadwalan Pertandingan Sepak Bola dengan Pewarnaan Graf

Setelah 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 warna.

Maksimum banyaknya sisi graf lengkap Kn yang dapat diberi warna sama adalah jumlah sisi pada graf lengkap dibagi banyaknya titik atau dapat dituiskan n(n-1)/2n=(n-1)/2.

Untuk grup I ini, lakukan algoritma pewarnaan graf lengkap untuk n ganjil.

Gambar 3

Penjadwalan Pertandingan Sepak Bola dengan Pewarnaan Graf

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 pula.

Langkah 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 lengkap.

Pada kasus ini, jumlah sisi yang memiliki warna sama dapat dihitung dengan (7-1)/2 = 3, yang berarti terdapat 3 sisi yang memiliki warna sama.

Gambar 4. Pilih sisi yang sejejar dengan salah satu sisi terluar dan warnai dengan warna yang sama.

Penjadwalan Pertandingan Sepak Bola dengan Pewarnaan Graf

Lakukan 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.

Gambar 5. Pewarnaan sisi graf lengkap dengan n = 7.

Penjadwalan Pertandingan Sepak Bola dengan Pewarnaan Graf

Dari 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 berikut.

Pewarnaan Sisi Graf untuk Penjadwalan Pertandingan Sepak Bola

Untuk 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 warna.

Langkah 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 titik.

Gambar 6. Penghapusan titik T dan pewarnaan graf lengkap dengan n = 5.

Pewarnaan Sisi Graf untuk Penjadwalan Pertandingan Sepak Bola

Setelah itu, Tambahkan kembali titik yang dihapus dan hubungkan titik tersebut ke semua titik. Kemudian warnai sisi dengan warna yang berbeda dengan sisi yang insiden dengannya.

Gambar 7. Penambahan kembali titik T dan proses pewarnaan sisi.

Pewarnaan Sisi Graf untuk Penjadwalan Pertandingan Sepak Bola

Setelah semua sisi diwarnai, graf yang dihasilkan adalah sebagai berikut.

Gambar 8. Pewarnaan graf lengkap dengan n = 6

Pewarnaan Sisi Graf untuk Penjadwalan Pertandingan Sepak Bola

Penjadwalan untuk grup II juga dilakukan dengan cara yang sama dengan grup I, yaitu dengan melihat warna yang sama pada graf.

Hasil penjadwalan pertandingan grup satu adalah sebagai berikut.

Pewarnaan Sisi Graf untuk Penjadwalan Pertandingan Sepak Bola

Dari 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 berikut.

Jadwal liga olahraga mahasiswa

Pewarnaan Sisi Graf untuk Penjadwalan Pertandingan Sepak Bola

Dari tabel tersebut dapat diketahui bahwa jumlah hari pelaksanaan kompetisi liga olahraga mahasiswa paling sedikit adalah 7 hari dengan 3 lapangan.

Ringkasan :

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 kegiatan.

Permasalahan 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.

Berkomentarlah dengan bijak,,No Spam !