搜索结果: 1-6 共查到“组合数学 圈”相关记录6条 . 查询时间(0.219 秒)
超图嵌入带权重圈的一个2-近似算法
最小阻塞 超图嵌入 带权圈 近似算法
2009/11/25
超图嵌入带权圈(HEWC)问题就是把超图的超边以路的形式嵌入一个带权圈, 使得圈上任何带权连接边的最大阻塞最小。这个问题的一个简单形式是图嵌入带权圈(GEWC),即把普通图的边以路的形式嵌入 一个带权圈。HEWC问题第一次被归结为一个整数线性规划问题,并且利用LP的放松问题和有界启发得到一个近似解。 然后设计了一个非常简单有用的可以和LP近似算法得到一样好的近似解的线性时间近似算法。
一类恰含三个圈的三色有向图的本原指数
三色有向图 本原指数 极图刻划
2009/11/20
一个三色有向图D是本原的,当且仅当存在非负整数h、k和v, 且h+k+v>0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,v)途径, 称h+k+v的最小值为D的本原指数。 本文研究一类特殊的三色有向图,其未着色图恰含一个n-圈、一个(n-1)-圈和一个2-圈, 给出了本原条件和本原指数上界, 并对本原指数上界的极图进行了刻划。
路和圈上的锥的D(2)-点可区别正常边染色
D(2)-点可区别的正常边染色 D(2)-点可区别的正常边色数 图上的锥
2009/11/19
设G是顶点集合为V(G)=｛v0i|i=1,2,…,p｝的简单图,n是正整数, 称Mn(G)为G上的锥(或广义Mycielski图),如果 V(Mn(G))=｛v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp,w｝, E(Mn(G))=E(G)∪｛vijv(i+1)k|v0jv0k∈E(G), 1≤j, k≤p,i=0,1,…,n-1｝∪｛vnjw|1≤j≤p...
单圈图的解析(英文)
单圈图 界 解析
2009/11/2
得到了一些特殊图类的解析值.~利用数学归纳和分类讨论的方法,~%
给出固定阶数的单圈图的解析的紧的界.~%
证明了在所有阶数为~$n$~的单圈图中,~%
图~$\Delta_{n-3}$~取得最小的~$a(G)$~和~$b(G)$;~图~$K_{1,n-1}^{+}$~%
取得最大的~$a(G)$~和~$b(G)$.~%
这里图~$\Delta_{n-3}$~是由联结~$K_{3}$~一...