演算法›Ch4 圖論演算法第 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 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 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 of the graph.
📄 台大112
▤完整推導請見《WH 資工筆記 · 演算法》Ch4 圖論演算法