D7_5平面方程

图 G 的正常着色 ( 或简称为着色 ) 是指对 它的每一个结点指定一种颜色，使得没有 两个相邻的结点有同一种颜色。如果图 G 在着色时用n种颜色，我们称G为n-色的。 对于图 G 着色时，需最少颜色数称为着 色数，记作x(G)。 虽然到现在还没有一个简单通用的方法， 可以确定任一图 G 是否是 n- 色的。但我们 可用韦尔奇· 鲍威尔法(Welch Powell)对图 G进行着色，其方法是：
[定义] 图G的面和边界 设 G 是一个连通平面图，由图中的边所 包围的区域，在区域内既不包含图的结点， 也不包含图的边，这样的区域称为图 G 的 一个面，包围该面的诸边所构成的回路称 为这个面的边界。
图7-5.3 面及其边界
例如图 7-5.3 ，具有六个结点九条边，它把平面 分成五个面。其中r1、r2、r3、r4四个面是由回 路构成边界，如由回路 BADB 所围， r3 可看成 从 C 点 开 始 围 绕 r3 按 反 时 针 走 ， 得 到 回 路 CDEFFC 所围。另外还有一个面r5 在图形之外， 不受边界约束，称作无限面。如果我们把图形 看作包含在比整个平面还要大的一个矩形之内， 那么在计算图形面的数目时，就不会遗漏无限 面了。 今后我们把面的边界的回路长度称作该面的次数， 记为deg(r)， 在图7-5.3中deg(r1)＝3，deg(r2)＝3，deg(r3)＝ 5，deg(r4)＝4，deg(r5)＝3。
e 2 v 3
3
3
6≤3v-e
e≤3v-6 应用此定理可以判定某些图不是平面图。
例1 设图G如图7-5.5所示，该 图是 K5 图。因为有 5 结点 10 条边，故 3×5 － 6 ＜ 10 ，即 e≤3v-6 对本图不成立，故 K5 是非平面图。
图7-5.5 K5图

章节副标题
点法式求解
点法式：将平面方程转化为点法式，即 Ax+By+Cz+D=0
单击添加正文，文字是您思想的提炼
求解步骤： a. 代入已知点坐标，得到关于A、B、C、D 的方程组 b. 解方程组，得到A、B、C、D的值 a. 代入已知点坐标，得到关于A、B、C、D的方程组 b. 解方程组，得到A、B、C、D的值
题型四：求平面与平面的交点 解析：利用平面方程和向量法，通 过联立方程组求解。 解析：利用平面方程和向量法，通过联立方程组求解。
THEME TEMPLATE
感谢观看
建立坐标系：根据题意，选择合适的坐标系，如直角坐标 系、极坐标系等。
设未知数：根据题意，设出未知数，如x、y、z等。
列方程：根据题意，列出与平面方程相关的方程，如直线 方程、平面方程等。
解方程：根据列出的方程，求解未知数，得到答案。
检验答案：将求得的答案代入原方程，检验答案是否正确。
平面方程的解题技巧
• 求解步骤： a. 确定系数A、B、C、D的值 b. 代入公式求解
• a. 确定系数A、B、C、D的值 • b. 代入公式求解
• 特殊情况： a. 当A=0时，平面方程为By+Cz+D=0 b. 当B=0时，平面方程为Ax+Cz+D=0 c. 当C=0时， 平面方程为Ax+By+D=0 d. 当D=0时，平面方程为Ax+By+Cz=0
平面方程：描述平面上点的坐标 关系的方程
性质：平面方程的系数决定了平 面的位置和方向
添加标题
添加标题
添加标题
添加标题
几何意义：平面方程表示平面上 任意一点的坐标满足的方程
特点：平面方程的系数决定了平 面的性质，如对称性、旋转性等

证明思路：设G的面数为r,当v=3,e=2时上式成立, 若e>=3,则每一面的次数不小于3,各面次数之和为2e, 因此 2e≥3r, r≤2e/3 代入欧拉公式: 2=v-e+r≤v-e+ 2e/3 整理后得: e≤3v – 6
本定理的用途:判定某图是非平面图。
说明：这是简单连通平面 图的必要条件。
6、定义7-5.3 给定两图G1和G2，或者它 们是同构的，或者反复地插入或去掉二度结 点后， 使G1和G2同构，则称G1和G2是在2 度结点内同构的，也称G1和G2是同胚的。
欧拉公式有时可以用来判定某个图 是非平面图。下面的库拉托夫斯基 定理给出了判定一个图是平面图的 充要条件
7、库拉托夫斯基定理(Kuratowski定理) 定理7-5.4 一个图是平面图的充要条件是 它不含与K5或K3，3在二度结点内同构的子图。
（3）设G为k条边时，欧拉公式成立，即 vk-ek+rk=2。
考察G为k+1条边时的情况。 因为在k条边的连通图上增加一条边，使它仍为连
通图，只有下述两种情况：
①加上一个新结点b，b与图上的一点a相连， 此时vk和ek两者都增加1，而面数rk没变，故 （ vk +1）-（ ek +1）+ rk = vk-ek+rk=2。
7-6 对偶图与着色
问题引入
例 考虑把三座房和三种 设施每种都连接起来的问题， 如图7-64所示，是否有可能使 得这样的连接里不发生交叉？ 这个问题可以用K3,3来建模。 原来的问题可以重新叙述为： 能否在平面里画出K3,3 ，使得 没有两条边发生交叉？
• 例如印刷线路板上的布线。 • 在现实生活中，常常要画一些图形，希望 边与边之间尽量减少相交的情况，

7、库拉托夫斯基定理(Kuratowski定理) 定理7-5.4：一个图是平面图的充要条件是它不含 与K5或K3，3在二度结点内同构的子图。
第十六页，编辑于星期二：九点 四十六分。
K5和K3，3常称作库拉托夫斯基图。
K3，3
K5
第十七页，编辑于星期二：九点 四十六分。
作业
P317： （1）（2）
一、对偶图
1、对偶图 定义7-6.1 对具有面F1 ,F2,..., Fn的连通平面图 G=<V,E>实施下列步骤所得到的图G*称为图G的对偶 图（dual of graph）：
第二十二页，编辑于星期二：九点 四十六分。
如果存在一个图G*=<V*，E*>满足下述条件： （a）在G的每一个面Fi的内部作一个G*的顶点vi* 。 即对图G的任一个面Fi内部有且仅有一个结点vi*∈V*。
第十八页，编辑于星期二：九点 四十六分。
7-6 对偶图与着色
掌握对偶图的定义，会画图G的对偶图 G* 掌握自对偶图的定义及必要条件。
第十九页，编辑于星期二：九点 四十六分。
与平面图有密切关系的一个图论的应用是图形的着色问 题，这个问题最早起源于地图的着色，一个地图中相邻国 家着以不同颜色，那么最少需用多少种颜色？ 一百多年前，英国格色里(Guthrie)提出了用四种颜色即 可对地图着色的猜想，1879年肯普(Kempe)给出了这个 猜想的第一个证明，但到1890年希伍德(Hewood)发现肯 普证明是错误的，但他指出肯普的方法 虽不能证明地图 着色用四种颜色就够了，但可证明用五种颜色就够了，即 五色定理成立。
(c)当且仅当ek只是一个面Fi的边界时(割边)，vi*存在 一个环e*k与ek相交。
即当ek为单一面Fi的边界而不是与其它面的公共边 界时，作vi*的一条环与ek相交（且仅交于一处）。所作的 环不与 G*的边相交。