若干联图的L(2,1)-边染色算法

图的距离染色问题是频率分配问题的一种图模型,所谓的频率分配问题是指某一区域的不同电台要使用无线电波发送信号,为了避免干扰,位置较近的电台需要使用不同的频道,当电台距离特别近时,它们之间需要间隔至少2个信道。L(2,1)-边染色是指距离为1的两条边的色数差值大于等于2,距离大于1的两条边的色数不同。本文针对随机图设计了一种L(2,1)-边染色算法,实验结果表明,该算法能够解决有限点内随机图的L(2,1)-边染色问题。通过分析实验结果,发现了3类单圈图的染色特性,定义C_(3)↑P_(n)↑S_(m),C_(n)↓S_(m)和C_(n)↑S_(m)分别来刻画这三类单圈图,并给出相关定理及其证明。

拟梯子的L(2,1)-标号

图G的一个L(2,1)-标号就是从顶点集V(G)到非负整数集的一个函数f,使得d(u,v)=1时,有|f(u)-f(v)|≥2;当d(u,v)=2时,有|f(u)-f(v)|≥1,其中u,v是图G的顶点.不妨设最小标号为0.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)-标号下的跨度max{f(v);v∈V(G)}的最小数.本文定义了拟梯子,并完全确定了拟梯子的L(2,1)-标号数.

手镯图的L(2,1)—标号

为了更好地研究频道分配问题,引入了从顶点集到非负整数集的一个函数,即图的一个L(2,1)—标号。假设最小标号为零,图的L(2,1)—标号数就是此图的所有L(2,1)—标号下的跨度的最小数。对于路和圈的Cartesian积图的推广图——手镯图的标号数问题,给出了手镯图的定义,即是将拟梯子的两端重合而得到的图形,同时给出了其L(2,1)—标号数的定义,运用顶点分组标号法,根据圈的个数和每个圈的顶点数的不同进行分类讨论,研究结果完全确定了手镯图的L(2,1)—标号数的确切值,丰富了图的种类并完善了标号数理论。

连通度为k的图的L(2,1)-标号

通过找出图G的补图Gc的路覆盖数与其子图G-S的各个连通分支补图的路覆盖数间的关系,在图G的λ数与其补图Gc的路覆盖数之间关系的基础上,给出图G的λ数与子图G-S的各个连通分支补图的路覆盖数之间的关系(这里S是G的一个k-顶点割).

油水井控制中GM(2,1)优化模型参数和病态性的影响研究

研究了原始序列的数乘变换对油水井控制中 GM( 2 ,1 )模型参数和病态性的影响问题 ,建立了数乘变换值分别与 GM( 2 ,1 )模型系数矩阵条件数、模型参数间的量化关系式 ,得到了 GM( 2 ,1 )优化模型完全适用于负数据序列建模、原始序列的初值化或均值化等处理不会影响系统的预测精度和误差。

最大度至多为6的平面图的L(2,1)-标号

令Δ(G),g(G)和λ(G)分别为图G的最大度,围长,和L(2,1)-标号数.证明了若G是Δ(G)≤6和g(G)≥5的平面图,则λ(G)≤Δ(G)+13.进而关于Δ(G)≤6和g(G)≥5的平面图G,这个界要比先前的结果好.

若干圈的广义冠图的(2,1)-全标号(英文)

研究了与频率分配有关的一种染色问题:(2,1)-全标号,它是对图的全染色的一种推广,根据圈的广义冠图的构造特征,利用穷染法,给出了一种标号方法,得到了几类圈的广义冠图的(2,1)-全标号数.

关于图的L(2,1)-标号问题

图的L(2,1)-标号问题来自频率分配问题并且是NP-完全性问题.得到:(ⅰ)G是p个顶点的简单图,对正整数k≥3,当p≥2k2和Δ≥p/k时,有L(G)≤Δ2.(ⅱ)Δ(G)表示图G的最大度,则L(G)≥Δ(G)+1.Vi及Vi∩Vj= ,i≠j,则L(G)≤p+k-2.(ⅲ)若V(G)可划分为独立集V1,V2,…,Vk,且V(G)

路和圈的广义Mycielski图的L(2,1)标号

令G=(V(G),V(G))是一个简单图,Mp(G)为图G广义Mycielski图。图G的L(2,1)标号数,记作λ(G),定义为λ(G)=min{k|G有一个k-L(2,1)标号}。n个顶点的路、圈分别记作Pn,Cn。给出了路和圈的广义Mycielski图的L(2,1)标号数λ(Mp(Pn))和λ(Mp(Cn))。

一个圈与一个完全二部图的直积的L(2,1)-标号

通过分类讨论、归纳综合的方法,研究了一个圈与一个完全二部图的直积的L(2,1)-标号问题,得到了以下的结果:(1)当n≥3时,C3×Kn,n的L(2,1)-标号数为3n+1;当n≥3时,C4×Kn,n的L(2,1)-标号数的上界是4n;当n≥3时,C5×Kn,n的L(2,1)-标号数为5n-1;(2)当n≥3,m≥6,m≡0(mod3)时,Cm×Kn,n的L(2,1)-标号数为3n+1;当n≥3,m≥6,m≡1(mod3)或m≡2(mod3)时,Cm×Kn,n的L(2,1)-标号数的上界是4n.

一类广义Petersen图的(2,1)-全标号

图G=(V,E)的一个k-(2,1)-全标号定义为从集合V(G)∪E(G)到{0,1,2,…,k}的映射,使得任意两个相邻的点和相邻的边得到不同的标号,且任一对相关联的点和边得到的标号的差绝对值至少为2.G的(2,1)-全标号数是G的所有k-(2,1)-全标号中的最小的k值.得到了一类广义Petersen图的(2,1)-全标号数.

几类联图的L(2,1)-边染色算法研究

本文针对随机图设计了一种L(2,1)-边染色算法,实验结果证明,该算法能够解决有限点内随机图的L(2,1)-边染色问题。通过分析实验结果发现了5类联图的染色特性,定义■分别来刻画这5类联图,并给出了相关定理及证明。

一个路与一个完全图的直积的L(2,1)-标号

为了得到一个路Pm与一个完全图Kn的直积Pm×Kn的L(2,1)-标号数,通过归纳猜想,分类讨论,证明了m=3或4时,Pm×K3的L(2,1)-标号数为6,m≥5时,Pm×K3的L(2,1)-标号数为7,m≥5且n≥3时,Pm×Kn的L(2,1)-标号数的上界是3n-2.