演算法›Ch4 圖論演算法
第 13 題/共 111 題
◀ AL 13/111
13. Graph Coloring、Chromatic Number、Independent Set
#AL-04-013易Graph ColoringChromatic NumberIndependent Set

(是非題)A stable set, or independent set, of a graph, is a subset of vertices with the property that no two vertices in the stable set are adjacent. The stability number α(G)\alpha(G) of a graph G is the cardinality of the largest stable set. For the classic coloring problem where the colors of any pair of the adjacent vertices must be distinct, we can solve it by partitioning the graph into stable sets. Therefore, the chromatic number χ(G)\chi(G) of a graph G, that is, the minimum number of colors needed to color the graph, must be smaller than or equal to the stability number α(G)\alpha(G) of the graph.

📄 台大112
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch4 圖論演算法
本章題號 · 1–20 / 111