115 lines
4.9 KiB
TeX
115 lines
4.9 KiB
TeX
\chapter{Euler公式}
|
||
\section{平面图}
|
||
\begin{definition}
|
||
如果图$G = (V, E)$的所有顶点和边可以在一个平面上图示出来，而使各边仅在顶点处相交，则图$G$称为平面图，它的平面图示称为图$G$的\newnoun{平图}{planar graph}；否则称$G$为非平面图。
|
||
\end{definition}
|
||
|
||
需要注意的是，有些图形从表面上看有几条边是相交的，但是不能就此肯定它不是平面图，下面这个图就是一个例子：
|
||
\begin{figure}[H]
|
||
\centering
|
||
\subfloat[最初的图形]{
|
||
\begin{tikzpicture}
|
||
\node[draw=black, circle] (a) at (0,0) {};
|
||
\node[draw=black, circle] (b) at (3,0) {};
|
||
\node[draw=black, circle] (c) at (3,2) {};
|
||
\node[draw=black, circle] (d) at (0,2) {};
|
||
\node[draw=black, circle] (e) at (1.5,3) {};
|
||
\draw (b)--(a)--(d)--(c)--(b)--(e)--(a)--(c)--(e)--(d);
|
||
\draw[opacity=0] (a).. controls (4,-1) ..(c);
|
||
\end{tikzpicture}
|
||
}
|
||
\hspace{2cm}
|
||
\subfloat[调整边的画法后的图形]{
|
||
\begin{tikzpicture}
|
||
\node[draw=black, circle] (a) at (0,0) {};
|
||
\node[draw=black, circle] (b) at (3,0) {};
|
||
\node[draw=black, circle] (c) at (3,2) {};
|
||
\node[draw=black, circle] (d) at (0,2) {};
|
||
\node[draw=black, circle] (e) at (1.5,3) {};
|
||
\draw (b)--(a)--(d).. controls (2,4.5) ..(c)--(b)--(e)--(a).. controls (4,-1) ..(c)--(e)--(d);
|
||
\end{tikzpicture}
|
||
}
|
||
\end{figure}
|
||
|
||
\section{面和边界}
|
||
\begin{definition}
|
||
设$G$是一连通平面，由图中的边所包围的区域，在区域内既不包含图的顶点，也不包含图的边，这样的区域称为$G$的一个\newnoun{面}{face}，有界的区域称为有界面，无界的区域称为无界面。
|
||
|
||
包围一个面的的诸边所构成的回路称为这个面的边界。面$F$的边界的长度称为该面的度数，记为$d(F)$。
|
||
\end{definition}
|
||
|
||
\begin{figure}[H]
|
||
\centering
|
||
\begin{tikzpicture}
|
||
\node[draw=black, circle] (a) at (-3,0) {};
|
||
\node[draw=black, circle] (b) at (0,0) {};
|
||
\node[draw=black, circle] (c) at (1,2) {};
|
||
\node[draw=black, circle] (d) at (1,-2) {};
|
||
\node[draw=black, circle] (e) at (5,0) {};
|
||
\node[draw=black, circle] (f) at (2,0) {};
|
||
\draw (f)--(e)--(c)--(d)--(b)--(c);
|
||
\draw (b)--(a).. controls (1,4).. (e) .. controls (4,-1) and (3,-1.5).. (d) .. controls (0,-1.8) and (-2, -1).. (a);
|
||
\node at (-3.5,0) {$A$};
|
||
\node at (-0.3, 0.3) {$B$};
|
||
\node at (1.3,2.3) {$C$};
|
||
\node at (1, -2.5) {$D$};
|
||
\node at (5.5,0) {$E$};
|
||
\node at (2, 0.5) {$F$};
|
||
\node at (-0.7,-0.7) {$r_1$};
|
||
\node at (0.5,0) {$r_2$};
|
||
\node at (1.5, 1) {$r_3$};
|
||
\node at (0,1) {$r_4$};
|
||
\node at (4,2) {$r_5$};
|
||
\end{tikzpicture}
|
||
\end{figure}
|
||
|
||
在上图中，$d(r_1) = 3, d(r_2) = 2, d(r_3) = 5, d(r_4) = 4, d(r_5) = 3$。
|
||
|
||
\begin{theorem}
|
||
有限平图面的度数之和为其边数的两倍：
|
||
\[\sum d(f) = 2 \vert E \vert\eqper\]
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
任意一条边只可能是下面两种情况中的一种：
|
||
\begin{enumerate}
|
||
\item 它是两个面的共同边，在两个面的度中分别被计算了一遍；
|
||
\item 它是一个面边界的重复，在这个面的度中被计算了两遍。\qedhere
|
||
\end{enumerate}
|
||
\end{proof}
|
||
|
||
\section{欧拉公式}
|
||
\begin{theorem}[Euler's Formula]
|
||
设$G$为一连通平图，$v$为其顶点数，$e$为其边数，$f$为其面数，那么有
|
||
\[v - e + f = 2\eqper\]
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
对面的数量进行归纳。
|
||
|
||
若$f = 1$，则$G$为一棵树，且$e = v - 1, f = 1$，因此$v - e + f = v - v + 1 + 1 = 2$成立。
|
||
|
||
设对于面数小于$n$的所有连通平图定理成立。那么对于面数为$n$的连通平图$G$，任选$G$的一条非桥的边$a$，那么$G-a$是连通平图，且$f(G-a) = n - 1$。由归纳假设有$v(G-a) - e(G-a) + f(G-a) = 2$，同时$v(G-a) = v(G), e(G-a) = e(G) - 1, f(G-a) = f(G) - 1$，因此$v(G) - e(G) + f(G) = 2$。
|
||
\end{proof}
|
||
|
||
\begin{theorem}
|
||
设$G$为一简单连通平图，其点数$v \geq 3$，其边数为$e$，那么$e \leq 3v - 6$。
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
设$G$的边数为$f$，那么每一个面的度数都不小于3；同时各面的度数和为$2e$，这意味着
|
||
\[3f \leq \sum d(F) = 2e, f \leq \frac{2}{3}e\]
|
||
代入Euler's Formula，
|
||
\[2 = v - e + f \leq v - e + \frac{2}{3}e\]
|
||
整理可得$e \leq 3v - 6$。
|
||
\end{proof}
|
||
|
||
这个定理不是充分的，满足此条件的图有可能不是平图。
|
||
|
||
上面的定理利用了``每个面的度都不小于3''这一事实。如果有图的面度都不小于$k$呢？
|
||
\begin{corollary}
|
||
对每个面的度至少为$k$的连通平图，有
|
||
\[e \leq \frac{k(v-2)}{k-2}\eqper\]
|
||
\end{corollary}
|
||
|
||
证明与前面的定理是类似的。 |