Sudoku dapat dipandang sebagai pewarnaan parsial dari graf. Banyak cara
menyelesaikan sudoku sama dengan banyak cara mewarnai titik-titik graf yang
belum diwarnai, yang dinyatakan dengan polinomial khromatik. Hal ini menjadi
ide teorema I dan II yang ditulis Agnez M. Herzberg dan M. Ram Murty, yang
dalam skripsi ini disebut teorema polinomial khromatik dalam sudoku. Teorema
adalah pernyataan yang dapat ditunjukkan kebenarannya. Dalam al-Quran surat
an-Naml ayat 64 disebutkan, “… Katakanlah: ‘Unjukkanlah bukti kebenaranmu,
jika kamu memang orang-orang yang benar’ ”. Ayat tersebut bermakna bahwa
setiap yang benar pasti dapat ditunjukkan bukti kebenarannya, termasuk teorema.
Oleh karena itu, skripsi ini bermaksud menjabarkan pembuktian teorema
polinomial khromatik dalam sudoku.
Misal G merupakan graf sederhana, dan p (k) G adalah banyak cara
mewarnai titik G dengan k warna sedemikian hingga tidak ada dua titik adjasen
mendapat warna sama. Fungsi p (k) G disebut polinomial khromatik G. Polinomial
khromatik adalah polinomial monik, yaitu polinomial dengan koefisien utama 1.
Sudoku adalah teka-teki angka yang tengah menjadi trend. Tujuan dari teka-teki
ini adalah mengisikan angka 1 sampai 9 ke dalam 9×9 persegi yang tediri dari
sembilan kotak berisi 3×3 persegi, tanpa ada angka yang terulang pada setiap
baris, kolom, dan kotak.
Langkah-langkah untuk membuktikan teorema I yaitu: menunjukkan bahwa
himpunan S yang dilengkapi dengan relasi subgraf ”≤ ” adalah poset,
menunjukkan berlakunya inversi mobius pada penjabaran hipotesis teorema I
sehingga diperoleh Σ≤
′
′ = ′
( , ) ( , )
, , ( ) ( ) (( , ),( , ))
G C G C
G C G C p λ q λ μ G C G C , menunjukkan
kebenaran konklusi teorema I, menunjukkan kebenaran teorema I untuk jumlah
sisi graf adalah nol, mengasumsikan benar untuk semua graf dengan jumlah sisi
kurang dari jumlah sisi graf (G, C), dan menunjukkan kebenaran teorema I untuk
graf (G, C). Sedangkan teorema II dibuktikan dengan menunjukkan kebenaran
hipotesis teorema II sehingga kebenaran konklusinya dapat ditunjukkan.
Berdasarkan pembahasan dalam skripsi ini, teorema I dapat dibuktikan
dengan dua cara. Cara pertama dengan pembuktian langsung yang menggunakan
teori poset dan fungsi mobius pada poset. Cara kedua dengan pembuktian induksi
kuat pada jumlah sisi graf. Adapun teorema II dapat dibuktikan dengan
pembuktian langsung.
menyelesaikan sudoku sama dengan banyak cara mewarnai titik-titik graf yang
belum diwarnai, yang dinyatakan dengan polinomial khromatik. Hal ini menjadi
ide teorema I dan II yang ditulis Agnez M. Herzberg dan M. Ram Murty, yang
dalam skripsi ini disebut teorema polinomial khromatik dalam sudoku. Teorema
adalah pernyataan yang dapat ditunjukkan kebenarannya. Dalam al-Quran surat
an-Naml ayat 64 disebutkan, “… Katakanlah: ‘Unjukkanlah bukti kebenaranmu,
jika kamu memang orang-orang yang benar’ ”. Ayat tersebut bermakna bahwa
setiap yang benar pasti dapat ditunjukkan bukti kebenarannya, termasuk teorema.
Oleh karena itu, skripsi ini bermaksud menjabarkan pembuktian teorema
polinomial khromatik dalam sudoku.
Misal G merupakan graf sederhana, dan p (k) G adalah banyak cara
mewarnai titik G dengan k warna sedemikian hingga tidak ada dua titik adjasen
mendapat warna sama. Fungsi p (k) G disebut polinomial khromatik G. Polinomial
khromatik adalah polinomial monik, yaitu polinomial dengan koefisien utama 1.
Sudoku adalah teka-teki angka yang tengah menjadi trend. Tujuan dari teka-teki
ini adalah mengisikan angka 1 sampai 9 ke dalam 9×9 persegi yang tediri dari
sembilan kotak berisi 3×3 persegi, tanpa ada angka yang terulang pada setiap
baris, kolom, dan kotak.
Langkah-langkah untuk membuktikan teorema I yaitu: menunjukkan bahwa
himpunan S yang dilengkapi dengan relasi subgraf ”≤ ” adalah poset,
menunjukkan berlakunya inversi mobius pada penjabaran hipotesis teorema I
sehingga diperoleh Σ≤
′
′ = ′
( , ) ( , )
, , ( ) ( ) (( , ),( , ))
G C G C
G C G C p λ q λ μ G C G C , menunjukkan
kebenaran konklusi teorema I, menunjukkan kebenaran teorema I untuk jumlah
sisi graf adalah nol, mengasumsikan benar untuk semua graf dengan jumlah sisi
kurang dari jumlah sisi graf (G, C), dan menunjukkan kebenaran teorema I untuk
graf (G, C). Sedangkan teorema II dibuktikan dengan menunjukkan kebenaran
hipotesis teorema II sehingga kebenaran konklusinya dapat ditunjukkan.
Berdasarkan pembahasan dalam skripsi ini, teorema I dapat dibuktikan
dengan dua cara. Cara pertama dengan pembuktian langsung yang menggunakan
teori poset dan fungsi mobius pada poset. Cara kedua dengan pembuktian induksi
kuat pada jumlah sisi graf. Adapun teorema II dapat dibuktikan dengan
pembuktian langsung.
Artikel Terkait:
Skripsi Matematika
- Download Skripsi Gratis Matematika: PENYELESAIAN PERSAMAAN REGRESI LINIER BERGANDA DENGAN PENDEKATAN METODE KUADRAT TERKECIL DAN METODE MATRIKS
- Download Skripsi Gratis Matematika: ANALISIS FUNGSI AKTIVASI JARINGAN SYARAF TIRUAN UNTUK MENDETEKSI KARAKTERISTIK BENTUK GELOMBANG SPEKTRA BABI DAN SAPI
- Download Skripsi Gratis Matematika: GENERALISASI FUNGSI AIRY SEBAGAI SOLUSI ANALITIK PERSAMAAN SCHRODINGER NONLINIER
- Download Skripsi Gratis Matematika: PENYELESAIAN SISTEM PERSAMAAN FUZZY NONLINIER DENGAN MENGGUNAKAN METODE STEEPEST DESCENT
- Download Skripsi Gratis Matematika: ESTIMASI PARAMETER MODEL REGRESI LINIER PADA DATA
- Download Skripsi Gratis Matematika: ANALISIS ALGORITMA METODE BOOTSTRAP DAN JACKKNIFE DALAM MENGESTIMASI PARAMETER REGRESI LINIER BERGANDA
- Download Skripsi Gratis Matematika: STUDI COPULA GUMBEL FAMILY 2-DIMENSI DALAM IDENTIFIKASI STRUKTUR DEPENDENSI
- Download Skripsi Gratis Matematika: DISKRETISASI MODEL LORENZ DENGAN ANALOGI PERSAMAAN BEDA
- Download Skripsi Gratis Matematika: LIMIT FUZZY DARI SUATU FUNGSI DI R+
- Download Skripsi Gratis Matematika: SIFAT HAMILTONIAN DAN HIPOHAMILTONIAN PADA GRAF PETERSEN DIPERUMUM (GPn,1 & GPn,2)
No comments:
Post a Comment