Get best of the week

Warna Pelangi Adalah Teman Terbaik Matematikawan

Baru-baru ini, warna pelangi telah membantu membawa bukti baru. Dan mereka bukan yang pertama kali berguna.



Pengodean warna dari kotak Latin dan grafiknya dapat memberi tahu banyak tentang mereka.

Baru-baru ini, kami berbicara tentang bukti baru hipotesis Ringel . Bagian dari bukti terkait dengan penggunaan warna pelangi, cara khusus pengkodean warna untuk memvisualisasikan informasi. Namun, buku mewarnai seperti itu telah digunakan oleh matematikawan sejak lama untuk memfasilitasi penyelesaian teka-teki, dan sekarang mereka mencoba menerapkan teknik ini pada masalah yang terkait dengan yang sebelumnya.

Hipotesis Ringel adalah masalah dari bidang kombinatorik yang terkait dengan konstruksi grafik - titik (simpul) yang dihubungkan oleh garis (tepi). Ini memprediksi hubungan khusus antara grafik besar dari jenis tertentu dengan 2n + 1 simpul dan grafik yang lebih kecil secara proporsional dengan n + 1 simpul.

Mari kita mulai, misalnya, dengan 11 puncak. Hubungkan setiap simpul dengan yang lainnya untuk mendapatkan apa yang disebut grafik penuh. Selanjutnya, kami mengambil enam simpul yang tersedia, dan menghubungkannya, sesuka kami, hanya agar kami tidak mendapatkan loop tertutup. Jadi kita mendapatkan apa yang disebut "kayu".


Contoh grafik dan pohon lengkap.

Hipotesis Ringel mengatakan bahwa salinan pohon apa pun idealnya dapat menutupi, atau ubin, semua tepi grafik lengkap yang sesuai - sama seperti Anda dapat ubin lantai dapur dengan ubin yang sama.



Seperti halnya lantai dapur, untuk sukses perlu memilih lokasi yang benar dari ubin pertama. Tiga matematikawan yang muncul dengan warna bukti mengkodekan tepi grafik lengkap berdasarkan jarak antar simpul untuk menemukan lokasi ini.



Kemudian mereka mencoba mengatur pohon di dalam grafik lengkap sehingga menutupi satu sisi dari setiap warna. Setelah menunjukkan bahwa pengaturan "pelangi" seperti itu mungkin dilakukan, mereka membuktikan bahwa ubin ideal yang diprediksi oleh Ringel selalu berhasil.

Namun, teknik pewarnaan pelangi ini tidak datang untuk menyelamatkan untuk pertama kalinya.

Pada abad ke-18, Leonard Euler menjadi tertarik pada sesuatu seperti Sudoku untuk anak-anak. Ambil kuadrat 3x3 sel. Euler mengisinya sehingga di setiap baris dan setiap kolom ada angka dari 1 hingga 3, tidak pernah terulang. Teka-teki ini disebut kotak Latin . Pola dan teknik yang ditemukan oleh Euler dan matematikawan lain dalam mempelajari kotak Latin memiliki hubungan dengan banyak bidang matematika yang berbeda.



Kemudian Euler bertanya-tanya: apakah mungkin untuk memilih tiga sel, satu dari setiap kolom dan setiap baris, sehingga angka-angka di dalamnya tidak berulang? Misalkan Anda dapat memilih sel dari kolom pertama dari baris pertama yang berisi 1, sel dari baris kedua dari kolom kedua yang berisi 3, dan dari baris ketiga dari kolom ketiga yang berisi 2. Jadi, kami memilih tiga sel, yang masing-masing memiliki baris dan kolom yang berbeda, dan berisi nomornya - 1, 3, 2. Set sel ini disebut transversal.



Euler ingin tahu apakah mungkin untuk membagi seluruh kisi 3x3 (atau kisi persegi dengan ukuran apa pun) seluruhnya ke dalam set transversal, sehingga setiap set memiliki satu angka dari setiap baris dan setiap kolom. Yaitu, dalam kasus kotak 3x3, saya ingin berharap bahwa kita dapat menemukan tiga set transversal yang berbeda yang menutupi semua sel-sel persegi itu.

Akibatnya, matematikawan telah menemukan bahwa salah satu cara untuk mengeksplorasi masalah ini adalah mengubah kotak menjadi grafik. Untuk melakukan ini, gambar tiga simpul di sebelah kiri, yang menunjukkan tiga kolom. Lalu kita menggambar tiga simpul di sebelah kanan, mewakili garis. Gambarlah ujung-ujungnya yang menghubungkan setiap simpul di sebelah kanan dengan setiap simpul di sebelah kiri. Setiap tepi, yang merupakan kombinasi dari baris dan kolom tertentu, mewakili satu dari sembilan sel. Misalnya, tepi antara simpul kanan atas dan simpul kiri atas berhubungan dengan sel baris pertama kolom pertama (sel kiri atas dari kotak Latin).



Sekarang kita mengeluarkan pensil warna dan menyandikan warna tulang rusuk sesuai dengan jumlah kotak yang ditunjukkannya. Misalkan kita mewarnai garis-garis yang menunjukkan 1 dengan biru, merah dengan 2, kuning dengan 3. Jika 1 berada di sel kiri atas, maka tepi antara simpul atas akan berwarna biru.



Mari kita lihat warna tepinya. Apakah mungkin untuk memilih tiga tepi dari masing-masing tiga warna sehingga mereka mulai dan berakhir pada simpul yang berbeda? Set ini disebut pelangi. Jika Anda menemukannya, menjadi jelas bahwa dalam kotak Latin yang sesuai ada transversal. Selain itu, jika Anda menemukan tiga korespondensi pelangi yang berbeda, menjadi jelas bahwa seluruh kotak Latin terdiri dari transversal.



Pewarnaan pelangi membantu peneliti mempelajari masalah di masa lalu, dan juga menjadi elemen kunci dalam bukti baru hipotesis Ringel. Mereka juga memainkan peran dalam tugas yang lebih kompleks, hipotesis markup anggun .

Untuk memahami esensi masalah, pertama menggambar enam simpul, dan kemudian menghubungkannya untuk membentuk pohon. Tetapkan setiap simpul nomor dengan cara apa pun. Kemudian tandai setiap tepi dengan perbedaan antara jumlah simpul yang terhubung. Misalnya, jika sebuah sisi menghubungkan simpul 6 dan 2, maka kami menandai sisi ini dengan angka 4.

Tujuan Anda adalah membuat label tepi berjalan berurutan dan nomor-nomornya tidak diulang. Dalam hal ini, 1, 2, 3, 4, 5. Jika Anda dapat melakukan ini, maka markup anggun akan ada untuk pohon Anda.



Pada 1960-an, Gerhard Ringel - yang mengajukan hipotesis - dan Anton Kotsig, bersama-sama menyarankan bahwa pohon apa pun, terlepas dari jumlah tepi atau bentuk, dapat ditandai dengan anggun.

Hipotesis markup anggun menyiratkan hipotesis Ringel - yaitu, jika hipotesis pertama benar, maka hipotesis Ringel juga benar. Untuk memahami hal ini, mari kita kembali ke pohon enam simpul yang ditandai dengan anggun dan grafik lengkap dari 11 simpul. Kami mendistribusikan 11 simpul di sekitar keliling dan menomori dari 1 hingga 11. Sekarang kita akan menempatkan salinan pohon pada grafik penuh sehingga label simpul bertepatan: simpul 5 dari pohon tumpang tindih dengan simpul 5 dari grafik penuh, dan seterusnya. Penempatan ini adalah salinan pelangi dari pohon yang ditandai dengan anggun.



Jadi, jika Anda tahu bahwa pohon dengan jumlah simpul n + 1 selalu dapat ditandai dengan anggun, maka Anda tahu bahwa mereka selalu dapat ditempatkan di dalam grafik lengkap yang sesuai dengan simpul 2n + 1 sehingga mendapatkan salinan pelangi dari pohon tersebut. Dan penempatan seperti itu akan menjadi posisi yang tepat untuk memulai proses pemasangan Ringel.

"Jika Anda menemukan markup anggun, saya dapat memberitahu Anda bagaimana menemukan salinan pelangi Anda," kata Benny Sudakov dari Institut Teknologi Federal Swiss, salah satu dari tiga penulis bukti hipotesis Ringel.

Tentu saja, matematikawan akhirnya dapat membuktikan kebenaran hipotesis Ringel tanpa harus membuktikan hipotesis anggun markup, meninggalkan pertanyaan ini tak terjawab.

"Markup anggun adalah masalah yang menarik dan indah dalam dirinya sendiri, dan masih tetap terbuka," kata Sudakov.

Namun, metode yang mengarah pada pembuktian hipotesis Ringel mungkin dapat diterapkan pada markup anggun - dan matematikawan ingin mengetahui sejauh mana metode ini dapat menuntun mereka.

More articles:


All Articles