Question

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、Parallelized Algorithm。然而现实生活鲜少出现分层图。

运用分层图，得以设计一些特别的演算法，例如“ Path ”以及“ Flow ”的演算法。