第九章平面图与图的着色
第九章 平面图与图的着色
91平面图与欧拉公式 9.1平面图与欧拉公式(补充) 92顶点着色 93平面图的着色 94边的着色 95图着色的应用
9.1 平面图与欧拉公式 9.1 平面图与欧拉公式（补充） 9.2 顶点着色 9.3 平面图的着色 9.4 边的着色 9.5 图着色的应用
平面图 在现实生活中,常常要画一些图形,希 望边与边之间尽量减少相交的情况,例 如印刷线路板上的布线,交通道的设计 等。 ■同构
平面图 在现实生活中，常常要画一些图形，希 望边与边之间尽量减少相交的情况，例 如印刷线路板上的布线，交通道的设计 等。 同构
9.1平面图与欧拉公式 、平面图 ■定义91(平面图) 若一个图能画在平面上使它的边互不 相交(除在顶点处),则称该图为平面图, 或称该图能嵌入平面的。 e6 e5 e3 e2 es e4
9.1 平面图与欧拉公式 一、平面图 定义9.1（平面图） 若一个图能画在平面上使它的边互不 相交（除在顶点处），则称该图为平面图， 或称该图能嵌入平面的
图91(a),(b) 图91(a)平面图G,(b)所示的G是G的平面嵌入
图9.1(a),(b) 图9.1(a)平面图G, (b) 所示的 Ğ 是 G的平面嵌入