检索结果-内蒙古大学图书馆

求图符号控制数的启发式算法

引用

计算机工程 2005年第1期31卷 41-44页

作者：陈卫东华南师范大学计算机系广州510631

针对具有NP难度的图符号控制数问题,沿着拟人的途径,制定了若干求解策略,给出了一个启发式算法即Local-Search-SDN算法。通过与完全算法的比较,实验结果表明Local-Search-SDN算法能快速找到问题的高质量解。

关键词：图符号控制数 NP难度拟人启发式算法

来源：评论

学校读者我要写书评

暂无评论

关于图的符号控制数的下界

引用

数学杂志 2002年第2期22卷 169-173页

作者：尹传勇毛经中韩娅玲秦前进华中师范大学数学系武汉430079 中国人民武装警察部队武汉指挥学校武汉430064

图的符号控制数的研究有许多应用背景 .但图的符号控制数的计算是NP完全问题 ,因而确定其上下界有重大意义 .本文在 [5 ]的基础上 ,引进了新参数δ (G) ,全面改进了 [5 ]所给出的符号控制数的下界 ,并给出了一些可达下界的图 .

关键词：图符号控制函数符号控制数

来源：评论

学校读者我要写书评

暂无评论

求图符号控制数的完全算法研究

引用

计算机工程与应用 2004年第24期40卷 45-47,53页

作者：陈卫东华南师范大学计算机系广州510631

确定图的符号控制数是NP-难度的问题。针对求解该问题的完全算法即能求得精确最优解的算法进行了研究,提出了几个启发式的限界策略,给出了两个完全算法:回溯算法和A算法。计算实验表明,针对随机产生的问题实例,用这两个算法求解时所生... 详细信息

确定图的符号控制数是NP-难度的问题。针对求解该问题的完全算法即能求得精确最优解的算法进行了研究,提出了几个启发式的限界策略,给出了两个完全算法:回溯算法和A算法。计算实验表明,针对随机产生的问题实例,用这两个算法求解时所生成的结点数目还不到其状态空间树中结点总数目的千分之五。对这两个算法也进行了比较。

关键词：图符号控制数 NP难度回溯法分枝定界法 A^*算法

来源：评论

学校读者我要写书评

暂无评论

两类乘积图的符号控制数

引用

河南科技大学学报（自然科学版） 2020年第2期41卷 94-98,M0008页

作者：徐保根张君霞李广华东交通大学理学院

设G=(V,E)是一个图,一个双值函数f:V→-1,+1,如果对任意顶点v∈V,均有∑u∈N[v]f(u)≥1成立,则称f为图G的一个符号控制函数。图G的符号控制数定义为γs(G)=min{∑v∈V f(v)f为图G的一个符号控制函数}。通过列举图例验证了以往研究中的... 详细信息

设G=(V,E)是一个图,一个双值函数f:V→-1,+1,如果对任意顶点v∈V,均有∑u∈N[v]f(u)≥1成立,则称f为图G的一个符号控制函数。图G的符号控制数定义为γs(G)=min{∑v∈V f(v)f为图G的一个符号控制函数}。通过列举图例验证了以往研究中的部分结果是错误的,并重新确定了两类乘积图Cn×P3和Pn×P3的符号控制数。

关键词：图控制数乘积图符号控制数

来源：评论

学校读者我要写书评

暂无评论

完全图全符号控制数的较小上界和下确界

引用

数学的实践与认识 2005年第8期35卷 184-187页

作者：王继顺王莲花王治文吕新忠张忠辅兰州交通大学应用数学研究所甘肃兰州730070

设图G=G(V,E),令函数f∶V∪E→{-1,1},f的权w(f)=∑x∈V∪Ef[x],对V∪E中任一元素,定义f[x]=∑y∈NT[x]f(y),这里NT[x]表示V∪E中x及其关联边、邻点的集合.图G的全符号控制函数为f∶V∪E→{-1,1},满足对所有的x∈V∪E有f[x]1,图G的全符... 详细信息

设图G=G(V,E),令函数f∶V∪E→{-1,1},f的权w(f)=∑x∈V∪Ef[x],对V∪E中任一元素,定义f[x]=∑y∈NT[x]f(y),这里NT[x]表示V∪E中x及其关联边、邻点的集合.图G的全符号控制函数为f∶V∪E→{-1,1},满足对所有的x∈V∪E有f[x]1,图G的全符号控制数γT(G)就是图G上全符号控制数的最小权,称其f为图G的γT-函数.本文得到了完全图全符号控制数的一个较小上界和下确界.

关键词：完全图全符号控制数上界下确界符号控制数符号控制函数图G 最小权集合邻点

来源：评论

学校读者我要写书评

暂无评论

特殊图类的符号控制数

引用

纯粹数学与应用数学 2005年第1期21卷 59-61页

作者：王军秀安徽工业大学数理系安徽马鞍山243002

图G的符号控制数γS(G)有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其上下界有重要意义.本文研究了1)一般图G的符号控制数,给出了一个新的下界;2)确定了Cn图的符号控制数的精确值.

关键词：符号控制函数符号控制数 Cn图

来源：评论

学校读者我要写书评

暂无评论

两类乘积图的符号控制数

引用

广西大学学报（自然科学版） 2017年第6期42卷 2253-2257页

作者：李宁范英梅广西大学数学与信息科学学院广西南宁530004

为了把符号控制数γs(G)=min{ω(f)|f是图G的一个符号控制函数}的概念应用到更多的图类中,扩大符号控制数的研究范围。以笛卡尔乘积图为例,通过对笛卡尔乘积图的顶点数进行数学归纳递推、对最小的符号控制函数的函数值进行反证假设,得... 详细信息

为了把符号控制数γs(G)=min{ω(f)|f是图G的一个符号控制函数}的概念应用到更多的图类中,扩大符号控制数的研究范围。以笛卡尔乘积图为例,通过对笛卡尔乘积图的顶点数进行数学归纳递推、对最小的符号控制函数的函数值进行反证假设,得到了圈图和路图的两类笛卡尔乘积图的符号控制数。研究结果得出:(1)n≥3时,笛卡尔乘积图C_n□P_3的符号控制数为n+2■n/3」;(2)n≥3时,笛卡尔乘积图C_n□C_3的符号控制数为n。

关键词：乘积图符号控制数圈路

来源：评论

学校读者我要写书评

暂无评论

图的符号控制数

图的符号控制数

引用

作者：周颖安庆师范大学

学位级别：硕士

图的控制理论的发展丰富了图论中的最优化问题.本文主要通过对图的符号控制数性质的研究,得到图的符号控制数及一些特殊情况下图的符号控制数的上下界,给出一些图的笛卡尔积的符号控制数和图的符号k-控制数.首先主要介绍本文要用到的图... 详细信息

图的控制理论的发展丰富了图论中的最优化问题.本文主要通过对图的符号控制数性质的研究,得到图的符号控制数及一些特殊情况下图的符号控制数的上下界,给出一些图的笛卡尔积的符号控制数和图的符号k-控制数.首先主要介绍本文要用到的图论中的一些符号,基本概念和定义,一些基本结论与引理.其次用符号控制数的相关定义与引理,确定图的符号控制数的一些上、下界,图的符号控制数与最大度、最小度的关系以及一些特殊图的符号控制数.我们还讨论乘积图的符号控制数,如路与路的笛卡尔乘积的符号控制数.最后我们介绍图的符号K-控制数的概念与相关引理结论,并讨论符号k-控制数的一些上界.

关键词：符号控制数笛卡尔积符号K-控制数

来源：评论

学校读者我要写书评

暂无评论

图的符号控制数

图的符号控制数

引用

作者：杜娟山西大学

学位级别：硕士

设G=(V(G),E(G))是一个简单图.对V(G)中的任意一顶点υ赋值f(υ),其中.f(υ)∈{-1,+1}.设N(υ)是顶点υ的邻域,记N[u]=N(v)∪{u}.令如果对任意u∈V(G),f[u]≥1均成立,则称/是G的一个符号控制函数.记图G的符号控制数γs(G)=min{f(V(G))|f是G的符号控制函数}.满足f(V(G))=γs(G)的一个符号控制函数.f称为G的一个最小符号控制函数.Wn是指由一个长为n的圈和一个孤立点υ。组成的图,并且圈上所有的顶点都和υ。相邻.称Wn为轮图,称v0为轮Wn的中心点.本文主要研究图的符号控制数,共分为三章.第一章主要介绍了一些将要用到的图论方面的基本概念.第二章给出了图的符号控制数的下界.结果如下：对任意n阶图G,△和δ分别是图G的最大度和最小度,则有第三章给出了两类特殊图的符号控制数.结果如下：(1)设y(n,m)={G| G为n个轮Wm的拷贝,且这n个轮Wm有且仅有一个非中心公共点}.则有(2)设H(n,m)={G| G为n个轮Wmn的拷贝,且这n个轮Wm有且仅有一条公共边}.则有γs(H(n,m))=(m-1-2[m/3J)n+2.

关键词：轮图符号控制函数符号控制数最小符号控制函数

来源：评论

学校读者我要写书评

暂无评论

平面图的诱导圈符号控制数问题

平面图的诱导圈符号控制数问题

引用

作者：刘晓艳华东师范大学

学位级别：硕士

设G=(V,E)是一个简单图,定义函数f：E→{-1,+1}.如果G的任意一个诱导圈C都满足f(C)=∑e∈E(C)f(e)≥1,则称f为图G的诱导圈符号控制函数(signed cycle domination function),简记为SCDF.同时定义γ'SC(G)=min{f(G)|f是G的一个SCDF}为图G的诱导圈符号控制数(signed cycle domination number). 本文主要研究了极大平面图,2-连通平面图和最小度为3的图的诱导圈符号控制数.主要结果如下： (1)设G(|V(G)|= n)是一个极大平面图,γ'SC(G)=n-2当且仅当它的所有诱导圈都是C3. (2)设G(|V(G)|= n)是一个极大平面图,γ'SC(G)≥n当且仅当G有一个诱导圈Ck,其中k≥4. (3)若G是一个2-连通平面图,则γ'SC(G)≥1. (4)任意δ(G)=3的图G,若γ'SC(G)有常数下界,则γ'SC(G)≥2. 上述关于极大平面图的结果,否定了徐宝根在[On signed cycle domination in graphs, Discrete Math.309 (2009) 1007-1012]中的一个猜想.

关键词：控制集符号控制数诱导圈符号控制数平面图极大平面图

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：