共查询到20条相似文献,搜索用时 93 毫秒
1.
Pm×Kn的邻点可区别全色数 总被引:6,自引:0,他引:6
设G是简单图.设f是一个从V(G)∪E(G)到{1,2,…,k}的映射.对每个v∈V(G),令C_f(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是k-正常全染色,且对任意u,v∈V(G),uv∈E(G),有C_f(u)≠C_f(v),那么称f为图G的邻点可区别全染色(简称为k-AVDTC).数x_(at)(G)=min{k|G有k-AVDTC}称为图G的邻点可区别全色数.本文给出路P_m和完全图K_n的Cartesion积的邻点可区别全色数. 相似文献
2.
设G(V,E)是简单连通图,k是正整数,若V∪到{1,2,3,…,k}的映射f满足对任意uv∈E(G),有f(U)≠f(v),f(u)≠f(uv)f(v)≠f(uv),且C(u)≠C(v),其中C(u):{f(u)}∪{f(uv)|uv∈E(G)}.那么称f为G的k-邻点可区别的E-全染色(简记为k-AVDETC),并称X_(at)~e(G)=min{k|G有k-邻点可区别的E-全染色}为G的邻点可区别的E-全色数.本文讨论了路、圈、扇、星、轮及完全图的Mycielski图的邻点可区别E-全染色,得到了该类图的邻点可区别的E-全色数. 相似文献
3.
联图Fn∨Pm的邻点可区别全染色 总被引:6,自引:0,他引:6
设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…k}的映射f满足:对任意uv,uw∈E(G),u≠w,有f(uv)≠f(vw);对任意uv∈E(G),有f(u)≠f(v), f(u)≠f(uv),f(v)≠f(uv);那么称f为G的k-正常全染色,若f还满足对任意uv∈E(G),有G(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)}那么称f为G的k-邻点可区别的全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别的全染色}为G的邻点可区别的全色数,记作Xat(G).本文得到了联图Fn∨Pm的全色数. 相似文献
4.
G(V,E)是一个简单图,k是一个正整数,f是一个V(G)∪E(G)到{1,2,…,k}的映射.如果(V)u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.给出了轮与路间的多重联图的邻点可区别E-全色数,其中C(u)={f(u)}∪ {f(uv)|uv∈E(G)}. 相似文献
5.
设G为简单图.G的全k-染色是指k种颜色1,2,…,k对图G的全体顶点及边的一个分配.设c是图G的一个全k-染色,任意的x∈V(G),称■为点x的扩展和,其中N(x)={y∈V(G)|xy∈E(G)}.称图G的全k-染色c为邻点被扩展和可区别(简记为NESD),如果w(x)≠w(y),其中xy∈E(G).使得图G存在NESD全k-染色的最小值k被称为图G的邻点被扩展和可区别全色数,简记为egndi_∑(G).本文利用数学归纳法探讨了仙人掌图的邻点被扩展和可区别全染色,并证明了这类图的邻点被扩展和可区别全色数不超过2.该结论说明Flandrin等人提出的NESDTC猜想对于仙人掌图是成立的. 相似文献
6.
设G(V,E)是简单图,k是正整数.从V(G)∪E(G)到{1,2,…,k}的映射f被称作G的邻点可区别-点边全染色,当且仅当:■uv∈E(G),f(u)≠f(uv),f(v)≠f(uv),■uv∈E(G),C(u)≠C(v),且称最小的数k为G的邻点可区别-点边全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数. 相似文献
7.
轮与星的多重联图的邻点可区别E-全染色 总被引:1,自引:1,他引:0
G(V,E)是一个简单图,k是一个正整数,f是一个V(G)UE(G)到{1,2,…,k}的映射.如果■u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.给出了轮与星的多重联图的邻点可区别E-全色数. 相似文献
8.
设f:V(G)∪E(G)→{1,2,…,k}是简单图G的一个正常k-全染色.令C(f,u)={f(e):e∈N_e(u)},C[f,u]=C(f,u)∪{f(u)},C_2[f,u]=C(f,u)∪{f(x):x∈N(u)}∪{f(u)}.N(u)表示顶点u的邻集,N_e(u)表示与顶点u的相关联的边的集合.令C[f;x]={C(f,x);C[f,x];C_2[f,x]},对任意的xy∈E(G),G[f;x]≠C[f;y]表示C(f,x)≠C(f,y),C[f,x]≠C[f,y],C_2[f,x]≠C_3[f,y]同时成立.对任意的边xy∈E(G),如果有C[f;x]≠C[f;y]成立,则称f是图G的一个k-(3)-邻点可区别全染色(简记为(3)-AVDTC).图G的(3)-邻点可区别全染色中最小的颜色数叫做G的(3)-邻点可区别全色数,记为x_((3)as)″(G).研究了联图,完全二部图的(3)-邻点可区别全染色,得到了它们的(3)-邻点可区别全色数. 相似文献
9.
设G(V,E)是简单连通图,T(G)为图G的所有顶点和边构成的集合,并设C是k-色集(k是正整数),若T(G)到C的映射f满足:对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),并且C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.那么称f为图G的邻点可区别E-全染色(简记为k-AVDETC),并称χ_(at)~e(G)=min{k|图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M(G)就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数. 相似文献
10.
强会英 《数学的实践与认识》2012,42(7):244-249
对简单图G(V,E),存在一个正整数κ,使得映射f:V(G)U E(G)→{1,2…,κ},如果对uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的邻点可区别VE-全染色,且称最小的数κ为图G的邻点可区别VE-全色数,讨论了路、圈、星、扇、轮等一些图的倍图与Mycielski图的邻点可区别VE-全色数。 相似文献
11.
Smarandachely邻点可区别全染色是指相邻点的色集合互不包含的邻点可区别全染色,是对邻点可区别全染色条件的进一步加强。本文研究了平面图的Smarandachely邻点可区别全染色,即根据2-连通外平面图的结构特点,利用分析法、数学归纳法,刻画了最大度为5的2-连通外平面图的Smarandachely邻点可区别全色数。证明了:如果$G$ 是一个$\Delta (G)=5$ 的2-连通外平面图,则$\chi_{\rm sat}(G)\leqslant 9$ 。 相似文献
12.
13.
14.
15.
16.
设$ G $ 是一个$ n $ 阶$ k $ 圈图, $ k $ 圈图为边数等于顶点数加$ k-1 $ 的简单连通图。$ \mu_{1}(G) $ 、$ \mu_{2}(G) $ 分别记为图$ G $ 的Laplace矩阵的最大特征值和次大特征值, 图$ G $ 的Laplace分离度定义为$ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $ 。本文研究了给定阶数的$ k $ 圈图的最大Laplace分离度, 并刻画了相应的极图, 其结果推广了已有当$ k=1, 2, 3 $ 时的结论。 相似文献
17.
设$ G $ 是一个$ n $ 阶$ k $ 圈图, $ k $ 圈图为边数等于顶点数加$ k-1 $ 的简单连通图。$ \mu_{1}(G) $ 、$ \mu_{2}(G) $ 分别记为图$ G $ 的Laplace矩阵的最大特征值和次大特征值, 图$ G $ 的Laplace分离度定义为$ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $ 。本文研究了给定阶数的$ k $ 圈图的最大Laplace分离度, 并刻画了相应的极图, 其结果推广了已有当$ k=1, 2, 3 $ 时的结论。 相似文献
18.
研究了单位$l_{\infty}$ 范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$ , 支撑树$T^0$ , 下界向量$\bm{l}$ , 上界向量$\bm{u}$ 及数值$K$ , 寻求一个新的边权向量$\bm{\bar{w}}$ 满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$ , 且$T^0$ 是在向量$\bm{\bar{w}}$ 下权值为$K$ 的一个最小支撑树, 目标是在单位$l_{\infty}$ 范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$ 最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$ 的强多项式时间算法。 相似文献
19.
研究了单位$l_{\infty}$ 范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$ , 支撑树$T^0$ , 下界向量$\bm{l}$ , 上界向量$\bm{u}$ 及数值$K$ , 寻求一个新的边权向量$\bm{\bar{w}}$ 满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$ , 且$T^0$ 是在向量$\bm{\bar{w}}$ 下权值为$K$ 的一个最小支撑树, 目标是在单位$l_{\infty}$ 范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$ 最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$ 的强多项式时间算法。 相似文献
20.
本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$ 台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$ 为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$ 为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$ 时, 该算法近似比为3, 当接受工件个数小于$(m-1)$ 时, 该算法近似比为$(2+\rho)$ , 其中$\rho$ 为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。 相似文献