南京大学：《图论与算法》课程教案讲稿（Graph Theory and Algorithms, GTA）第15周 平面

商有京大努 NANJING UNIVERSITY 第10章平面 程龚 2023/5/22

第10章 平面 程龚 2023/5/22 1

电路版图设计问题 2023/5/22

2023/5/22 2 电路版图设计问题

电路版图设计问题 V2 2023/5/22

2023/5/22 3 电路版图设计问题

电路版图设计问题 V2 3 V2 V3 V4 Vs. 2023/5/22

2023/5/22 4 电路版图设计问题

本次课的主要内容 10.1可平面图 10.2面的染色 2023/5/22

10.1 可平面图 10.2 面的染色 2023/5/22 5 本次课的主要内容

本次课的主要内容 10.1可平面图 10.2面的染色 2023/5/22 6

10.1 可平面图 10.2 面的染色 2023/5/22 6 本次课的主要内容

可平面图 ■在平面上的画法 ●单射函数dr: 将顶点v∈映射到平面上的坐标点d(v) 将边(u,v)∈E映射到平面上的d(w)d(v)曲线 V2 V2 V3 V4 2023/5/22

n 在平面上的画法 l 单射函数dr： 将顶点v ∈ V映射到平面上的坐标点dr(v) 将边(u, v) ∈ E映射到平面上的dr(u)-dr(v)曲线 2023/5/22 7 可平面图

可平面图 ■在平面上的画法 ●单射函数山r: 将顶点v∈映射到平面上的坐标点d() 将边(uv)∈E映射到平面上的d()-d(v)曲线 ■可平面图 ●任意两条边映射到的平面曲线不交叉 (没有除端点外的公共坐标点) ·平面嵌入：画法 平面图：映射到平面上的结果 3 V5 2023/5/22

n 在平面上的画法 l 单射函数dr： 将顶点v ∈ V映射到平面上的坐标点dr(v) 将边(u, v) ∈ E映射到平面上的dr(u)-dr(v)曲线 n 可平面图 l 任意两条边映射到的平面曲线不交叉 （没有除端点外的公共坐标点） l 平面嵌入：画法 平面图：映射到平面上的结果 2023/5/22 8 可平面图

可平面图 ■在平面上的画法 ● 单射函数dr: 将顶点v∈映射到平面上的坐标点d(v 将边(u,v)∈E映射到平面上的d(0)d(v)曲线 ■可平面图 ●任意两条边映射到的平面曲线不交叉 (没有除端点外的公共坐标点) ·平面嵌入：画法 平面图：映射到平面上的结果 ■ 不可平面图 V2 V V5 2023/5/22

n 在平面上的画法 l 单射函数dr： 将顶点v ∈ V映射到平面上的坐标点dr(v) 将边(u, v) ∈ E映射到平面上的dr(u)-dr(v)曲线 n 可平面图 l 任意两条边映射到的平面曲线不交叉 （没有除端点外的公共坐标点） l 平面嵌入：画法 平面图：映射到平面上的结果 n 不可平面图 2023/5/22 9 可平面图

可平面图 ■完全图K1,K2,K3,K4,K是可平面图吗？ V5 2023/5/22 10

n 完全图K1, K2, K3, K4, K5是可平面图吗？ 2023/5/22 10 可平面图 v1 v5 v4 v2 v3