Pewarnaan Graf

Warnai graf dengan sesedikit mungkin warna

Tentang kalkulator ini

Kalkulator Pewarnaan Graf mencari bilangan kromatik χ(G) — jumlah warna paling sedikit yang diperlukan untuk mewarnai simpul-simpul graf sehingga tidak ada sisi yang menghubungkan dua simpul berwarna sama — dan menampilkan satu pewarnaan optimal. Masukkan jumlah simpul dan daftar sisi; kalkulator menghitung χ secara eksak dengan pencarian branch-and-bound, melaporkan derajat maksimum Δ dan klik terbesar ω (batas bawah untuk χ), menandai graf bipartit dan graf lengkap, serta menggambar graf yang telah diwarnai. Berguna untuk penjadwalan, alokasi register, pewarnaan peta, dan mempelajari bilangan kromatik.

Cara mewarnai graf

  1. Masukkan jumlah simpul; simpul diberi nomor 1 hingga n.
  2. Tuliskan sisi-sisi sebagai pasangan seperti 1-2, 2-3 — satu pasangan untuk setiap hubungan.
  3. Baca bilangan kromatik χ(G) dan warna yang ditetapkan untuk setiap simpul.
  4. Bandingkan χ dengan klik terbesar ω untuk melihat mengapa diperlukan sebanyak itu warna, atau muat preset untuk bereksplorasi.

Contoh umum

  • Segitiga (K₃) memerlukan 3 warna — setiap pasang simpulnya bertetangga.
  • Siklus genap bersifat bipartit dan hanya memerlukan 2 warna; siklus ganjil seperti C₅ memerlukan 3.
  • Graf lengkap Kₙ memerlukan tepat n warna.
  • Klik terbesar berukuran ω memaksa paling sedikit ω warna, sehingga χ(G) ≥ ω.
  • Graf Grötzsch memerlukan 4 warna tetapi tidak memuat segitiga, sehingga χ dapat melebihi bilangan klik.

Pertanyaan yang sering diajukan

Apa itu bilangan kromatik?

Bilangan kromatik χ(G) adalah jumlah warna paling sedikit yang diperlukan untuk mewarnai simpul-simpul suatu graf sehingga tidak ada sisi yang menghubungkan dua simpul berwarna sama.

Bagaimana jumlah warna minimum ditemukan?

Karena grafnya kecil, kalkulator mencari secara eksak: mencoba 1 warna, lalu 2, dan seterusnya, lalu mengembalikan jumlah pertama yang memungkinkan pewarnaan sah. Jumlah tersebut dijamin merupakan minimum yang sebenarnya.

Apa itu derajat maksimum dan klik terbesar?

Derajat maksimum Δ adalah jumlah sisi terbanyak yang bertemu di satu simpul. Klik terbesar ω adalah himpunan simpul terbesar yang semuanya saling bertetangga; karena semuanya harus berbeda warna, χ(G) paling sedikit ω.

Mengapa graf tanpa segitiga tetap bisa memerlukan banyak warna?

Klik yang besar memaksa banyak warna, tetapi itu bukan satu-satunya alasan. Siklus ganjil dan graf seperti graf Grötzsch memerlukan warna tambahan meskipun tanpa segitiga, sehingga χ(G) dapat lebih besar dari bilangan klik.

Apakah ada batas ukuran graf?

Ya. Pewarnaan graf secara eksak sulit secara komputasi, sehingga kalkulator membatasi graf hingga 12 simpul agar hasilnya tetap instan dan tepat.