bipartite graph

bipartite graph

「二分圖」。可以分成兩群點,兩群點之間有邊,兩群點內部無邊。

二分圖可以重新繪製,讓所有點分成左右兩側,只有左右之間有邊。通常有許多種分法。

二分圖沒有奇環(奇數條邊的環)、只有偶環(偶數條邊的環)。沿著邊走,一往一返,必為偶數。

樹、有向無環圖沒有環,二分圖則是沒有奇環。二分圖也是十分重要的特例,往往存在速度極快的演算法,例如「matching」以及「vertex cover」的演算法。

directed bipartite graph

「有向二分圖」鮮少討論。

現實生活當中的bipartite graph

現實生活有許多圖是二分圖。

配對的概念:男生女生聯誼配對,是二分圖。運動比賽兩隊人馬對決,是二分圖。鬼腳圖,是二分圖。一個蘿蔔一個坑,是二分圖。

輪替的概念:西洋棋盤,點是格子,邊是上下左右相鄰關係,黑格白格形成二分圖。邊是八方向相鄰關係,不是二分圖。騎士移動,是二分圖。國王移動,不是二分圖。

交叉的概念:西洋棋盤,點是行列,邊是格子,是二分圖。兩層迴圈,是二分圖。

bipartite graph資料結構

當資料結構是adjacency matrix,可以進行精簡。就這樣。

bipartite graph recognition

檢查一張圖是不是二分圖,方法很簡單:確認圖上是否有奇環,沒有奇環就是二分圖。

把圖重新畫成樹的形狀,就容易找環了!把圖重新畫成樹的形狀,利用graph traversal即可,無論是DFS或BFS都行!

在樹上標記深度。然後檢查圖上每一條邊,看看端點是否一奇一偶,就能判斷是否有奇環。

最後有件事值得一提。確認一張圖只有偶環、沒有奇環(二分圖),是P問題,有著快速的演算法。確認一張圖沒有偶環、只有奇環,卻是NP-complete問題,目前沒有快速的演算法。非常不可思議!

level graph

level graph

「分層圖」。所有點可以分成許多層,所有邊只連接相鄰的層,所有邊皆朝向更高的層。

很明顯地,樹、森林、有向無環圖、二分圖都是分層圖的特例。

分層圖容易設計有效率的演算法,諸如dynamic programming、parallel algorithm。然而現實生活鮮少出現分層圖。

運用分層圖,得以設計一些特別的演算法,例如「path」以及「flow」的演算法。