软 件
•则
学 院
n-m+r=2
张 丽
离
散
数
学
欧拉公式证明
北
京 工
• 用归纳法，对边数进行归纳。
业 大 学
• 当图中仅有一条边时，有两种结构，
软 件
一是有两个邻接点和一条关联这两顶点
学 院
的边，
张 丽
易知n=2，m=1，r=1(仅有一个无限区 域)，所以欧拉公式n-m+r=2成立；
另一种是由一条自由回路构成的图，这
3n – 6 ≥ m
离
散
数
证明（续）
学
北
京 工
由此可得
业 大
6n－12≥ (n-1)n/2
学 软
整理后得
件
学 院
n2 - 13n+24≤0
张或
丽
n2 - 13n+22≤0 (n - 11)(n - 2)<0
由此可得n<11，这和假设n≥11矛盾，证毕。
离
散
数
学
二度同构
北
京 工 业
• 如果两个图是由同一个图的边上插
件
学 院
3n- 6≥m
张 丽
离
散
数
推论证明
学
北
京 工
•
由于G是简单图，因此G中每一个区域
业 大
至少由3条边围成，
学 软
•
件
学
院
若G中有r个区域，围成r个区域总边数 为2m(因为每条边都作为两个相邻区域 的公共边，被计算了两次)。
张 • 所以有
丽
2m≥3r 或 r ≤ 2m/3
• 代入欧拉公式后得
n - m+ 2m/3 ≥ 2
K3,3中，n=6，m=9，不满足上述不等式， 所以K3,3不是平面图。
离
散
数
证明
学
北
• 京
工 业
证明具有5个顶点的无向完全图K5
大 学
是非平面图
软
件 学
•
证明 因为在K5中顶点数n=5，边
院 数m=10，3n – 6 = 9<m，
张 丽
不满足平面图的必要条件，
所以K5是非平面图。
离
散
数
平面图例1
大 学
入一些新的顶点(它一定是2度点)而
软 件
得到的，
学
院 • 则称这两个图是二度同构的。
张 丽
离 散 数 学
二度同构
北 京 工 业 大 学 软 件 学 院 张 丽
离
散
数
学
库拉托夫斯基定理
北
京 工 业
• 一个图是平面图的充分必要条件是
大 学 软
该图不包含二度同构于K5或K3,3的
件 学
子图。
院
张 丽
学
北
京 工 业
• 设G是至少有11个顶点的无向简单连通平面图， 证明G的补图~G一定是非平面图。
大 学
• 证明
设图G有n个顶点(n≥11)，m条边，显然
软 件
其补图~G 有n个顶点、(n-1)n/2-m条边。
学 院
用反证法，设补图~G也是平面图， 则有
张 丽
3n – 6 ≥ (n-1)n/2-m
图G是连通简单平面图，所以有
学
北
京 工 业
• 证明
把DE和
大 学
FH删去，
软
B
A FG
C
H
件 学
与K3,3是二度同
院 构的，
JI
E
D
张 丽
所以彼得逊图是
I
B
D
E
J
非平面图。
F
H
A
G
C
业 大
边和r个区域的连通平
学 软
面图记作G(n,m,r)。
件 学
• 在G(n,m,r)中添加一条
院
边后，增加了一个顶点
张
但没增加区域数
丽
• 构成图G(n+1,m+1,r)，
欧拉公式仍然成立
• 证毕。
离
散
数
欧拉公式推论
学
北
京 工
• 设图G是具有n(≥3)个顶点、m条边
业 大
的无向连通平面图，
学 软
•则
离
散
数
学
欧拉公式证明（续）
北
京 工
可能有三种不同的结构。
业
大
学
软
件
学
院
张 丽
离
散
数
学
欧拉公式证明（续）
北
京 工
• 把具有n个顶点，m条
业 大
边和r个区域的连通平
学 软
面图记作G(n,m,r)。
件 学
• 在G(n,m,r)中原有的
院
两点中添加一条边，
张
增加一个区域
丽
• 构成图G(n,m+1,r+1),
学
北
京
工
业
大
学
软
件
学
院
张 丽
离
散
数
区域
学
北
京 工 业
• 平面图的边把平面图
大 学
划分成的块
软
件 学
• 例如
院 – 平面图将平面划分成4
R2 R1
张 丽
个区域
R3
– R1、R2、R3是有限区域
R4
– R4是无限区域
离
散
数
欧拉公式
学
北
京 工
• 设图G是无向连通平面图，
业 大 学
• 它具有n个顶点，m条边和r个区域，
时n=1，m=1，r=2，所以欧拉公式成立。
离
散
数
学
欧拉公式证明（续）
北
京 工
• 设当连通平面图具有m条边时，欧拉公
业 大
式成立。
学 软 件 学
• 一个具有m+1条边的连通平面图，删去 一条边后，仍然是平面图。
院
• 把具有m+1条边的连通平面图看作是由
张 丽
含m条边的连通平面图添加一条边后构
成的。
离
散
数
平面图
学
北
京 工 业
• 如果能把一个图在平面上画成除端
大 学
点外，任何两边都不相交，
软
件 学
• 则称此图为可平面的，
院 • 或称平面图。
张
丽
离
散
数
平面图示例
学
北
京
工
业
大
学
软
件
学
院
张 丽
离
散
数
平面图示例
学
北
京
工
业
大
学
软
件
学
院
张 丽
离
散
数
非平面图示例
学
北
京
工
业
大
学
软
件
学
院
张 丽
离
散
数
非平面图示例
从而得到 3n－6≥m
离
散
数
示例1
学
北
京 工
• 证明K3,3是非平面图
业 大 学 软
• 证明 由于K3,3是完全二部图，因此每条回路 由偶数条边组成，
件 学 院
而其K每3,一3又个是区简域单至图少，由所4以条如边果围成K3，,3是平面图，
张 于是有 2m≥4r 或 r≤m/2 。 丽 代入欧拉公式后可得 2n－4≥m。
欧拉公式成立
离
散
数
学
欧拉公式证明（续）
北
京 工
• 把具有n个顶点，m条
业 大
边和r个区域的连通平
学 软
面图记作G(n,m,r)。
件 学
• 在G(n,m,r)中原有的
院
两点中添加一条边，
张
增加一个区域
丽
• 构成图G(n,m+1,r+1),
欧拉公式成立
离
散
数
学欧拉公式证明（续） Nhomakorabea北
京 工
• 把具有n个顶点，m条
离
散
数
非平面图证明例2
学
北
京 工 业
• 证明所示图是非平面图。
大 学 软
• 证明
把图中的边ED删去后，所得
件 学
的子图就是K3,3 ，所以此图是非平
院 面图。
张
B
丽
A
B
C
A
F
C
E
D
F
E
D
离
散
数
非平面图证明例3
学
北
京
工
业
大 学
• 证明彼得逊图
软 件
B
是非平面图。
学
院
A
G
C
F
H
张
丽
J
I
E
D
离
散
数
非平面图证明例3