離散數學›Ch6 圖論
第 15 題/共 34 題
◀ LS 15/34
15. 著色理論、著色多項式、色數
#LS-06-015易著色理論著色多項式色數
  1. (10 points) Given a graph G3G3, the first vertex can be colored with any color. The second one can be colored with any color that was not chosen from the first vertex. The adjacent vertices of the G3G3 are colored differently.

a. (2 points) The chromatic number is the smallest number of colors needed to produce a proper coloring of a graph. What is the chromatic number of GG, denoted by χ(G)\chi(G)?

b. (3 points) The chromatic polynomial is a polynomial that represents the number of distinct ways to color the vertices of a graph. What is the chromatic polynomial of G3G3, PGP_G?

c. (5 points) Let PG(n)P_G(n) be the number of different ways to color the vertices of G3G3 using nn colors, where n≥0n \ge 0 is an integer. What is minimum number of PG(n)P_G(n), where PG(n)>0P_G(n) > 0?

題目附圖
📄 交大111
跳轉到第題
▤完整推導請見《WH 資工筆記 · 離散數學》Ch6 圖論
本章題號 · 1–20 / 34