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 的問題。

    既然是恐怖的 NPC，要嘛就乖乖花 exponential time 的時間去解它，再不然就是去找 approximation 了。Vizing's algorithm 可以找到一個最多用 Δ(G) + 1 種顏色的塗色方法，這是一個很強大的近似解，它最多只比最佳解多 1 ！
    好 approximation，不看嗎？所以我就看了，而且還要把它實做出來 (不過實作的細節還沒想完 XDD)。不過關於時間複雜度嘛，可以說是眾說紛紜：

    我偉大的老闆：amortized O(E)
    強大的維基百科^[2]：只要用 "some simple data structures" 就可以把這個演算法 bound 在 O(VE)
    Stony Brook Project Implementation^[3]：大概是 O(V²E) 之類的，我也沒看很懂它的 code @@

    好啦總之就是這樣子，所以下面先敘述一下這個演算法到底在幹嘛 (它很特別的是，做法跟證明是合在一起的，在講完做法的同時它的正確性也被證完了)。關於實作細節和時間複雜度，等我想完再發另一篇吧！


[以下正文]

* 下面所有的「塗色方式」都是指合法的塗色方式，即共點的邊不會是一樣的顏色。


0. G 是一個 simple graph，現在要證明 χ'(G) ≦ Δ(G) + 1，同時說明要怎麼找到這樣的一種塗色方式。

1. 假設 G 的 subgraph G' 已經塗好顏色了。若 G' ≠ G，必存在一個 edge uv 未塗色。如果我們可以幫 uv 塗色 (可能需要改變一些目前已經塗好顏色的 edge)，就能不斷重複這個過程 (稱為 augmentation)，直到 G' = G，就完成了我們的目標 =D 。

2. 對於每個點 (vertex) 來說，它附近的邊一定至少有一種顏色沒用過。 (因為我們有 Δ(G) + 1 種顏色可以用~~)

3. 現在開始嘗試著幫 uv 塗顏色！ (Let v = v₀)
    假設：a₀ 是 u 沒用到的顏色、a₁ 是 v₀ 沒用到的顏色。
        如果 u 也沒用過 a₁，我們就可以幫 uv₀ 塗上 a₁ 這個顏色！

        

        Done!!!!!!!!!!!
        但是世界不會這麼美好，要來考慮一下 u 有用過 a₁ 的狀況。

4. 找到 u 的另一個 neighbor v₁，而且 uv₁ 就是塗 a₁ 顏色的傢伙。
    假設：a₂ 是 v₁ 沒用到的顏色。
        如果 u 也沒用過 a₂，我們就可以把 uv₁ 換成 a₂、uv₀ 就可以塗 a₁ 了！

        Done!!!!!!!!!!!
        噩夢是不會輕易結束的，還要考慮 u 有用過 a₂ 的狀況。

5. 找到 u 的另一個 neighbor v₂，而且 uv₂ 就是塗 a₂ 顏色的傢(ㄏㄨㄣˊ)伙(ㄉㄢˋ)。
    假設：a₃ 是 v₂ 沒用到的顏色。
        如果 u 也沒用過 a₃，我們就可以把 uv₂ 換成 a₃、uv₁ 換成 a₂、uv₀ 就可以塗 a₁ 了！

        Done!!!!!!!!!!!
        依照這樣的規則，我們就可以一直推下去囉~~

6. 一直往後找 a_i 和 v_i-1，如果發現 u 沒用過 a_i，就可以照上面的方法往回推，幫 uv₁ ~ uv_i-1 重新塗顏色，最後幫 uv₀ 塗上 a₁ 顏色。這個過程叫做 downshifting from v_i-1。

7. 但是世界是有盡頭的噢，因為顏色最多只有 Δ(G) + 1 種，遲早會重覆。
    假設：v_l 是第一個「沒用過的顏色和前面重覆」的點，並且假設重覆的顏色是 a_k。
        沒用過的顏色 list：

vertex	u	v0	v1	...	vk-1	...	vl-1	vl
color	a0	a1	a2	...	ak	...	al	ak

        如果 v_l 也沒用過 a₀，我們就可以把 uv_l 換成 a₀，之後downshifting from v_l-1 (因為 uv_l 被換成 a₀，此時 u 已經沒有用過 a_l 了)。

    
    

        Done!!!!!!!!!!!
        事情絕對沒有這麼簡單，還是要考慮 v_l 有用過 a₀ 的情形。

8. 現在要找到一條從 v_l 開始，延伸到最長的 path P，其中 P 經過的 edge 被輪流塗成 a₀ 和 a_k 兩種顏色。示意圖：



    接下來要把 v_x 分成 3 種情形來討論：
        (1) v_x = v_k
        (2) v_x = v_k-1
        (3) v_x ∈ V - { u, v_l, v_k, v_k-1 }
             u：沒用過 a_k，且 a₀ 已用過
             v_l：a₀ 和 a_k 都已用過
             v_k & v_k-1：在 (1) 和 (2) 討論過了

9. v_x = v_k
    把 uv_k 換成 a₀、把 P 上的 edge a₀ 換成 a_k、a_k 換成 a₀，之後 downshifting from v_k-1 (因為 uv_k 被換成 a₀，此時 u 已經沒有用過 a_k 了)。

    
    

    downshifting from v_k-1 之後，augmentation 就完成了！

10. v_x = v_k-1
    把 uv_k-1 換成 a₀、把 P 上的 edge a₀ 換成 a_k、a_k 換成 a₀，之後 downshifting from v_k-2 (因為 uv_k-1 被換成 a₀，此時 u 已經沒有用過 a_k-1 了)。

    
    

    downshifting from v_k-2 之後，augmentation 就完成了！

11. v_x ∈ V - { u, v_l, v_k, v_k-1 }
    把 P 上的 edge a₀ 換成 a_k、a_k 換成 a₀ (v_x 要嘛沒用過 a₀、要嘛沒用過 a_k，否則 P 可以繼續延伸)、把 uv_l 換成 a₀，之後 downshifting from v_l-1 (因為 uv_l 被換成 a₀，此時 u 已經沒有用過 a_l 了)。

    
    

    downshifting from v_l-1 之後，augmentation 就完成了！

我們已經把所有的可能討論完了，以上就是 Vizing's Algorithm 的做法 (以及證明)。
(這個結尾有點無力，但是請原諒我，因為我已經好累了 zz)

[正文結束]


附上不精美手稿 (紀念用 XD)





Comments
(*1) Δ(G)：G is an undirected simple graph, Δ(G) is its maximum degree.
(*2) χ'(G)：G is an undirected simple graph, χ'(G) is the chromatic index, or edge chromatic number of G, which is the smallest number of colors needed in a edge coloring of G. Also denoted χ₁(G)

References
[1] Wikipedia. (2013 June 9). Edge coloring [Online/Web]. Available: http://en.wikipedia.org/wiki/Edge_coloring
[2] Wikipedia. (2013 February 21). Vizing's theorem [Online/Web]. Available: http://en.wikipedia.org/wiki/Vizing%27s_theorem
[3] Stony Brook. (2008 July 10). Edge Coloring [Online/Web]. Avaliable: http://www.cs.sunysb.edu/~algorith/files/edge-coloring.shtml
[4] Douglas B. West, Introduction to Graph Theory, Upper Saddle River, NJ: Prentice-Hall, 1996, sec. 6.1.