Isi kandungan:

Bilakah graf boleh berwarna?
Bilakah graf boleh berwarna?
Anonim

Graf dikatakan k-berwarna jika ia boleh diwarnakan dengan betul menggunakan k warna. Sebagai contoh, graf dwipartit adalah 2-berwarna. Untuk melihat ini, hanya tetapkan dua warna berbeza pada dua set bercabang dalam graf dwipartit.

Bagaimana anda tahu jika graf mempunyai dua warna?

Sesuatu graf boleh berwarna 2 jika kita boleh mewarnakan setiap bucunya dengan satu daripada dua warna, katakan merah dan biru, supaya tiada dua bucu merah disambungkan dengan tepi dan tiada dua bucu biru disambungkan dengan tepi (graf berwarna-k ditakrifkan dengan cara yang serupa).

Bagaimana anda tahu jika graf mempunyai tiga warna?

Biarkan x ialah bucu dalam V (G) − (N[v] ∪ N2(v)). Dalam mana-mana 3-pewarnaan G yang betul, jika wujud, puncak x sama ada mendapat warna yang sama seperti v atau x menerima warna yang berbeza daripada v. Oleh itu, ia cukup untuk menentukan sama ada mana-mana daripada graf G/xv dan G ∪ xv adalah 3-berwarna.

Apakah syarat untuk mewarna graf?

Penjelasan: Syarat untuk pewarnaan graf yang betul ialah dua bucu yang berkongsi tepi sepunya tidak boleh mempunyai warna yang sama. Jika ia menggunakan k warna dalam proses maka ia dipanggil k pewarnaan graf.

Apakah pewarna graf dan bagaimana ia digunakan?

Pewarna graf ialah prosedur penetapan warna pada setiap bucu graf G supaya tiada bucu bersebelahan mendapat warna yang sama Objektifnya adalah untuk meminimumkan bilangan warna semasa mewarna graf. Bilangan warna terkecil yang diperlukan untuk mewarnakan graf G dipanggil nombor kromatik graf tersebut.

Disyorkan: