$n$grafik -partit yang dibentuk oleh $\{0,1,2, \dots, n-1\}^k$

Question

Ada banyak pertanyaan tentang bagaimana membuat grafik $Q_k$dan itu juga dikenal sebagai k-cube dan itu bipartit. Dimana$Q_k$ yang simpulnya diberi label dengan string panjangnya $k$ lebih $\{0, 1\}$. Ada tepi di antara ke simpul jika string yang melabelinya berbeda persis di satu tempat.

Sekarang, apa yang akan berubah jika grafik ini, $Q_k$ dan itu dibentuk oleh $n$string -ary panjangnya $k$. Dan, ada tepi di antara ke simpul jika string yang melabelinya berbeda persis di satu tempat. Bagaimana grafik seperti itu$n$-partite?

Answer 1

Saya pikir pewarnaan berikut membuktikan hal itu $3$ warna sudah cukup (yaitu grafik seperti itu adalah tripartit): Diberikan string $s \in \{0, 1, 2 \}^k$ kami dilambangkan dengan $f(s)$ jumlah dari digit $s$. Kami mendefinisikan pewarnaan kami menjadi fungsinya$C$ peta yang mana $s$ ke jumlah dari digitnya modulo $3$, yaitu $C : s \rightarrow \mathcal{R}_3(f(s))$.

Pertimbangkan dua string yang berdekatan $s$ dan $s'$. Mereka berbeda persis dalam satu posisi. Tanpa kehilangan keumuman yang kita miliki$f(s) < f(s') < f(s) + 3$. Karenanya$\mathcal{R}_3(f(s)) \neq \mathcal{R}_3(f(s'))$ dan oleh karena itu $s$ dan $s'$harus diwarnai berbeda. Ini membuktikannya$C$ adalah pewarnaan yang tepat.

Perhatikan bahwa ada argumen umum yang mendasari: Untuk $l$string -ary Anda dapat membuktikan bahwa mereka dapat diwarnai menggunakan $l$ warna dengan cara yang sama.