共查询到20条相似文献,搜索用时 46 毫秒
1.
用矩阵方法讨论仿射超平面构形的可约性。通过证明仿射构形可约等价于对应的中心构形可约,把仿射构形因子分解存在惟一性归结为中心构形相应的已知结论,得到仿射超平面构形因子分解的存在惟一性。 相似文献
2.
讨论了中心构形的可约性。对超平面中心构形 构造了拟阵 ,在超平面构形和拟阵之间建立了对应关系。证明了中心本质构形 不可约当且仅当对应的拟阵 连通;且每一个超平面中心构形都可以分解成若干个不可约构形的乘积,并在不计因子次序意义下,这种分解是惟一的。 相似文献
3.
朱秉寰 《中山大学学报(自然科学版)》1991,30(2):39-45
证明了顶点的权为参数t的线性函数,尺寸为n的可外平面图的最小顶点复盖的耗费函数的折点个数囿界于O(n~(?)),且提出了一个时间复杂性为O(n~(?))的求解算法。 相似文献
4.
平面图3-可着色是指可用3种颜色对该图的顶点进行着色,使得相邻的顶点着不同的颜色.研究了平面图在长度不大于6的圈或长度不大于7的圈之间满足一定条件下是3-可着色的. 相似文献
5.
关于平面图3-可着色的一个定理 总被引:1,自引:0,他引:1
Borodin和Raspaud提出一个猜想:任何既没有5-圈也没有相邻三角形的平面图是3-可着色.这个猜想强化了Steinberg提出的猜想.在本文中,我们研究了没有5-,6-,9-圈并且没有相邻三角形的平面图的结构.利用这个结构,证明了这类图是3-可着色的.它加强了由Borodin及Sanders和Zhao的结果,并且又是对Borodin和Raspaud猜想的一个正面的支持. 相似文献
6.
程淑华 《湖南工程学院学报(自然科学版)》2008,18(2):44-47
研究了可约超平面中心构形因子分解的应用.得到了可约中心构形与其因子构形的麦比乌斯函数和庞加莱多项式之间的关系;并且利用线性代数的基本性质给出了构形超可解性的一个定理的证明:若中心构形A1,A2,L,Acc是超可解构形,那么它们的乘积构形A=A1×A2×L×Acc也是超可解的. 相似文献
7.
给G=(V,E)的每个顶点分配一个色列表L={L(v)|v∈V},若G有一个正常顶点染色φ,使得对每个顶点v∈V,都有φ(v)∈L(v),则称G是L可染的。若对G的每一个满足|L(v)|≥k,v∈V的L,G都是L可染的,则称G是k可选择的。本文通过权转移方法证明了每个不含4,6,8,10圈的可平面图是3可选择的。 相似文献
8.
图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长. 相似文献
9.
10.
平面图着色的遗传算法 总被引:6,自引:0,他引:6
洪斌 《贵州大学学报(自然科学版)》1999,16(4):297-302
基于遗传算法的思想 ,建立了一个用四种不同颜色对平面图结点进行着色的快速算法。 相似文献
11.
赵诚 《山东大学学报(理学版)》1988,(3)
本文得出几个平面图边可重构的结论:1.若 G 是平面图,δ(G)=4,且 G 没有次为5的点,则 G 是边可重构的。2.若 G 是平面图,δ(G)≥3,且 S_3为 G 中次为3的集合,又设 G—S_3为3连通的,G 无次为4的点。则 G 是边可重构的。 相似文献
12.
图G的一个分数染色是从G的独立集的集合ζ到区间[0,1]的一个映射c,使得对任意顶点x,都有∑s∈ζ,s,1 x∈s c(s)≥1,将此分数染色的值定义为∑s∈ζ c(s).图G的分数色数xf(G)是它的所有分数染色的值的下确界,讨论了几类平面图的分数色数。 相似文献
13.
图G的一条边e称为G的同构不动边,如果当且仅当e’=e.若e=uv是G的同构不动边,则对G—e的任一自同构映射。都有π({u,v})={u,v}文中证明了,除K3V(K1+K1;)外的极大平面图和除P2VK1,P3VK1外的2-连通外可平面图都含有同构不动边. 相似文献
14.
15.
本文研究了围长至少为5的平面图的线性着色问题。利用反证法,通过分析最小反例图的结构,运用欧拉公式结合适当的权转移规则得出矛盾,从而证明了围长至少为5的平面图的线性色数满足lc(G)≤[△(G)/2]+4,改进了这方面的结果。 相似文献
16.
吴建良 《山东大学学报(理学版)》1999,34(2):121-124
改进了一些边染色临界图的边数的下界.同时证明了:对没有4圈或任何两个3面都不同时关联于一个点的平面图,关于边染色的平面图猜想成立. 相似文献
17.
18.
特殊平面图的全染色 总被引:1,自引:1,他引:1
孙向勇 《山东师范大学学报(自然科学版)》2007,22(1):10-12
给定一个图G,G的全k染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一种颜色.图G的全染色数xT(G)是指使G全k染色的最小整数k.Δ(G)是G的最大度,本文对不含从4到k的圈,且3-圈不重点的平面图得出的结论有:如果(Δ,k)分别是(6,4),(5,5),(4,11),则G的全染色数是Δ 1. 相似文献
19.
由轮图出发构造了一类平面图,进而讨论了它们的一些基本性质和相互之间的同态关系,并得到了这些图的圆色数的精确值均介于2和3之间. 相似文献
20.
线性k-森林是指一个图G,它的每个连通分支是长至多为k的路.图G的线性k-荫度是指使得G可以边划分成m个线性k-森林的最小整数m,用lak(G)表示.本文探讨特殊平面图的线性二荫度,得到的结论有:1)每个3-圈不重边的平面图G,有la2(G)≤[△(G)/2]+10;2)每个3-圈不重点的平面图G,有la2(G)≤[△(G)/2]+7;3)每点至多关联[△(G)/2]个3-面的平面图G,有la2(G)≤[△(G)/2]+10. 相似文献