Kalkulator Pewarnaan Graf

Tentang Kalkulator Pewarnaan Graf

Kalkulator Pewarnaan Graf menghitung bilangan kromatik χ(G) dan pewarnaan titik yang valid untuk graf tak berarah mana pun. Masukkan graf Anda sebagai daftar sisi atau daftar ketetanggaan dan alat ini akan mengembalikan jumlah warna minimum yang diperlukan sehingga tidak ada dua titik yang bertetangga berbagi warna yang sama, bersama dengan visualisasi SVG interaktif, jejak DSATUR animasi, dan rincian warna-per-warna tentang titik mana yang menerima warna apa.

Apa itu pewarnaan graf?

Sebuah pewarnaan titik yang tepat dari sebuah graf G = (V, E) menetapkan warna pada setiap titik sehingga setiap sisi memiliki ujung dengan warna yang berbeda. Bilangan kromatik, yang ditulis sebagai χ(G), adalah jumlah warna terkecil yang memungkinkan pewarnaan tersebut ada. Menghitung χ(G) secara umum adalah masalah NP-hard, tetapi masalah ini memiliki teori matematika yang indah dan banyak aplikasi praktis: penjadwalan ujian, alokasi frekuensi radio, alokasi register dalam kompiler, dan teorema empat warna yang terkenal untuk peta planar.

Teorema dan batas utama

• Batas trivial: 1 ≤ χ(G) ≤ |V| untuk graf apa pun.
• Batas bawah klik: χ(G) ≥ ω(G), di mana ω(G) adalah ukuran klik terbesar.
• Karakterisasi bipartit: χ(G) ≤ 2 jika dan hanya jika G tidak memiliki siklus ganjil (König).
• Teorema Brooks: χ(G) ≤ Δ(G), kecuali jika G adalah graf lengkap atau siklus ganjil, dalam hal ini χ(G) = Δ(G) + 1. Di sini Δ(G) adalah derajat maksimum.
• Teorema empat warna: Setiap graf planar dapat diwarnai dengan 4 warna.
• Batas atas greedy: Algoritma greedy apa pun menggunakan paling banyak Δ(G) + 1 warna.

Algoritma yang digunakan oleh kalkulator ini

DSATUR (Degree of Saturation)

Diperkenalkan oleh Daniel Brélaz pada tahun 1979, DSATUR adalah salah satu heuristik praktis terkuat untuk pewarnaan graf. Algoritma ini berulang kali memilih titik yang belum diwarnai yang tetangganya sudah menggunakan warna paling berbeda (saturasinya), memecahkan hasil seri berdasarkan derajat titik, dan menetapkannya warna terkecil yang tidak digunakan oleh tetangganya. DSATUR terbukti optimal pada graf bipartit dan banyak famili graf terstruktur, serta menghasilkan pewarnaan berkualitas tinggi dalam hitungan milidetik pada graf dengan ratusan titik.

Welsh-Powell

Algoritma Welsh-Powell mengurutkan titik dalam urutan derajat yang menurun dan kemudian mewarnainya secara greedy. Algoritma ini berjalan dalam waktu O(|V|²) dan menjamin paling banyak Δ(G) + 1 warna. Algoritma ini sangat cepat dan seringkali menjadi perkiraan pertama yang baik, meskipun dapat dikalahkan oleh DSATUR pada graf dengan struktur lokal yang bervariasi.

Greedy (urutan input)

Algoritma yang paling sederhana: menelusuri titik dalam urutan input dan memberikan masing-masing warna terkecil yang tidak digunakan oleh tetangga yang sudah diwarnai. Hasilnya sangat sensitif terhadap urutan input, tetapi urutan acak memberikan garis dasar yang dapat Anda bandingkan dengan heuristik yang lebih cerdas.

Backtracking eksak

Untuk graf kecil (hingga sekitar 18 titik), kalkulator dapat menemukan bilangan kromatik yang sebenarnya dengan mencoba k = 2, 3, 4, ... dan mencoba mewarnai graf-k dengan backtracking depth-first. Pencarian mengurutkan titik berdasarkan derajat yang menurun dan memangkas pencarian ketika tidak ada warna yang tersedia. Ketika algoritma eksak berhasil, hasilnya diberi label "Eksak".

Format input

Daftar sisi

Tulis setiap sisi sebagai dua label titik yang dipisahkan oleh tanda hubung, spasi, atau panah. Pisahkan sisi dengan koma atau baris baru. Label titik dapat berupa huruf, angka, atau garis bawah. Contoh:

Daftar ketetanggaan

Tulis setiap titik, titik dua, dan daftar tetangganya yang dipisahkan koma. Contoh:

Loop sendiri ditolak karena sebuah titik tidak dapat diberi warna yang berbeda dari dirinya sendiri. Sisi duplikat akan dihapus secara otomatis, dan graf diperlakukan sebagai graf tak berarah.

Cara menggunakan kalkulator ini

1. Pilih format: Beralih antara daftar sisi dan daftar ketetanggaan dengan tombol radio.
2. Masukkan graf: Tempel data Anda atau klik salah satu contoh cepat (segitiga, lengkap K₅, roda mirip Petersen, bipartit K₃,₃, penjadwalan ujian).
3. Pilih algoritma: Biarkan "Otomatis" untuk default terbaik, atau paksa Welsh-Powell, greedy, DSATUR, atau backtracking eksak.
4. Klik "Warnai Graf": Bilangan kromatik, daftar warna-per-warna, SVG interaktif dengan titik yang bisa digeser, dan jejak langkah-demi-langkah animasi akan muncul di bawah.
5. Eksplorasi: Tekan Putar untuk melihat algoritma mewarnai titik satu per satu, geser titik untuk mengatur ulang tata letak, dan gunakan Mundur / Maju untuk menelusuri jejak secara manual.

Aplikasi praktis pewarnaan graf

Penjadwalan ujian

Biarkan setiap ujian menjadi titik dan tarik sisi di antara ujian yang berbagi setidaknya satu siswa. Pewarnaan yang tepat dengan k warna memberikan jadwal dengan k slot waktu sedemikian rupa sehingga tidak ada siswa yang mengalami konflik. Bilangan kromatik adalah jumlah slot minimum.

Alokasi frekuensi radio

Pemancar yang berada dalam jangkauan interferensi satu sama lain harus memancarkan pada frekuensi yang berbeda. Bilangan kromatik dari graf interferensi adalah jumlah frekuensi minimum yang diperlukan.

Alokasi register

Dalam kompiler, rentang hidup variabel adalah titik; dua rentang hidup yang tumpang tindih dalam waktu berarti ada sisi di antara mereka. Pewarnaan-k menetapkan variabel ke k register CPU tanpa tabrakan.

Pewarnaan peta

Negara-negara yang berbagi perbatasan harus menerima warna yang berbeda. Teorema empat warna (Appel-Haken, 1976) membuktikan bahwa empat warna selalu cukup untuk peta planar apa pun.

Sudoku dan teka-teki batasan

Sudoku yang sudah selesai adalah pewarnaan-9 dari sebuah graf yang titik-titiknya adalah 81 sel dan sisinya menghubungkan sel-sel di baris, kolom, atau kotak 3×3 yang sama. Pewarnaan graf adalah inti matematika dari banyak teka-teki pemenuhan batasan.

Kasus khusus yang menarik

• Graf lengkap K_n: χ(K_n) = n. Setiap pasangan titik bertetangga, sehingga semua warna harus berbeda.
• Siklus C_n: χ(C_n) = 2 jika n genap, 3 jika n ganjil.
• Pohon: Pohon apa pun dengan ≥ 2 titik memiliki χ = 2 (pohon adalah bipartit).
• Graf bipartit: χ = 2 jika graf memiliki setidaknya satu sisi.
• Graf Petersen: Graf 3-reguler yang terkenal dengan χ = 3.
• Roda W_n: Titik pusat yang dihubungkan ke siklus-n. χ = 3 jika n genap, 4 jika n ganjil.

Pertanyaan yang sering diajukan

Apa itu bilangan kromatik sebuah graf?

Bilangan kromatik χ(G) adalah jumlah warna terkecil yang diperlukan untuk mewarnai titik-titik graf sehingga tidak ada dua titik yang bertetangga berbagi warna yang sama. Graf bipartit memiliki bilangan kromatik paling banyak 2; graf apa pun yang mengandung segitiga memiliki bilangan kromatik setidaknya 3; dan menurut teorema Brooks bilangan kromatik tidak pernah melebihi derajat maksimum, kecuali untuk graf lengkap dan siklus ganjil.

Algoritma apa yang digunakan kalkulator ini?

Untuk graf kecil, kalkulator menjalankan pencarian backtracking eksak untuk menemukan bilangan kromatik yang sebenarnya. Untuk graf yang lebih besar, digunakan heuristik DSATUR, yang secara berulang mewarnai titik yang belum diwarnai dengan tetangga yang paling banyak sudah diwarnai. Anda juga dapat memaksa Welsh-Powell atau greedy biasa dari dropdown Algoritma.

Bagaimana cara memasukkan graf saya?

Gunakan mode daftar sisi untuk mengetik satu sisi per baris seperti A-B, atau dipisahkan koma seperti A-B, B-C, C-A. Gunakan mode daftar ketetanggaan untuk menulis setiap titik diikuti dengan titik dua dan tetangganya, seperti A: B, C. Loop sendiri ditolak karena sebuah titik tidak dapat diwarnai berbeda dari dirinya sendiri.

Mengapa DSATUR tidak selalu menemukan bilangan kromatik yang sebenarnya?

Pewarnaan graf adalah NP-hard, sehingga tidak ada algoritma cepat yang diketahui selalu menemukan jumlah warna minimum. DSATUR adalah heuristik praktis yang sangat baik dan sering kali cocok dengan bilangan kromatik yang sebenarnya, tetapi pada graf adversarial ia bisa menggunakan lebih banyak warna dari yang diperlukan. Kalkulator melaporkan warna yang digunakan dan batas bawah dari klik terbesar yang ditemukan, sehingga Anda dapat menilai seberapa akurat jawabannya.

Apa kegunaan dunia nyata dari pewarnaan graf?

Pewarnaan graf memodelkan penjadwalan ujian (setiap ujian adalah titik, konflik adalah sisi, warna adalah slot waktu), alokasi frekuensi radio (titik adalah pemancar, sisi adalah interferensi), alokasi register dalam kompiler, pewarnaan peta, pemecahan sudoku, dan penetapan pekerjaan ke mesin di bawah batasan konflik.

Apakah bilangan kromatik selalu sama dengan klik terbesar?

Tidak. Bilangan klik ω(G) selalu merupakan batas bawah untuk bilangan kromatik χ(G), dan keduanya sama untuk graf sempurna seperti graf bipartit, pohon, graf interval, dan graf kordal. Untuk graf umum, χ(G) bisa jauh lebih besar daripada ω(G); contoh klasiknya adalah graf Mycielski, yang bebas segitiga tetapi membutuhkan warna sebanyak apa pun.

Berapa ukuran graf terbesar yang bisa ditangani kalkulator ini?

Kalkulator ini mendukung hingga 60 titik dan 600 sisi. Untuk algoritma eksak, graf dengan lebih dari sekitar 18 titik mungkin beralih ke DSATUR karena backtracking menjadi terlalu lambat. Untuk penggunaan praktis, ini mencakup sebagian besar contoh kelas, masalah penjadwalan ujian, dan aplikasi kecil hingga menengah.

Bacaan Lebih Lanjut

• Pewarnaan graf — Wikipedia
• Algoritma DSATUR — Wikipedia
• Polinomial kromatik — Wikipedia
• Teorema empat warna — Wikipedia
• Teorema Brooks — Wikipedia