（计算数学专业论文）有关分片代数曲线bezout数的研究.pdf

大连理工大学硕士学位论文 摘要 分片代数曲线定义为二元样条函数的零点集合。利用样条函数对散乱数据插值时， 插值适定的充要条件即为节点数与样条空间维数一致且所有节点不落在同一条分片代数 曲线上。分片代数蓝线的研究不仅对二元样条插值有重要的意义，而且对于传统的代数 曲线理论研究也是较为重要的。众所周知，b e z o u t 定理是传统代数几何的开卷定理其弱 形式是：两条交点有限的代数曲线交点上界不超过其次数的乘积，我们将两条代数曲线次 数的乘积称为其b e z o u t 数鉴于b e z o u t 定理在传统代数曲线理论中的重要地位，考虑 b e z o u t 定理在分片代数曲线中的推广对于分片代数曲线的研究十分重要。 施锡泉与王仁宏在文 2 2 中对任意三角剖分上，两条0 阶光滑的分片代数曲线交点有 限的前提下，相交数所能达到的上界进行了估计，即考虑了o 阶光滑的分片代数曲线的 b e z o u t 定理。王仁宏，赵国辉在文 2 1 中引入了齐次三角样条的概念。并利用三角函数 的性质估计出t b e z o u t 数b n ( m ，1 ；n ，1 ；a ) 许志强在文 9 中首先证明了文 2 2 中提出的 关于三角剖分的猜想性结论，并指出了分片线性代数曲线与四色猜想之间的内在联系， 再利用m o r g a n s c o t t 剖分，指出了分片代数曲线b e z o u t 数的不稳定性，最后利用组合优 化的方法，给出了任意三角剖分上任意光滑的分片代数曲线b e z o u t 数的上界估计，即考 虑了任意阶光滑的分片代数曲线的b e z o u t 定理。 本文首先对文 9 中的b e z o u t 数a n ( m ，r ；n ，以) 做了一些适宜的修整和改进，并把 这个结果用到了矩形割分上的分片代数曲线b e z o u t 数的估计上。再对0 阶光滑分片代 数曲线的b e z o u t 数b n ( m ，0 ；n ，0 ；a ) 做了进一步的补充，得出了b n ( m ，r ；n ，r ；) = m n t 的充分必要9 d 牛- ，用b n ( m ，0 ；n ，o ；) 的性质论述了一个图论中的有趣的性质，并用组合 数学的方法估计出齐次三角样条函数零点个数的上界，最后举出例子说明这个上界能达 到的可能性。 关键词：b e z o u t 定理分片代数曲线牛顿公式齐次三角样条函数 三角剖分 论文题目 a b s t r a c t ap i e c e w i s ea l g e b r a i cc u r v ei sac u r v ed e t e r m i n e db yt h ez e r os e to fa b i v a r i a t es p l i n ef u n c t i o n i ti so b v i o u st h a tt h ep i e c e w i s ea l g e b r a i cc u r v e i sag e n e r a l i z a t i o no ft h ec l a s s i c a la l g e b r a i cc u r v e t h ep i e c e w i s e a l g e b r a i cc u r v ei s n o to n l yv e r yi m p o r t a n tf o rt h ei n t e r p o l a t i o nb yt h e b i v a r i a t es p l i n e s ( c f 2 0 ) ，b u ta l s oau s e f u lt o o lf o rs t u d y i n g t r a d i t i o n a la l g e b r a i cc u r v e s i ti sw e l lk n o w nt h a tb e z o u t st h e o r e mi sa n i m p o r t a n ta n dc l a s s i c a lt h e o r e mi nt h ea l g e b r a i cg e o m e t r y ( c f 1 9 ) i t s w e a kf o r ms a y st h a tt w oa l g e b r a i cc u r v e sw i l lh a v ei n f i n i t e l ym a n y i n t e r s e c t i o np o i n t sp r o v i d e dt h a tt h en u m b e ro ft h e i ri n t e r s e c t i o np o i n t s m o r et h a nt h ep r o d u c to ft h e i rd e g r e e s d e n o t eb yb n ( m ，0 ；疗，0 ；) t h es o c a l l e db e z o u t sn u m b e r 。i tm e a n sa n yt w op i e c e w i s ea l g e b r a i cc u r v e s f ( x ，y ) = 0 ，g ( x ，y ) = o ， 厂戳( ) ，g ( ) ，m u s t h a v ei n f i n i t e l ym a n yi n t e r s e c t i o np o i n t sp r o v i d e d t h a tt h e yh a v em o r et h a nb ni n t e r s e c t i o np o i n t s i nc i t e 2 2 ，t h eu p p e rb o u n d a r yo f b n ( m ，o ；n ，o ；a ) i sp r e s e n t e d i n 2 1 ， a nu p p e rb o u n d a r yo f b n ( m ，1 ；n ，1 ；a ) i sp r e s e n t e d i n 9 x uu s e dt h e c o m b i n a t o r i a lm e t h o dw h i c hi sd i f f e r e n tw i t ht h em e t h o di n 2 2 ，a nu p p e r b o u n do ft h e b n ( m ，r ；n ， ) i sp r e s e n t e d i nt h i st h e s i s ，w em a k es o m ei m p r o v e m e n tt o b n ( m ，r ；n ，f ；) ，w h i c hi s o b t a i n e db y 9 a n dw i t ht h ef u r t h e rs t u d y i n go fb n ( m ，o ；n ，0 ；a ) ，o b t a i n e d t h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o no f b n ( m ，r ；n ，f ；厶) = r a n t 。a n du s i n g t h i sc h a r a c t e ri l l u s t r a t e do n ei n t e r e s t i n gf a c t o ro fg r a p h i c s n e w t o nf o r m u l ai sa ni m p o r t a n tf o r m u l ao fc o m b i n em a t h e m a t i c s ，i nt h i s t h e s i sw eo b t a i n e do n ee x p r e s s i o no f 岛+ i = 曰“+ + 1 + + “b yu s i n gn e w t o n f o r m u l a ，a n du s i n gt h i se x p r e s s i o n ，w ee s t i m a t e dt h eu p p e rb o u n d a r yo fz e r o p o i n t so fh o m o g e n e o u st r i a n g u l a rs p l i n e k e y w o r d s , p i e c e w i s ea l g e b r a i cc u r v e s ：b e z o u t sn u m b e r ；n e w t o nf o r m u l a ； - u - 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：那e t 顺日期：2 0 0 5 6 1 0 大连理工大学硕士学位论文 1 绪论 1 1 多元样条函数的基本理论 多元样条函数作为函数逼近论的一个重要分支，在过去的三十年中得蚕d 广泛的发 展。它已成为研究计算几何。数值分析，逼近和优化的基本工具。并广泛地应用于计算 机辅助几何设计( c a g d ) ，曲线、曲面几何造型，计算机辅助设计与制造( c a d c 田 等诸多领域。在散乱数据插值以及曲面拟合中，多元样条有着广泛的应用。 1 9 7 5 年，王仁宏在文献( f l 】) 中采用函数论和代数几何的方法建立了任意音q 分下 多元样条函数的基本理论框架，并提出所谓的光滑余因予协调法。从这种基本观点出发 多元样条函数的任何问题都可以转化为与之等价的代数问题来研究。此方法深刻地刻划 了多元样条函数光滑连接的内在本质，对研究样条函数空间的结构有重大理论指导意 义。使用这种方法，人们成功地解决了平面上相当广泛的一类剖分( 比如贯穿剖分等) 上的样条函数空间的维数及基底。 设d 为二维e u c l i d 空间r 2 中的给定区域，以n i 记二元七次实系数代数多项式集 女k 一 合：i - i t _ p = c 口x y 。i 勺为实数) 。一个二元多项式p 。称为是不约多项式， # i o j - 0 如果除了常数和该多项式自身外没有其它多项式可整除它( 在复域中) 。代数曲线 r ：? 似力= o ， ，瓴力。，称为不约代数曲线。如果，似力是不可约多项式， 显然直线是不约代数曲线。 今用有限条不约代数曲线对区域d 进行割分，于是d 被刮分为有限个区域 q ，d 2 ，d 。它们被称为d 的胞腔。形成每个胞腔边界的线段称为网线，网线的交点 称为网点或顶点，同一网线的两个端点称为相邻网点。以某一网点v 为顶点的胞腔的并 集称为网点v 的关联区域或星形区域，记为( 矿) 。d 上关于剖分的二元七次阶光 滑的样条函数空间记醚( a ) 墨p c 一( d ) i 引n 1 7 j ，j = 1 ， 。 王仁宏在文献( 【1 】) 中指出了样条函数光滑连接的内在本质，表现为下面定理1 1 1 1 1 2 。 定理1 1 1 ( 【1 】) 设z = s ( x ，y ) 在两相邻胞腔d j 和j d ，上的表达式分别为 z = p ，( x ，y ) 和z = p s ( x ，力，其中n ，p je 1 - i i 。为使j ( 乓y ) e c 一( 瓦c 历_ ) ， 论文题目 必须且只须存在多项式吼( x ，y ) n i - ( 1 ) d ，使得 p ， ，y ) 一p ，( x ，y ) = 【( x ，j ，) 】”- q u ( x ，_ y ) ， 其中巨与e 的公共内网线为：0 ( 墨_ y ) = 0 ， ( 1 1 1 ) ( 1 1 2 ) 且不约代数多项式0 ( x ，力1 - i 。由定理1 1 1 中( 1 1 1 ) 式所定义的多项式因子o ，y ) 称为内网线l ：( x ，y ) = 0 上的( 从d ，到d j 的) 光滑余因子( 1 】) 。说明内网线0 上的 光滑余因子存在在，恒指形如( 1 1 1 ) 的等式成立。 定义1 1 1 ( 1 ) 位于区域d 内部的网点称为内网点，否则称为边界网点。 如果一条网线的内部属于区域d 内，则称此网线为内网线，否则称为边界网线。 设4 为任一给定的内网点。今按下列顺序将过a 的所有内网线矾) 所涉及的i 和， 进行调整：使当一动点沿以一为心的逆时针方向越过r i ，时，恰好是从d ，跨入口。 设爿为一内网点，定义4 点处的“协调条件”( c o n f o r m a l i t y c o n d i t i o n ) ( 1 】) 为 一i t p ( x ，y ) 】“碍口( x ，) ，) 暑o ( 1 1 3 ) 其中己表示对一切以内网点a 为一端的内网线所求的和，而吼( x ，力为上的光滑 余因子。 设的所有内网点为爿l ，一，a u ，则“整斗蝴调条件”( 1 】) 为 町x ，斓川q f ( 昂川；0 ， v = 1 ，m ， ( 1 1 4 ) 下述的定理建立了二元样条的基本理论框架： 定理1 1 2 ( 【1 ) 对给定的剖分a ，二元样条函数s ( x ，力酣( ) 存在，必须且只须 s ( x ，奶在每条内网线上均有一光滑余因子存在，并且满足( 1 1 4 ) 所示的整体协调条 件。 王仁宏还在文献( 3 ) 中建立了多元样条函数的一般表达式。 设区域d 被剖分a 分割为如下有限个胞腔d 。，d ：，d 。任意取定其中一个胞 腔。例如d 1 作为源胞腔，从源胞腔d 1 出发，画一流向图0 ，使之满足： 1 c 流遍所有胞腔d i ，d 2 ，d 各一次； 2 c 穿过内网线的次数不多于一次； 3 c 不允许穿过网点。 流向图0 所经过的内网线称为相应于0 的本性内网线，其它的内网线则称为相应于0 的 可去内网线。显然可去内网线与本性内网线只是一个相对的概念。设：毛( x ，y ) = o 为 2 大连理工大学硕士学位论文 0 的任意一条本性内网线，将从源胞腔0 出发，沿0 前进时，只有越过r 才能进入的 所有闭胞腔的并集记作u ( 聪) 。将从源胞腔0 出发沿f v 前迸时，在越过之前所经 过的备胞腔并集记为u ( 巧) ，称u ( e ) u ( 巧) 为网线l 的前方，记作z ( ) 。 定义1 1 2 ( 2 ， 3 ) 设l ：f ，( x ，y ) = 0 为相应于流线0 的本性内网线，多元 广义截段多项式定义为 叭w 坩= t 乒o ，删” 瓴穿曼天撼。 n 1 样条函数的表现定理： 定理1 i 3 ( 2 。 3 ) 任意s 雕( ) 均可唯一地表示为 s ( x ，_ y ) = p ( x ，j ，) + 【毛( x ，_ y ) 】r “q ( 工，y ) ，( x ，) ，) d ， ( 1 1 6 ) 其中p ( x ，y ) e l - i 。为s ( x ，y ) 在源胞腔上的表示式，d 表示对所有本性内网线求和，而 且沿c 越过l ：乇( 石，力= o 的光滑余因子为劬丑，。 在文献( 4 】) 中，王仁宏给出了栉维样条函数的基本理论框架。这些基本理论类似于 上面关于二元样条的结果。 王仁宏，c 。k c h u i ，l ，l s c h u m a k e r , 何天晓，施锡泉等学者应用光滑余因子协调法 成功的解决了贯穿刺分( 【2 4 1 ) ，拟贯穿剖分( 【6 1 ) ，l - 致【2 5 】) ，2 - 霎d ( 5 1 ，1 7 1 ，口6 】) 等三角剖分 上彤( ) 空间的维数以及样条基函数，其中耐( 镰) 嗣( k ) ，( ) 等空间上的丑样 条基是非常重要且实用的。他们也讨论了带边界条件的样条函数空间的结构问题( 详见 文献【8 】，【2 7 】) 。上面结果也可以参考王仁宏的专著( 【2 】) 。其他学者也用此方法研究了 某些特殊三角割分上样条函数空间的结构，并得到了丰富的结果。这些充分表明了光滑 余因子协调法对研究样条函数空间结构的巨大作用。 1 2 分片代数曲线和b e z o l r t 数的研究意义及发展历程与主要研究结果 利用多元样条函数进行散乱数据插值是计算几何中一个非常重要的课题。王仁宏 ( 【2 】， 2 4 】， 2 5 9 ，l l s c h u m a k e ( 3 4 1 ) , o l e gd a v y d o v ( 3 0 ，【3l 】) ，c a m t h e rn t l r n b e r g e t ( 3 5 3 6 】) ， 等学者在构造多元样条函数空间插值适定结点组与讨论插值结点的适定性方面做了大量 的研究工作。在某些特殊样条函数空间里，他们给出了寻找适定结点组的方法，同时也 讨论了在给定结点组下，如何寻找使之成为适定结点组的剞分。在文献( 3 2 】， 3 3 】冲， - 3 一 论文题目 o l e gd a v y d o v , m a n f i e ds o m m e , h a n ss t r a u s s 提出了几乎插 e ( a l m o s t i n t e r p o l a t i o n ) 和局 部线性独立基( l o c a l l yl i n e a r l yi n d e p e n d e n ts y s t e m s ) 概念，并给出了插值结点组几乎适 定( a l - s e t s ) 的充簧条件( 【3 7 】) 。这个充耍条件类似于一元样条中的s c h o e n b e r g - w h i t n e y 定 理。在2 0 0 0 年，他们( 2 9 】) 给出了鄙( ) 空间插值结点组适定的一个充要条件。但由于 多元样条函数空间的结构不但依赖于剖分拓扑性质，而且紧密地依赖于剖分的几何性 质，这就使得对样条函数空间的插值结点的适定性的研究变得十分复杂。目前为止，其 它样条函数空间彤( ) 的插值( 特别是l a g r a n g e 插值) 适定性问题始终未能解决。王仁宏 为解决这一问题提出了分片代数曲线的概念( 见 1 】，【2 】，【3 】，【2 8 】) ，并指出：插值结点组适 定的充要条件是这些结点不在同一条非零分片代数曲线上。因此，本质上，解决插值结 点的适定性问题关键在于研究分片代数曲线，在高维空间里就是研究分片代数簇。 分片代数曲线作为二元样条函数的零点集合，它是代数几何与计算几何中种新的 重要概念，显然也是经典代数曲线的推广。因此，研究分片代数曲线具有重要的理论与 实用价值。在这方面，王仁宏( 【2 】，1 2 0 ，【2 1 】 2 8 1 ) ，施锡泉( 【l o 】) ，罗钟铉( 【11 】) ，苏志勋 ( 【1 2 】) ，赵国辉( 1 3 】) ，刘秀平( 1 4 】) 等学者做了大量的研究工作。他们特别对分 片代数曲线的一个核心问题：交点的b c z o u t 数进行了深入的研究。在文献( 2 2 】) 中，施 锡泉，王仁宏给出了关于- s o ( ) ，碟( 厶) 中任意两个分片代数曲线交点的b e z o u t 数，从 而推广了代数曲线的经典b e z o u t 定理，得到了b n ( m ，o ；n ，0 ；) 的上界。在文献 2 q 中， 赵国辉用齐次三角样条的性质估计出了b n ( m ，1 ；n ，i ；a ) 的一个上界。在文献【9 】中，许志 强首先证明了文 2 2 中提出的关于三角剖分的猜想性结论，并指出了分片线性代数曲线 与四色猜想之间的内在联系，再利用m o r g a n - s c o t t 剖分，指出了分片代数曲线b e z o u t 数的不稳定性，最后利用组合优化的方法，给出了任意三角剖分上任意光滑的分片代数 曲线b e z o u t 数的上界估计，即考虑了任意阶光滑的分片代数曲线的b e z o u t 定理。 我们知道b e z o u t 定理的弱形式是说：如果两条代数曲线有超过它们次数乘积的交 点数，那么它们必有无限个交点( 即有公共分支) 。这个次数乘积数称为b e z o m 数。 我们用b n = b n ( m ，r ；n ，f ；) 表示爵( ) ，( ) 中两个分片代数曲线交点b e z o u t 数，那 么对任意两个分片代数曲线f ：f “y ) = 0 ，g ( x ，y ) = 0 ，f 戳( ) ，g ( ) ， 若它们有超过b n 个交点，则必有无限个交点( 1 l p 有局部公共分支) 。 4 大连理工大学硕士学位论文 一个三角剖分叫2 符号：如果中每一个三角形的三个顶点均可用一1 或1 标号，但 同一三角形的三个顶点不能用同一数标号。 一个三角剖分叫3 符号：如果中每一个三角形的兰个顶点均可用- 1 ，0 或1 标号， 但同一三角形的三个顶点必须用- 1 ，0 ，l 标号。 称的内顶点v 是偶顶点，如果过顶点v 有偶数条剖分网线，否则称为奇顶点。 定理1 2 1 ( f ，翻) 当是2 顶点符号剖分，且m 忍为偶数；或是3 一顶点符号剖 分时； 丑( m ，o ；n ，o ) = m n t ， 否则 b n ( m , o ；栉，o ) s 坍疗t - 【v 一- d + 2 】， j 其中r 是三角剖分中三角形的个数，p o 是中奇顶点的个数。 在文献( 1 3 】， 2 1 】，【2 8 】) 中，王仁宏，赵国辉给出了星形域上砩( ) 和醴( a ) 的b e z o m 数的一个上界。罗钟铉( 1l 】) 给出了平行剖分的b c z o u t 数的一个上界。刘秀平( 【1 4 】) 着 重研究了分片代数曲线的局部性质，给出了网线上的分片曲线的点为跨越点的一些充分 条件及算法。 但由于分片代数曲线依赖于剖分的几何性质且具有局部性，使得对它的研究存在许 多实质性困难，它绝不是代数曲线的简单推广。目前，对它的研究还刚剐开始，有许多 问题有待于解决。 分片代数簇作为一些多元样条函数的公共零点集合，同样也是代数几何中一种新的 重要概念，是经典代数簇的推广。它与许多实际问题如：c a d ，c a m 和c a e 紧密相 联，因此，对它的研究也具有重要的理论与实用价值。王仁宏，苏志勋( 【2 】， 1 2 1 ， 2 0 】) 在这方面做了较深入的研究，建立了有关分片代数簇的基本理论。但同样存在许 多问题有待于解决，特别是关于实分片代数簇问题。 5 论文题目 2 前人的结果 利用样条函数对数据进行插值是样条函数的重要作用之一。一元样条函数的插值无 论在理论还是应用中都已比较成熟。但多元样条函数的插值的研究却颇为困难。即使对 多元样条的锐化形式一多元多项式插值的研究也并不完善。人们在研究多元多项式插值 的过程中发现，无论是构造插值的试顶节点组还是研究插值适定性的充要条件均与多元 多项式的零点集合代数曲线有着密切关系。由此，启发我们研究多元样条函数的零点 集合分片代数曲线。分片代数曲线是代数几何与计算几何中的一中新的重要概念，显 然也是经典代数曲线的推广。分片代数曲线也是研究传统代数曲线的一种有效工具。因 此，分片代数曲线的研究无论在理论还是应用中都有重要的意义。 众所周知，b e z o u t 定理是传统代数几何的开卷定理。其弱形式是：两条交点有限的 代数曲线交点上界不超过其次数的乘积，我们将两条代数曲线次数的乘积称为其b c z o u t 数【1 9 】。 签予b c z o u t 定理在传统代数曲线理论中的重要地位，考虑b c z o u t 定理在分片代数 曲线中的推广对于分片代数睦线的研究十分重要。在文 2 2 1 中，施锡泉和王仁宏给出0 阶光滑分片代数衄线b c z o u t 数上界。许志强 9 】考虑任意光滑的分片代数曲线b e z o u t 数 上界。文【9 】首先指出了分片代数曲线和四色猜想之间的关系。利用m o r g a n - s c o t t 剖分 指出b o z o u t 数的不稳定性。最后与文【2 2 】完全不阿的方法，给出任意阶分片代数曲线 b e z o u t 数的上界。本章主要介绍文 9 】中的得到的结果，并在最后一节介绍齐次样条的 概念。 2 1 单纯形剖分顶点染色问题 对去间【o ，1 】进行剖分，可用黑白两种颜色进行染色，使得对任子区间的两个端 点颜色不同。这一结论非常显然。但是，这一结论如何推广到高维? 通常，区间剖分在 高维推广就是单纯形剖分。具体2 维，则是三角剖分。首先考虑2 维情形的推广。 对有界区域d 进行三角剖分，能否用黑白两种颜色对顶点进行染色，使得每一三 角形的三个顶点颜色不全一致，即：三个顶点的颜色不全是黑的也不全是白的? 我们将 用图论的方法证明这结论成立。 所谓图g 是指有序组( v ，d ，其中e 为无序对v ( 2 的一个子集v 称为顶点集，e 称为边集 图g 中一个点边交替的非空有限序列w = 0 0 e 。o l e 2 口。称为g 中的一条路，其中u 。是 - 6 大连理工大学硕士学位论文 点，e l 是边，对于l f 玎，e 。的端点是q 。和q ，和u 。分别称为路的起点和终点起点与 终点相同的路称为圈对g 中的两个顶点u , u 如果存在一条路连接“和u 则称u 和u 是连 通的如果g 中任意一对顶点都是连通的则称g 为连通图若e 的子集e 使得g e 不连通， 则称五+ 是g 的一个边割图g 称为k 边连通的如果没有势小于k 的边割假定v 是图g 的一个 顶点，在g 中与u 相连的边的数目称为u 的度，记为d ( v ) 如果g 中所有顶点的度均为k ，则g 称为k 正则图 任意不含圈的连通图称为树与同一个顶点关联的两条边称为相邻的设e 为边的 子集，若e 中任两条边在g 中均不相邻则称五+ 为g 的一个匹配若g 中每个顶点都与e 。中的 一条边关联，则称e 为完美匹配事实上，三正贝t j _ - - 边连通图一定存在一个完美匹配 2 7 将三角剖分考虑作为个平面图a = ( n d 给定一三角割分，我们将构造另外一个图 a = ( 矿1 ，e ) 在里每个三角形乃内部选择一点u j ，若瓦与乃，相邻，并设公共边为p f ， 则连接u j 与u ，。，并将连线记为e ：最后围绕画一圈，记为0 ，对每一条边界网线e ， 。_ 。 我们画一条线穿过b ，连接。与一，此处 ：为与e ，相关的三角形丁，内部的点，并将该线记为 e ：不同的u ? 与圈的连接点也不同那么，我们构造的图厶称为图a 的对偶图，边p ：与e ， 互为对偶边图2 1 显示了一给定及其对偶厶在图2 1 中，我们用1 ，一l 表示两种不同的 颜色 图2 1 利用数学归纳法，可以比较容易地证明如下引理 引理2 。1 i1 对于任意的四边形剖分，可用黑、自两种颜色对顶点染色，使任意相连的 顶点颜色不同。 定理2 1 1 对任意三角音0 分，可用黑白两种颜色对顶点进行染色，使得每一胞腔 的三个顶点颜色不全一致 7 论文题目 证明：显然，对任意的三角剖分，其对偶图厶一定是三正则二边连通的因此存 在一个完美匹配，设为e o ，鹾在中的对偶边集记为或考虑i 薹t d ( a ) = ( 矿，e 、或) 和 d ( 厶) = ( 矿。，e e ) d ( ) 是四边形剖分和一些树的并利用引理2 1 1 和树的定义， d ( ) 中的每个顶点可用两种颜色染色，并使得任意两个相连顶点标记不同颜色，将该染 色方式记为m 因为d ( ) 与顶点一致，我们可用同样的标号方式恻中每一顶点染色 根据完美匹配与对偶的定义，d ( a ) 实际上是将中的每个三角形去掉且仅去掉一条边 产生的因此，a 中位于同一三角形中的三个顶点不能在标号方式m 中标记为完全相同的 颜色由此，我们得到了一个的染色方式m ，使得里任意三角形三个顶点的颜色不全部 一致证毕 设k ( n ) 为大于l 的整数，且满足如下条件： k j - n 维空间的有限单纯形剖分，可用k ( n ) 种颜色对其顶点染色，使得对任一单纯形d n 而言，k ( e 1 ) 种颜色中的任一种，都染在d 0 的一个顶点上 由此，我们有如下问题： 问题2 1 1 对任意整数一1 ，k ( n ) 存在吗? 若存在，唯一吗? 能否对给定的n 列出所 有k ( n ) ? 上述问题的答案即可看作本节刚开始时简单结论的推广 对低维情形，根据上面的证明，很显然有： 定理2 1 2 当珂2 ，k ( n ) 存在且唯一，且k ( n ) = 2 三角剖分称为2 顶点符号的，如果可以用一1 或l 对里的每一个顶点标记，使得内 任一三角形三个顶点的标记符号不全部一致 文 2 2 提出一个有趣的猜想：任意三角剖分都是2 顶点符号的 借助这个猜想，可以方便地得到o 阶光滑的分片代数曲线b e z o u t 数的上界事实上， 通过定理2 1 1 j 这一猜想成立 2 2 三角剖分与分片代数曲线 设为三角剖分，设v i 为内顶点数目，v b 为边界顶点数目，v 0 为顶点总数目 e i 为内网线数目，为边界网线数日，e o 为网线总数，n 为内三角形总数对于 二元样条函数空间彤( ) ，曲r ： o ，y ) i j 帆n = o ，s ( x ，y ) 彭( ) ) 称为分片代数曲线 - 8 大连理工大学硕士学位论文 推论2 2 1 对任意三角剖分和整数d 1 ，存在一条分片代数曲线 f ：f ( x ，y ) = o ，( 五y ) 础( ) 、o 使得r n r , o ，1 f n 证明：因为任意三角剖分都是两顶点符号的，我们能对a 中的每个顶点标记一1 或1 使 得没有一个三角形的三个顶点的符号完全一致令g 研( ) 定义为g ( o ) = w ， 此处w 是p 标记的符号令f ( x ，y ) ：= g ”醴( ) ，我们有r n r , g ，对所有的三角形胞腔霉 证毕 下面我们将给出一反例显示这一结论不能推广到任意样条函数空间群( ) 给一三 角形a b c 在其内部选择一点，记为0 1 连接0 1 和a ，b 与c 我们得到三个三角 形，o _ i a b ，0 _ 1 a c ，0 1 b c 这三角剖分记为筮对缱中的每一三角形，我们继续这一过程在m 步后，我们将 得到的三角剖分记为，根据二元样条函数空间一点处的维数公式我们知道若网 点v 的度为3 则d i m 趟( ( d ) ) = 6 由此，容易推出d i m 鼋( ：) = 6 因此，对任意m 昱( ) 等于昱显然。对足够大的 m ，代数曲线f ( x ，y ) = o ，v f ( e y ) 鼋( ) 不能与配中所有的三角形相交 上面给出的反例非常特殊因为g ( 畿) 对任意的吐一致 更一般地，我们对下述问题感兴趣： 问题2 2 1 若d i m 彤( ) n ，是否存在s ( x ，力e ( ) 、o 使得r n r , a ，1 s f n ， 此处n 为中三角形个数，f ：f ( x ，y ) = 0 7 该问题的解决有可能得到一方便的判断二元样条插值适定性的充分条件 众所周知，四色猜想是非常著名的公开问题下述定理显示了四色猜想与与分片代数 曲线之间的联系为了描述该定理我们首先介绍一些定义。对一三角形a b c ，假定三条边 的中点分边为a ，b o c ，那么三角形a b c 称为三角形a b c 的中位三角形，记为m ( a a b c ) 对三 角剖分a ，m ( a ) 定义为u 兰肘q ) 。三角剖分称为3 边符号的，如果能对的每条边标记 l ，2 或3 ，使得里任意三角形的三条边标记完全不同的符号，即：每一个三角形都不存在 两条边标记符号相同 定理2 2 1 四色猜想成立，当且仅当对任意的三角剖分，存在三条分片代数曲线 f 。：z ( x ，y ) = o ，z ( x ，j ，) 邵( ) ，i = 1 ，2 ，3 使得f l u r 2 u r 3 = 肘( ) 证明：通过图论知识，四色猜想成立当且仅当任意三角剖分是3 边符号的假定四色 猜想成立，我们可对的每条边标记1 ，2 或3 ，使得里任意三角形的三条边标记完全不 9 论文题目 同的符号令置为标记符号为i 的边的集合考虑q ( ) = ( y ，四e ) 显然q ( ) 是四边形 剖分和一些树的并集通过引理3 1 1 ，口( ) 中的每个顶点能够标记1 或一l 使得任意两个 相连顶点标记不同符号，将该标号方式记为m _ i 令ze 研( ) 由f _ i ( v ) - - w 定义，其中w 是 顶点v 在虻i 下的标号 显然u 3 l l f ，= m ( ) ，其中r ，：z ，y ) = o ，f ( x , y ) 邵( ) ，f = 1 ，2 ，3 假定对任意的三角剖分存在三条分片代数曲线f ，：z ( x ，y ) = o ，扣1 ，2 ，3 使得 u 乙。f ，= 肘( ) 考虑中的一个三角形t 因为u 3 - l l = m ( ) ，r 。n r 必定平行于t 的一 条边，设为e ( r ) 令e ( o = u ，e ( o ( r ) 显然中任一条边包含在u l e 中令e ( 中的 边标记数字i 容易看出，中任一三角形三条边标记符号都是完全不一致的因此，三 角剖分是3 边符号的，四色猜想成立证毕 2 3 分片代数曲线交点个数 这一节里我们主要介绍一些基本概念及文 2 2 中的主要结果 设d r2 是有界区域，用有限条不可约代数衄线将d 分成有限个小区域，从而产生 了对d 的一个剖分vu d ，称 r ( u ) = ( 艿cd ，u 占，占是d 的一个胞腔) 是v 的星形域通常地，称、，= ( x ，y ) d 为代数曲线p ( x ，y ) = 0 的，= 0 ( ，) l 重零点倘若 鼻- * p ( u ) = 0 ，f ，_ ，0 ，i + _ ，s ，一1 ，上l 榷i 和j ，i + j = r ，使得 口o 。 j i + 专子i 丁p ( u ) 0 倘若，p ( u ) 0 ，令，= ( p ) = 0 uo 。 设u = ( x ，y ) d 如果p ( v ) = q ( v ) = 0 ，且x 是结式r ( p ，q ) ( x ) 的r 重零点，则称代数 曲线p = o ，q - o 在v 处的相交重数为r 为方便起见，如果r _ v ( p ) - o 或r - v ( q ) = 0 ，定义r = 0 众所 周知，如下关系成立：7 0 ( p ) ( g ) ( p ，g ) s 棚疗，此处p ，q 分别为次数 uu 为r n ，n 的多项式，且没有公共分支 设fes ，( ) ，p = ( x ，y ) d ，r ( v ) 为v 的星形域，则称 ，= k ( ，) = m i nd 。月( 。) 0 ( p j ) ：p j = fi d ，j ) 为分片代数曲线f = 0 在点v 处的熏数 1 0 大连理工大学硕士学位论文 设f s ：- ( ) ，g s f t ( ) ，且，i d gf d 无公共分支，称 ，= r o ( ，g ) = m i n 。r ( 。) ，。( p 5 ，q 5 ) ：p # = ，1 5 ，qd =gl d ) 为分片代数曲 线f = 0 ，g = 0 在点v 处的相交重数容易看出，如下不等式成立： o ( 厂) o ( g ) 乙( j f ，g ) s mn n 若存在样条 s i ( ) 和 s ；，( ) 使得，= ，l 成立，f _ 1 不是常函数， 称f j = o 为f = o 的一个分支与代数曲线不同，两条分片代数曲线即使没有公共分支也可能 交点无限例如： ，c 工，y ，= 。x x - - 一y y , ，喜：三? 和 ，、f 膏一y ，若x 0 烈托2 13 x y ，若工 0 容易看出f ，ges ，( ) ，此处剖分为仅目a y t 线x = o 产生的剖分f = 0 ，g = 0 有无限 个交点，但却没有公共分支 令( ，g ) = 。l ( ，g ) 称 b n ( m ，r ；珂，f ；a ) = m a x ，g i n ( ，g ) ：，s ：( ) ，g s ：( ) ) 为s ：( ) 和s ：( ) 的b e z o u t 数显然，b n ( m ，；n ，f ；a ) mn n 文 2 2 中 考虑了b n ( m ，0 ；，l ，0 ；a ) 为介绍其工作，我们首先介绍相关的概念上一节曾经介绍 - i 2 顶点符号的定义一个三角剖分称为3 顶点符号的，如果中每个三角形都可用1 ，0 或一l 标号，使得同一三角形的三个顶点必须用l ，0 ，一1 标号称的内顶点v 为奇顶点，如 果过v 的剖分线有奇数条 定理2 3 1 设为三角剖分，当为2 顶点符号且衄为偶数；或为3 顶点符号 时： b n ( m , 0 ：n ，o ：a ) = m n n ，否则雪( 聊，o ； ，0 ；) 朋玎n 一【兰4 】，其 中，n 是中三角形的个甄矿。是中奇顶点个数特别地，当i i f n = 1 时有 定理2 3 2 当三角剖分为3 顶点符号时，b n ( 1 ，o ：1 ，o ：a ) _ n ：否则 b n ( 1 ，o ；1 ，o ；) 茎n 一【掣】 确实存在剖分使得口( 1 ，0 ；l ，0 ；) ：n 一 三班】成立，见下图2 3 ： 论文题目 图2 3 我们构造两个属于s ? ( ) 的样条函数f ，g 拜口g 在标记为i 的点上取值为 w ，= ( ，( d ) ，g ( u ) ) ，且l l = ( - 2 ，一2 ) ，w _ 2 = ( 2 ，1 ) ，w _ 3 = ( 1 ，2 ) ，叫2 ( 1 ，一2 ) ，w _ 5 = ( 2 一1 ) 和w - 6 = ( 屹，2 ) 容易看出f = o ，g ：o l 艮在三角形u u d ，上没有交点因此，等式成立 2 4 b e z o m 数b n ( m ，1 ；n ，1 ；a ) 为了给出任意三角剖分的b e z o u t 数上界，我们首先介绍几个引理 如果一个剖分仅仅由k 条平行直线所产生，那么这个剖分称为平行线剖分，记为& 图2 4 通过利用结式与一元样条函数的零点公式， 11 中得到如下结果： 引理2 4 1b n ( m ，r ；n ，q ；a ) ( k + 1 ) r a n - m i n ( r ，) 七 如果三角剖分中的每 t - - 角形都不是钝角三角形，那么这个三角剖分称为非钝三 角剖分利用结式与极坐标的方法， 2 1 给出了下述结果： 引理2 4 2 设为非钝三角剖分，v 为其中任一内顶点，则有 b n ( m ，1 ；n ，1 ；r ( u ) ) s d ( v ) m n 一( d ( u ) 一1 ) 用与上述定理证明类似的方法，可以得到 引理2 4 3 设为非钝三角剖分，v 为其中任一边界顶点，则有 b n ( m ，1 ；n ，l ；r ( u ) ) ( d ( 一1 ) m 疗一( d ( u ) 一2 ) 对非钝三角剖分，为了得割b n ( m ，1 ；n ，1 ；a ) 的上界，我们首先介绍一个组合优化问 题 1 2 躜 羞h 大连理工大学硕士学位论文 驰，= 黝：1 2 j 雪麓嚣瑶翥点脚删分内的一熊考虑d i t w 。1 d ( u ) 一，当p 是里的一个边界顶点阪。列剐刀凸利腻呆巧届 问题2 4 ir m n 。 ps j p i 菏足条件2 4 1 张4 i ( a ) 任一点均不落在剖分线上 ( b ) 对任顶点v ，落在r ( v ) 内点的数目不小于 ( c ) 落在任意相邻两三角形内点的数目不小于1 ( d ) 落在任一个三角形内的点数不超过m 对任意给定的三角剖分，问题2 4 1 的解为月沏，n ；a ) 我们有 定理2 4 1 对任意的非钝三角剖分a ，b n ( m ，1 ；n ，1 ；a ) 蔓m n n 一 毋( 研，塌) 证明：通过b e z o u t 数的定义，存在两条分片代数曲线 f l ：，( z ，力= o ，f 2 ：g ( x ，y ) = o ，f ( x ，y ) s ( ) ，g ( x ，y ) s i ( a ) 交点数目有限并且等 于b n ( m ，1 ；n ，i ；a ) 对三角剖分里的顶点与三