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