Leabharlann 平面图。 平面图 (球极投影)
定理1 可嵌入球面⇔ 可嵌入平面。 定理1 图G可嵌入球面⇔图G可嵌入平面。 例1 是否可平面性？ Q3是否可平面性？
定义2 (平面图的面 边界和度数). 平面图的面, 定义2 (平面图的面,边界和度数). 设G是一个平面图，由G中的边所包围的区域， 是一个平面图， 中的边所包围的区域， 在区域内既不包含G的结点，也不包含G的边， 在区域内既不包含G的结点，也不包含G的边， 这样的区域称为G 这样的区域称为G的一个面。有界区域称为 。有界区域称为内 部面，无界区域称为 ，无界区域称为外部面。包围面的长度最 。 短的闭链称为该面的边界。面的边界的长度称 短的闭链称为 。 为该面的度数。 。
证明:首先建立图G=<V,E>,其中V就取平面上给定的n 证明:首先建立图G=<V,E>,其中V就取平面上给定的n G=<V,E>,其中 个点( ),当两个顶点之间的距离为 个点(位置相同),当两个顶点之间的距离为1时,两顶 ),当两个顶点之间的距离为1 点之间用一条直线段连接,显然图G是一个n阶简单图. 点之间用一条直线段连接,显然图G是一个n阶简单图.
定理2 对任何平面图G 定理2 对任何平面图G，面的度数之和是边数的二倍。 是 。 证明:对内部面而言,因为其任何一条非割 证明:对内部面而言,因为其任何一条非割边同时在两个 面中,故每增加一条边图的度数必增加2. 2.对外部面的边 面中,故每增加一条边图的度数必增加2.对外部面的边 若某条边不同时在两个面中, 边必为割边, 界,若某条边不同时在两个面中, 边必为割边,由于边界 是闭链,则该边也为图的度数贡献2.从而结论成立. 2.从而结论成立 是闭链,则该边也为图的度数贡献2.从而结论成立. 定理3 是带v个顶点， 条边， 定理3 设G是带v个顶点，e条边，r个面的连通的平面 图，则 v-e+r=2。（欧拉公式） e+r=2。（欧拉公式） 。（欧拉公式 证明:(1)当n=e=1时 如下图,结论显然成立. 证明:(1)当n=e=1时,如下图,结论显然成立. :(1)
e j i d c (a) (b)H f g h e i h e i (c)K3,3 h f b a c d g j f d
j
说明:库拉图斯基给出了平面图的充要条件,但用它并不能 说明:库拉图斯基给出了平面图的充要条件, 判别一个图是否是平面图的有效算法. 判别一个图是否是平面图的有效算法. 定义2 设G是阶大于等于3的简单可平面图，若在任意两 定义2 是阶大于等于3的简单可平面图， 个不相邻的结点v 之间加入边{v 个不相邻的结点vi,vj之间加入边{vi,vj}，就会破坏图的 平面性，则称G 平面性，则称G是极大平面图。极大平面图的平面表示称 。 为三角剖分平面图. . 定理2. 极大平面图的判别定理:v阶简单平面图G是极大平 :v阶简单平面图 定理2. 极大平面图的判别定理:v阶简单平面图G 面图的充要条件是: 面图的 是 （1）G中每个面的度数都是3 中每个面的度数都是3 中有e条边r个面， （2） G中有e条边r个面，则3r=2e （3）设G带有v个顶点，e条边，r个面则 带有v个顶点， 条边， e=3v-6,r=2ve=3v-6,r=2v-4.
指出下图所示平面图的面、 例2 指出下图所示平面图的面、面的边界及 面的度数。 面的度数。
e1 f1 e 4 4 f4 e5 e2 e3 6 5 f5
3
1
e10 2 e7 f 3 e6 f2 e8 e9 7
其边界1e 解:面f1,其边界1e15e24e43e72e101,d(f1)=5. 其边界1e 面f2,其边界1e102e87e91,d(f2)=3. 其边界2e 面f3,其边界2e73e67e82,d(f3)=3. 其边界3e 面f4,其边界3e44e57e63,d(f4)=3. 外部面f 外部面f5, 其边界1e 其边界1e15e24e36e34 e57e91,d(f5)=6.
推论1 是非平面图. 推论1知,K5是非平面图. 显然K 没有长度为3的圈,且有6个顶点9条边, 显然K3,3没有长度为3的圈,且有6个顶点9条边, 因而9>2*6 4,由推论 9>2*6- 由推论2 是非平面图. 因而9>2*6-4,由推论2知K3,3是非平面图. 推论3 是带v个顶点， 条边， 推论3 设G是带v个顶点，e条边，r个面的平面 r=1+w。其中w 的连通分支数。 图，则 v- e+ r=1+w。其中w为G的连通分支数。 证明:由欧拉公式有: =2(i=1,2,…,w) 证明:由欧拉公式有: vi- ei+ ri=2(i=1,2, ,w) 从而有 ∑ vi- ∑ ei+ ∑ ri =2w =r+(w-1)(外部面被重 又∑ vi=v, ∑ ei=e, ∑ ri =r+(w-1)(外部面被重 复计算了w ).所以有 所以有: 复计算了w-1次.).所以有: e+r+(wV-e+r+(w-1)=2w 整理即得: v整理即得: v- e+ r=1+w.
a o
θ
y b
a
x b (b) y
x
(a)
第2 节
库拉图斯基定理与极大平面
定义1 定义1 设G是一个平面图，通过删除G的一条边{x、y},并 增加一个新结点a和两条边{x 、a}与{a、y}（所获得的任 何图也是平面图），这样的操作称为初等细分 初等细分。若可以从 初等细分 相同的图G通过一系列初等细分来获得图G1和G2，称G1和G2 称 是同胚的. 是同胚的. 如下图G1,G2,G3是同胚的.
推论1 是带v个顶点， 推论1 设G是带v个顶点，e条边的连通的平面简 单图，其中v 单图，其中v≥3，则e≤3v-6。 证明:由于G是简单图, 中无环和无平行边. 证明:由于G是简单图,则G中无环和无平行边.因此 的任何面的度数至少为3. 3.故 G的任何面的度数至少为3.故 2e=∑d(f)≥ 2e=∑d(f)≥3r (1) 其中r 的面数. 其中r为G的面数.由欧拉公式 v-e+r=2 所以r=2 v+e,代入(1)中有 r=2代入(1)中有: 所以r=2-v+e,代入(1)中有: 2e≥3(2 v+e) 2e≥3(2-v+e) 即 e ≤ 3 v -6。
G1
G2
G3
定理1 一个图G是非平面的，当且仅当它包含一个同 定理1 一个图G是非平面的，当且仅当它包含一个同 胚于K 的子图。（证略） 。（证略 胚于K3.3或K5的子图。（证略） 例1 说明彼得森图不是平面图。 说明彼得森图不是平面图。 解:删去下图(a)皮得森图的结点b,得其子图(b)H.而H 删去下图(a)皮得森图的结点b,得其子图(b)H.而 (a)皮得森图的结点b,得其子图(b)H. 胚于K ,所以皮得森不是平面图. 胚于K3.3a 所以皮得森不是平面图.
证明:必要性: 证明:必要性:因G是简单图,故G中没有环和平行边,故不 是简单图, 中没有环和平行边, 存在度数为1 的面.假设G存在度数大于3的面f, f,不妨 存在度数为1或2的面.假设G存在度数大于3的面f,不妨 为内部面,如下图G,显然v G,显然 不相邻,在面f 设f为内部面,如下图G,显然v1与v3不相邻,在面f内加入 },图 的平面性显然没有改变,这与图G 面{v1,v3},图G的平面性显然没有改变,这与图G是极大平 面图矛盾.因此图G的每个面的度数为3,所以有3r=2e 3,所以有3r=2e且 面图矛盾.因此图G的每个面的度数为3,所以有3r=2e且 e=3v-6,r=2v-4(欧拉公式 欧拉公式) e=3v-6,r=2v-4(欧拉公式) 充分性显然. 充分性显然.
由推论1,只要证明 为一平面图时 即知结论成立. 由推论 只要证明G为一平面图时 即知结论成立 只要证明 为一平面图时,即知结论成立 中存在两条不同的边{a,b}和{x,y}相交于 相交于非端点 反设 G中存在两条不同的边 中存在两条不同的边 和 相交于 如下图(a)所示 其夹角为θ 处o,如下图 所示 其夹角为θ(0< θ <π). 如下图 所示,其夹角为 π 这时如下图(b),显然存在两点距离小于 若θ =π,这时如下图 显然存在两点距离小于 π 这时如下图 显然存在两点距离小于1,与已知 矛盾,从而 从而0< 由于a到 的距离为 的距离为1,x到 的距离为 的距离为1, 矛盾 从而 θ <π.由于 到b的距离为 到y的距离为 π 由于 因此a,b,x,y中至少有两个点 从交点 到这两点的距离不 中至少有两个点,从交点 因此 中至少有两个点 从交点o到这两点的距离不 超过1/2,不妨设为 则点 与x之间的距离小于 不妨设为a,x,则点 则点a与 之间的距离小于 之间的距离小于1,与已知 超过 不妨设为 矛盾,所以 中的边除端点外不再有其它交点,即G为平面 所以G中的边除端点外不再有其它交点 即 为平面 所以 中的边除端点外不再有其它交点 再据推论1知 结论成立 结论成立. 图.再据推论 知,结论成立 再据推论
推论4 推论4
设G是任意平面简单图，则δ(G)≤5。 是任意平面简单图， (G)≤
证明: 证明:设G有v个顶点e条边.若e≤6,结论显然成立; 个顶点e条边. 6,结论显然成立; 结论显然成立 e>6,假设 的每个顶点的度数≥6,则由推论1,有 假设G 则由推论1, 若e>6,假设G的每个顶点的度数≥6,则由推论1,有 2(3v6v ≤2e ≤2(3v-6) 矛盾,所以δ(G)≤ 矛盾,所以δ(G)≤5. 平面上有n个顶点， 例4 平面上有n个顶点，其中任两个点之间的距 离至少为1 证明：在这n个点中距离恰好为1 离至少为1，证明：在这n个点中距离恰好为1的 的点对数至多是3n 3n的点对数至多是3n-6。
推论2 设G是带v个顶点，e条边的连通的平面简单图，其 推论2 是带v个顶点， 条边的连通的平面简单图， 且没有长度为3的圈， 中v≥3且没有长度为3的圈，则e≤2v-4。 证明:因为图G中没有长度为3的圈,从而G 证明:因为图G中没有长度为3的圈,从而G的每个面的度数 至少为4.因此有2e= d(f)≥ 4.因此有2e=∑ 至少为4.因此有2e=∑d(f)≥4r (1) 其中r 的面数. 其中r为G的面数.由欧拉公式 v-e+r=2 所以r=2 v+e,代入(1)中有 r=2代入(1)中有: 所以r=2-v+e,代入(1)中有: 2e≥4(2 v+e) 2e≥4(2-v+e) 即e ≤2 v - 4 。 例3 都是非平面图。 K5和K3.3都是非平面图。 解:图K5有5个顶点10条边,而3*5-6=9,即10>9,由 个顶点10条边, 3*5-6=9,即10>9,由 10条边