边着色路到完全图的嵌入

一、一个猜想设 P_n 为具有 n 个顶点的一条路,它的 n-1条边着上了不同的颜色,若这个着色能扩充为 n 个顶点的完全图 K_n 的一个正常的 x′(K_n)一边着色,则称边着色路 P_n 能嵌入于完全图.一般说来,设 G 是具有边色数 x′(G)的一个简单图,令 M(G)为 G 中所有满足以下性质的子图 H(?)G 的集合:存在 G 的一种正常的 x′(G)-边着色使得 H 的各条边具有不同的颜色.设 K_n 是 n 个顶点的完全图,把集合 M(K_n)简记为 M_n 于是我们一开始提出的问题“P_n 能否嵌入于完全图”等价于“P_n 是否属于 M_n”.     

从一道高考题看一类和式不等式证明的函数方法

1 原题的分析及解答 10年广东文科卷第21题原题如下: 已知曲线C_n:y＝nx~2,点P_n(X_n,y_n)(X_n>O,y_n>0)是曲线C_n上的点(n=1,2,…). (1)试写出曲线C_n在点P_n处的切线l_n的方程,并求出l_n与y轴的交点Q_n的坐标; (2)若原点0(0,0)到l_n的距离与线段P_n Q_n的长度之比取得最大值,试求点P_n的坐标(x_n,y_n);     

关于一个特殊六阶图与路和圈的联图的交叉数

Garey和Johnson证明了确定图的交叉数问题是一个NP-难问题.目前,已确定交叉数的图类并不多.本文证明了一个特殊6阶图与n个孤立点,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+n;cr(Q+P_n)=Z(6,n)+n+1及cr(Q+C_n)=Z(6,n)+n+3.     

一个五阶图与路、圈的联图的交叉数

目前已经确定的两个图的联图的交叉数结果较少.设H是由一个4圈及一个孤立点所构成的5阶图.研究了图H与路、圈的联图的交叉数,得到了cr(H+P_n)=Z(5,n)+[n/2]+l,cr(H+C_n):Z(5,n)+[n/2]+2,其中,P_n与C_n分别表示含n个顶点的路与圈.     

图的一般邻点可区别均匀边染色和均匀全染色

提出了一般邻点可区别均匀边染色和全染色的新概念,研究了路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全二部图K_(m,n)、2维平面网格图P_m×P_n的一般邻点可区别均匀边染色和全染色,具体给出这些图的一般邻点可区别均匀边染色和全染色指标.     

一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数

图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3.     

关于乘积图的二维带宽问题

给出一般乘积图的二维带宽的界，并解决一类乘积图的二维带宽问题．最后给出完全ｋ部图的二维带宽。     

关于Ramsey数r^＊（Cm^（≥）,Pn）

求Ramsey数的问题是图论中一个相当重要且难度较大的问题,并一直未获彻底解决。本文定义Ramsey数r(C_m~((≥)),P_n)为满足下述条件的最小整数:任何r(C_m~((≥)),P_n)阶简单图必含点数至少为m的圈C_m~((≥)),或其补图含P_n。这篇论文的主要结果就是求出r(C_m~((≥)),P_n)的精确值为:     

P_m×P_n的邻强均匀边色数

图G的一个k-正常着色满足相邻的点所关联的边的色集合不同,且任两色的边数之差不超过1称为G的k-邻强均匀边染色,图G邻强均匀边染色中最小的k称为图G的邻强均匀边色数.本文得到了P_m×P_n的邻强均匀边色数.     

(向量)R_n和(向量)G_n的有向优美性

优美图可用在图论中的某些H-分解问题中,很多人研究无向图的优美标号.研究有向优美标号,通过对阶数奇偶性的讨论,给出了n(≥2)阶有向路(向量)P_n和n(≥3)阶有向(向量)C_n圈是有向优美的充分条件.     

S_m∨P_n与S_m∨C_n的交叉数

本文研究与星图有关的联图的交叉数,得到了对任意的n≥1,当m=3,4,5时,星Sm与路P_n的联图的交叉数;以及对任意的n≥3,当m=3,4时,星S_m与圈C_n的联图的交叉数.     

几类图的Fractional星控制数

设G=(V,E)是一个无孤立点的图,一个实值函数f:E(G)→[0,1]若对所有的点u∈V(G),均有∑uv∈Ef(uv)≥1成立,则称f为图G的一个Fractional星控制函数.图G的Fractional星控制数定义为γ_(fs)(G)=min{∑uv∈Ef(uv)|f为图G的一个Fractional星控制函数}.研究了几类乘积图的Fractional星控制问题,给出了一些常见特殊图的Fractional星控制数,主要确定了积图P_m×P_n和C_m×P_n的Fractional星控制数.     

非连通图G_1uG_2及G_1uG_2uK_2的优美性

将k-优美图的概念进行了推广,引入了k～l 优美图及标号间距的概念,并以此为基础, 分别推出了一般情形下判定非连通图G_1 ∪G_2及G_1 ∪G_2 ∪K_2是优美图的两个充分条件;同时得出了图(C_3 ∨(?)_n)∪St(m)∪K_2是优美图,其中k、l 为自然数,l相似文献   

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,...,k}的G的一个正常边染色.用w_σ(χ)表示顶点χ关联边的颜色之和,即■,并称w_σ(x)为x关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为x′_Σ(G).现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

余数巧算

在整数的集合里,两个整数相除多半不能整除,必定要产生余数。数字较小时余数可直接求出,但数字较大,尤其是有乘积、乘方的数时余数的求法则很困难。如求199~(108)/13的余数,硬算是很难求出的。怎么办呢?我经过多次的实践、推理和验算,得出了求余数的一些灵巧     

“跳蛙问题”的推广

<正> 本文所指“跳蛙问题”,即第二十一届国际中学生数学竞赛试题的第6题.此题在[1]中已有一种解法.本文目的是将问题推广,并用一种新解法求得解答的普遍形式.一、问题的一般提法跳蛙问题.设 A_0A_1A_2…A_(m-1)A_mA′_(m-1)A′_(m-2)…A′_2A′_1是一个正2m 边形.一只青蛙从 A_0点开始跳跃.如果青蛙在任一个不是 A_m 的顶点,那么它可以跳向两个相邻顶点中的任一点,当它跳到 A_m 点时就停在那里.设 e_n(m)为经过 n 步到达 A_m 的不同的路的个数,试求 e_n(m).(注.一个 n 步路是指顶点的一个序列(P_0,P_1,…,P_n)满足:1) P_0=A_0,P_n=A_m;2)对每个 i,0≤i≤n-1,P_i(?)A_m;3)对每个 i,0≤i≤n-1,P_i 与     

求∑_(r=1)~(k 1)r~n的一种简单方法

关于求sum from r=1 to (r~n)的问题,初等数学只能用较繁琐的递推方法来解决。下面通过一串积分便可以得到一个较简单的求法。这里要用贝努利(Bernoulli)多项式序列{P_n(x)}_0~∞,它的定义是     

两个完全图的乘积的树宽

本文确定了乘积图Km×Kn的树宽.我们的结果是若m和n都是偶数,且m≥n,或m是奇数而n是偶数,或m和n都是奇数且n≥m,则Km×Kn的树宽是TW(Km×Kn)=n(m+1)/2-1.这恰好是图Km×Kn的带宽.     

树的线图的图扩充问题

图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题.     

求卡样板角度的正截面法

<正> 在平面体的板金工划线工作中,除了需要求出展开图外,还必须求出加工成形用的两面角,以便制造卡角样板.因此,求卡样板角度实际上就是在板金工划线工作中求两面角的问题.目前在实际工作中,求展开图和求两面角通常是各自按照投影放样图分别求解.这样,求两面角就往往不得不采用投影变换的方法,而且在一般情况下必须变换两次.实践证明,这种方法作图步骤较多,占地面积太大,不利于提高工效.在制件较大的情况