平面圖

定義

如果圖 \(G\) 能畫在平面 \(S\) 上，即除頂點處外無邊相交，則稱 \(G\) 可平面嵌入 \(S\)，\(G\) 為可平面圖或平面圖。畫出的沒有邊相交的圖稱為 \(G\) 的平面表示或平面嵌入。

\(K_{3,3}\) 和 \(K_5\) 不是平面圖。

設 \(G\) 是平面圖，由 \(G\) 的邊將 \(G\) 所在的平面劃分成若干個區域，每個區域稱為 \(G\) 的一個面，其中面積無限的面稱為無限面或外部面，面積有限的稱為有限面或內部面。包圍每個面的所有邊組成的迴路稱為該面的邊界，邊界的長度稱為該面的次數。

平面圖中所有面的次數之和等於邊數 \(m\) 的 2 倍。

若在簡單平面圖 \(G\) 的任意不相鄰頂點間添加邊，所得圖為非平面圖，稱 \(G\) 為極大平面圖。

若 \(G\) 為 \(n (n \geq 3)\) 階簡單的連通平面圖，\(G\) 為極大平面圖當且僅當 \(G\) 的每個面的次數均為 3。

對於任意的連通的平面圖 \(G\)，有：

\(n-m+r=2\)

其中，\(n, m, r\)，分別為 \(G\) 的階數，邊數和麪數。

推論：對於有 \(p (p \geq 2)\) 個連通分支的平面圖 \(G\)，有

\(n-m+r=p+1\)

可推出其他性質：

設 \(G\) 是連通的平面圖，且 \(G\) 的各面的次數至少為 \(l(l \geq 3)\)，則有：

\(m \leq \frac{l}{l-2}(n-2)\)

推論：對於有 \(p (p \geq 2)\) 個連通分支的平面圖 \(G\)，有

\(m \leq \frac{l}{l-2}(n-p-1)\)

推論：設 \(G\) 是 \(n \geq 3\) 階 \(m\) 條邊的簡單平面圖，則 \(m \leq 3n-6\)

若兩個圖 \(G_1\) 與 \(G_2\) 同構，或通過反覆插入或消去 2 度頂點後是同構的，則稱二者是同胚的。

圖 \(G\) 是平面圖當且僅當 \(G\) 不含與 \(K_5\) 或 \(K_{3,3}\) 同胚的子圖。

圖 \(G\) 是平面圖當且僅當 \(G\) 中沒有可以收縮到 \(K_5\) 或 \(K_{3,3}\) 的子圖。

設 \(G\) 是平面圖的某一個平面嵌入，構造圖 \(G^{*}\)：

在 \(G\) 的每個面 \(R_i\) 中放置 \(G^{*}\) 的一個頂點 \(v_i^{*}\)
設 \(e\) 為 \(G\) 的一條邊，若 \(e\) 在 \(G\) 的面 \(R_i\) 和 \(R_j\) 的公共邊界上，做 \(G^{*}\) 的邊 \(e^{*}\) 與 \(e\) 相交，且 \(e^*\) 關聯 \(G^{*}\) 的頂點 \(v_i^*, v_j^*\)，即 \(e^*=(v_i^*, v_j^*)\)，\(e^*\) 不與其他任何邊相交。若 \(e\) 為 \(G\) 中橋且在 \(R_i\) 的邊界上，則 \(e^*\) 是以 \(R_i\) 中頂點 \(v_i^*\) 為端點的環，即 \(e^*=(v_i^*,v_j^*)\)

稱 \(G^{*}\) 為 \(G\) 的對偶圖。

\(G^{*}\) 為平面圖，且是平面嵌入。
\(G\) 中自環在 \(G^{*}\) 中對應橋，\(G\) 中橋在 \(G^{*}\) 中對應自環。
\(G^{*}\) 是連通的。
若 \(G\) 的面 \(R_i, R_j\) 的邊界上至少有兩條公共邊，則關聯 \(v_i^*, v_j^*\) 的邊有平行邊，\(G^*\) 多半是多重圖。
同構的圖的對偶圖不一定是同構的。
\(G^{**}\) 與 \(G\) 同構當且僅當 \(G\) 是連通圖。

平面圖最小割轉對偶圖最短路：BZOJ 1001 狼抓兔子

設 \(G\) 為平面圖，若 \(G\) 存在平面嵌入 \(\tilde{G}\)，使得 \(G\) 中所有頂點都在 \(\tilde{G}\) 的一個面的邊界上，則稱 \(G\) 為外可平面圖，簡稱外平面圖。

設 \(G\) 是簡單的外平面圖，若對於 \(G\) 中任二不相鄰頂點 \(u, v\)，令 \(G'=G \cup (u, v)\)，則 \(G'\) 不是外平面圖，稱 \(G\) 為極大外平面圖。

所有頂點都在外部面邊界上的 \(n (n \geq 3)\) 階外可平面圖是極大外可平面圖當且僅當 \(G\) 的每個外部面的邊界都是長為 3 的圈，外部面的邊界是一個長為 \(n\) 的圈。

\(n (n \geq 3)\) 階極大外平面圖有 \(n-2\) 個內部面。

設 \(G\) 是 \(n (n \geq 3)\) 階極大外平面圖，則：

一個圖 \(G\) 是外平面圖有當且僅當 \(G\) 中不含與 \(K_4\) 或 \(K_{2,3}\) 同胚的子圖。

任何 4 - 連通平面圖都是哈密頓圖。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用