Jawaban:

Dalam teori graf , pewarnaan sisi dari suatu graf adalah pemberian “warna” pada sisi-sisi graf sehingga tidak ada dua sisi datang yang memiliki warna yang sama. Misalnya, gambar di sebelah kanan menunjukkan pewarnaan tepi suatu graf dengan warna merah, biru, dan hijau. Pewarnaan tepi adalah salah satu dari beberapa jenis pewarnaan graf . Masalah pewarnaan tepi menanyakan apakah mungkin untuk mewarnai tepi suatu graf dengan menggunakan paling banyak k warna berbeda, untuk nilai k tertentu , atau dengan warna sesedikit mungkin. Jumlah minimum warna yang diperlukan untuk tepi grafik yang diberikan disebut indeks kromatikdari grafik. Sebagai contoh, sisi-sisi graf pada ilustrasi dapat diwarnai dengan tiga warna tetapi tidak dapat diwarnai dengan dua warna, sehingga graf yang ditampilkan memiliki indeks kromatik tiga.



Pewarnaan 3-sisi dari grafik Desargues

Dengan teorema Vizing , jumlah warna yang diperlukan untuk mewarnai tepi graf sederhana adalah derajat maksimumnya atau +1 . Untuk beberapa graf, seperti graf bipartit dan graf planar derajat tinggi , jumlah warna selalu , dan untuk multigraf , jumlah warna mungkin sebanyak 3Δ /2 . Ada algoritma waktu polinomial yang membangun pewarnaan optimal graf bipartit, dan pewarnaan graf sederhana non-bipartit yang menggunakan paling banyak +1 warna; namun, masalah umum untuk menemukan pewarnaan tepi yang optimal adalah NP-harddan algoritma tercepat yang diketahui untuk itu membutuhkan waktu eksponensial. Banyak variasi dari masalah pewarnaan tepi, di mana penetapan warna ke tepi harus memenuhi kondisi lain selain non-kedekatan, telah dipelajari. Pewarnaan tepi memiliki aplikasi dalam masalah penjadwalan dan dalam penetapan frekuensi untuk jaringan serat optik.

Penjelasan:

semoga membantu