【平面圖】

對于一個圖 G=(V,E)，若其重畫后，在平面任意兩條邊的交點除了圖中點外，沒有其他交點，那么這個圖稱為平面圖

• 在平面圖中，由邊包圍并且其中不含頂點的區域稱為面
• 包圍面 R 的所有邊組成的回路稱為面 R 的邊界
• 回路長度稱為面 R 的度，記為 deg(R)
• 具有相同邊界的面稱為相鄰面
• 由平面圖的邊包圍的無窮大的面稱為外部面，一個平面圖有且僅有一個外部面
• 所有面的度的和等于其邊數 E 的兩倍，即有：

【對偶圖】

對于平面圖 G=(V,E)，若圖 G'=(V',E') 滿足：

• G 的任一一面 Ri 內有且僅有一點 vi'
• 對 G 的域 Ri 和 Rj 的共同邊界 Ek，連接一條邊 Ek'=(vi',vj') 且只與 Ek 交于一點
• 若共同邊界 Ek 完全在域 Ri 中，那么 vi' 有一自環 Ek'

則稱圖 G' 為平面圖 G 的對偶圖

【平面圖轉對偶圖】

平面圖與對偶圖常應用于網絡流中。

若網絡流的圖 G 能轉換成一個平面圖，那么有：

• 對偶圖 G' 中的環對應平面圖 G 中的割
• 平面圖 G 的面數等于對偶圖 G' 的點數，且 G 與 G' 的邊數相同

利用最大流最小割定理轉換模型，根據平面圖 G 與對偶圖 G' 的關系，若想求出 G 的最小割，那么令轉換后的 G' 的每條邊的長度等于他的容量，于是最小割的容量就等于最短路的長度。

總結

以上是生活随笔為你收集整理的图论 —— 网络流 —— 最小割 —— 平面图与对偶图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。