Vizing's Algorithm

    這個演算法是在找一個 simple graph 上的 edge coloring，並且保證他最多只用 Δ(G)^(*1) + 1 種顏色。由 Vizing 在 1964 年發表。

    所謂的 edge coloring 就是，在一張圖 (graph) 上，幫每個邊都塗一種顏色，而共點的邊不能塗一樣的顏色。
    事實上，Vizing's theorem 把無向圖 (undirected graph) 分成兩類：第一類的 χ'(G)^(*2) = Δ(G)、第二類的 χ'(G) = Δ(G) + 1，但是要判斷到底是哪一種，本身就是個 NP-Complete 的問題。