一个边着色定理

Berge曾给出一个边着色定理,下面为使用方便起见,我们不妨称它为B定理。著名的Vizing定理和另外一些边着色的结果都可以作为B定理的推论。我们叙述这个定理如下:B定理 设G是一个无环重图,[a,b]_0是G的一条边,令G′=G—[a,b]_0,若G′是可q-边着色的,且q≥d_G(a),q≥d_G(b);d_(G′)(x) m_(G′)(a,x)≤q,则G也可q-边着色。这里d_G(x)表示顶点x在图G中的次;m_(G′)(x,y)表示在图G′中以x和y为端点的边数;Γ_(G′)(x)表示顶点x在G′中的邻点集合。     

图的关联着色

文章综述了目的关联图以及关联图的一些性质,给出了关联着色已有的一些结果.     

图的关联着色

文章综述了图的关联图以及关联图的一些性质,给出了关联着色已有的一些结果。     

四色问题和五色定理

四色问题已借助于计算机获得解决,但是它的证明过程不是人力所能完成的.杨忠道教授1979年夏天在复旦大学讲学期间曾就五色定理的证明向数学系学生作了一个简明清晰的报告,从中可以学到如何用严格的数学手段去证明这一看来似乎较直观的问题的方法.现刊登如下,以飨读者.     

全着色边临界图的全色数

定义 对于简单图G(V,F),(?)e∈E(G),当 χ_T(G)>△(G)+1, χ_T(G-e)=△(G-e)+1时,则称G为全着色边临界图.其中厶(G)表示G的最大度,χ_T(G)表示G的全色数。 引理1 对图G(V,E)。(?)e∈E(G),若△(G)≥2,则 χ_T(G-e)≤χ_T(G)≤χ_T(G-e)+1。 定理1 若图G(V,E)是全着色边临界图,则 χ_T(G)=△(G)+2。     

从蒸鸡蛋羹谈起——物质的溶解度

有的朋友蒸出的鸡蛋羹内部有许多“蜂窝眼”、表面皱折不平。吃起来口感不细腻。这是什么原因呢,又如何蒸出色香味形俱佳的鸡蛋羹呢？     

一种图顶点着色DNA计算机模型

设计了一种专门用于求解图顶点着色的DNA计算机. 该计算机的主体是由一个可变温度的聚丙烯酰胺凝胶电泳构成. 可变温度的电泳由3部分组成, 分别为“解链区”、“非解区”和“解区”. 它们对应的可控温度分别为T_m1, T_m2和T_m3. 本文介绍了该计算机的基本结构与基本原理, 给出了存储库的构建方法, 特别讨论了编码问题, 并成功地对5个顶点的图给出了系统的生物操作与生化实验.     

N阶完全图K_N的t边着色

如果N阶完全图K_N的边用t种颜色着色,则K_N称为是t边着色的。图F_i,l≤i≤t的Ramsey数n(F_1,…,F_i)是这样的最小正整数,使得对于任意一个i边着色完全图K_n,都可以在其中找到某个子图F_i,它是用第i种颜色着色的。当F_1=     

关于两类图的色多项式

目前,只有为数很少的几类图有色多项式的计算公式,而对绝大多数图而言,计算色多项式仍是非常不方便的。本文为两大类图找到了色多项式的计算公式,并为寻找更多的色多项式的计算公式提供了一定的模式。这两大类图是:一条长为n的路P_n的补图(?)_n以及n圈的补图(?)_n。     

关于简单MCD图的一个定理

设S_n是n个顶点的没有两个等长圈的简单图的集合。如果对于S_n中的一个图G,S_n中不存在适合|E(G′)|>|E(G)|的图G′,则称其为简单最大圈分布图,简称简单MCD图(ma-     

Coates图的两个消去定理

本文旨在证明Coates图的两个消去定理,正如文献[1]中所表明的那样,把图论技术用到计算方法上是卓有成效的。 本文采用文献[2]中的一切符号与术语,只是各有向边的重量不必一定是数,可以是任意环(如多项式)之元,我们的讨论从推广文献[2]中定义3.2关于1-因子的概念开始。考察1-     

从细胞核的全能性谈起

分化之谜大家知道,受精卵起初只是一个细胞,可是当它经过无数次分裂,形成动物个体的时候,竟会分化出许许多多的细胞类型。有的成为长长的神经细胞,有的成为圆圆的血红细胞,它们之间不论在结构、组成,还是在功能等方面都迥然有异。这种现象虽已习以为常,丝毫没有稀奇之处,可是解释起来却困难重重,令人绞尽脑汁。现在不妨让我们运用分子生物学知识,对它作一番追究:生物性状差异的基础是化学物质的差异;化学物质有些是蛋白质,有些是由酶支配下形成的,而酶本身也是蛋白质;合成蛋白质需要核糖核酸做模板;去氧核糖核酸决定了核糖核酸的特异性;去氧…     

从擀面条谈起

三日入厨下,洗手做羹汤。未谙姑食性,先遣小姑尝。这是唐代诗人王建的《新嫁娘词》。写的是嫁过来的新媳妇,在第三天要下厨房做饭的习俗。这实际上是婆婆(即诗中的姑)对新媳妇的一次     

从里根患病谈起

1994年底,一则美国前总统里根患精神病的新闻不仅传遍美国,而且在欧洲和亚洲一些国家也成为要闻大炒特炒,一时间沸沸扬扬。 里根患的是什么精神病呢?他患的是阿尔茨海默氏病,临床上又称早老性痴呆。这是一种神经纤维受损变性而引发的精神病症,主要表现为痴呆。病人的大脑中一些神经原纤维(即阿尔茨海默氏神经原纤维)变性、增粗,呈现不规则弯曲、扭曲成螺旋形式缠绕结成球节状。另外还有神经     

从墙脚潮湿谈起——毛细现象与表面张力

墙脚潮湿的秘密。家住底楼的小张怎么也弄不明白,装修好不久的房子．内墙脚老是湿漉漉的!他凿开了墙脚．看见并没有水管之类的设施漏水．可墙内也是湿漉漉的,但却不知道这些水从哪里来？     

四色地图问题的解决

对任何平面地图着色,使得任何两个邻国都没有相同的颜色,只要四种颜色就够了。这个著名的猜测已经证明是真实的了,用的是一种依靠高速计算机的新的证明方法。     

鸟眼的四色颜色视觉

在鸟眼视网膜内,每一个锥细胞内段的远心端含有带色的油滴。所有入射光到达视色素前必先经过这些油滴。它们含有类胡萝卜素。长期以来,认为油滴对锥细胞起着一种滤色片的作用。近来,借各种电生理测量和化学抽提方法有力地证明,在鸽、鸡和穴乌的视网膜内存     

由一类图的着色导出的素数子集的分类

设P表示全体素数的集合,D(?)P。令G(Z,D)表示这样一个图:它的顶点集是全体整数的集合,两个顶点x和y之间有边连结当且仅当|x—y}∈D。Eggleton,Erds和Skilton等在文献中证明了:不论对任何素数子集D(?)P,图G(Z,D)的色数至     

比较偶图能量的两个定理

以一定方式给某些图一个偏序是人们常常研究的课题。文献[1]研究了某些图依支撑树数排序,文献[2]研究了依匹配多少排序,文献[3]研究了树依能量排序。此类问题不仅在理论上且在实际上有价值。如对图能量的研究在化学上可比较异构物的稳定性。     

极小n棱连通图的一个定理

D. R. Lick(J. Reine Angew. Math., 1972)首先证明:极小n棱连通图的最小度点数为n。W。Mader(Math。Ann。,1971)推广了上述结论,证明:极小n棱连通图至少有n 1个度n的点。本文推广了Mader的定理,证明了: