这里由于不计外区域和中空区域，原图形P的边界为环路，其边数等于頂点数，因此有 N+R-(N+E)=2-B (1) 又因P的边界线只是一个三角形的边，而辅助线是两个三角形的公共边，则有3R±N+ 2E,'根据式(1)和上式，则有 R=N-4+2B (2) 因各三角形内角总和与P的各顶点的内角之和相等，故 (N-4+2B)×2∠R=N,×∠R+N:×3∠R (3) 又N,+N2=N,代入上式整理即得 N,=N+4-2B 2 N:=义-4+2B 证华。 从分析图形可知，凸点总是图形P里某矩形单元的顶点，划分P的线（称划分线）总是 从凹点引出。在P点任取一凹点，向X或Y方向作划分线时，必然是下列的情况之一：1)刘 分线与边界线（或和已划出的划分线）相交，交点称划分点，图3(b)里用△记号表示，2) 划分线恰好通过另一个凹，点，如图3()，称这种联结情况为并联 型。给出图形P,对于并联型的凹点显然应连接这些凹点。对于 第一种情况的凹点则向X或Y任取一方向作划分线，与P的边界 相交，且只相交一点，以后再取另一个凹点作划分线，对所有凹 煮都进行这样划分，就可完成一次划分。这种划分称为合理划 图3， 分。· 是理二：对于一个无并联型凹点的图形P,作合理划分，其划分数M和划分，方式无关 其划分数为 M=N+B-2 2 (4) ·证：由于没有并联型凹点，且作合理划分，无论凹点向X还是向Y引刘分线，和它对应的 划分点只有一个，所以划分点个数N分=N:。又图形经刘分后，边数比原图增加了2N:条线 (除分线外，对应边也被划分点分为两个线段)。经划分后，图形是连通的，由欧拉公式 n+r-e=2 以n=N+N:,e=N+N,r=M+B代入，整理即得 M=N:+2-B =(N-4+2B)+2-B 2 =N+B-2 2 证毕： 对于有并联型凹点的图形P,显然划分数M和划分方式有关，划分点数N分<N:,因 此有 定重三：对于图形P作合理划分，其划分数 145这里 由于不计外 区域 和 中空 区域 ， 原 图 形 的 边界为环路 ， 其边数等于填 点数 ， 因此有 一 一 ’ 又 因 的边界线只 是一个三 角形的边 ， 而辅助线是 两个三 角形 的公共边 ， 则 有 ” 瓦 ， 根据式 和 上 式 ， 则有 一 · 因各三 角形 内角 总和 与 的 各顶点 的 内角之和 相 等 ， 故 ‘ 一 ” ‘ 、 、 一 乙 艺 匕 又 ， 代入 上 式 整理 即得 “ 一 粤 一 十 一 ” 攫一 十 ” 证单 从分析图形可 知 ， 凸点 总是 图形 里 某 矩形单 元的 顶点 ， 划 分 的线 称 划 分线 总是 ‘ 从 画点引出 。 在 点任取 一 凹 点 ， 向 或 方 向 作划 分线 时 ， 必 然是 下列 的情 况 之一 划 夯线与边界线 或和 巳划 出的划 分线 相交 ， 交 点称划 分点 ， 图 里用八记 号表示 ， 一 喧 划 分线恰好通 过 另一个凹 点 ， 如 图 ， 称 这种 联结情况 为并联 型 。 给 出图形 ， 对于并联 型 的 凹点显然应 连 接这些 凹 点 。 对于 第“ 种情况的 凹点则向 或 任取一方 向作划 分线 ， 与 的边界 相交 ， 且只 相交一点 ， 以 后再取 另一个凹 点作划 分线 ， 对所有凹 照都进行这样 划 分 ， 就可完 成一 次划 分 。 这种 划 分称 为合 理划 分 。 凸 凸 图 定理二 对 于一 个无 并联 型 凹点 的 图形 ， 作 合理划 分 ， 其划 分数 和划 分 ， 方式 无 关 其划 分数 为 。 」且 — 十 一 乙 一 证 由于没有并联型 凹点 ， 且 作合 理 划 分 ， 无 论 凹 点向 还是 向 引划 分线 ， 和 它对应的 划 分点只 有一个 ， 所 以划 分点 个数 分 二 。 又 图形经划 分后 ， 边数 比原 图 增加 了 条线 对应 边也被划分点分 为两个线 段 。 经划分后 ， 图形是连通 的 ， 由欧拉公式 一 片 ， 代入 ， 整 理 即得 一 今 一 ‘ “ ， 一 ” 答 一 证毕 对于有并联 型 凹 点 的 图形 ， 显 然 划 分数 和 划 分方 式 有关 ， 划 分点 数 分 ， 因 此有 定翔三 对于 图形 作 合理 划 分 ， 其 划 分数