首页 | 本学科首页   官方微博 | 高级检索  
文章检索
  按 检索   检索词:      
出版年份:   被引次数:   他引次数: 提示:输入*表示无穷大
  收费全文   3篇
  免费   2篇
  国内免费   4篇
综合类   1篇
数学   8篇
  2023年   1篇
  2017年   3篇
  2015年   1篇
  2012年   2篇
  2011年   1篇
  2009年   1篇
排序方式: 共有9条查询结果,搜索用时 15 毫秒
1
1.
一个社会网络中通常包括具有正面影响和负面影响的两类人员,为了研究这个社会网络中人们之间相互影响的某些规律,引入了一个新的概念. 用划分图G=(V,E),V=V+ \cup V-表示这样的一个社会网络,其中V+和V- 分别表示正面人员的集合和负面人员的集合. 图G的一个点子集D\subseteq V-被称为G的一个正影响集,若G的每个点的至少一半的邻点在D\cup V+中. G的所有正影响集的最小基数称为G的正影响数. 给出G的正影响数的几个下界并证明了这些界是紧的. 此外,还证明了求正影响数问题在二部图和弦图上都是NP-完全的.  相似文献   
2.
首先给出了格的反软理想新概念,证明2个反软理想分别在软集的限制并和"或"运算下仍然是反软理想.其次,利用软集的反对偶给出反软理想的等价刻画.再次,利用软集的反扩张原理给出反软理想在同态映射下反像与原像的性质.最后,在全体反软理想组成的集合H上,引入链条件并讨论H是阿丁的或诺特的充要条件.  相似文献   
3.
研究两类广义控制问题的复杂性: k-步长控制问题和k-距离控制问题, 证明了k-步长控制问题在弦图和平面二部图上都是NP-完全的. 作为上述结果的推论, 给出了k-距离控制问题在弦图和二部图上NP-完全性的新的证明, 并进一步证明了k-距离控制问题在平面二部图上也是NP-完全的.  相似文献   
4.
The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D.In the present paper,by using a labeling method,we provide an O(m) time algorithm to solve the2-step domination problem on block graphs,a superclass of trees.  相似文献   
5.
A set D of vertices in a graph G = (V, E) is a locating-dominating set (LDS) if for every two vertices u, v of V / D the sets N(u) ∩D and N(v) ∩ D are non-empty and different. The locating-domination number γL(G) is the minimum cardinality of an LDS of G, and the upper-locating domination number FL(G) is the maximum cardinality of a minimal LDS of G. In the present paper, methods for determining the exact values of the upper locating-domination numbers of cycles are provided.  相似文献   
6.
Let G =(V, E) be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f:V∪E→ {-1, 1} such that ∑_(y∈N_m(x)∪{x})f(y)≥ 1for every element x∈V∪E, where N_m(x) is the set of elements of V∪E adjacent or incident to x. The weight of f is w(f) =∑_(x∈V∪E)f(x). The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.  相似文献   
7.
图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.  相似文献   
8.
美国数学家Bondy给出了一个非负整数序列为简单图的度序列的充要条件.本文对此进行了发展,证明了一个正整数序列为连通简单图的度序列的充要条件;然后在此基础上又探讨了平面图的低度点个数问题并定义了描述连通平面图的低度点个数的一个概念φ(n,m),并对某些低阶平面图求出了φ(n,m)的值.最后给出了φ(n,m)的上下界.  相似文献   
9.
$f: E(G)\rightarrow\{-1,1\}$称为图$G =(V,E)$的一个符号边控制函数 (简称SEDF),如果$f[e]=f(N[e])=\sum_{e''\in N[e]}f(e'')\geq1$对于图$G$的每条边$e\in E$都成立. $w(f)=\sum_{e\in E}f(e)$称为函数$f$的权. $G$的符号边控制数$\gamma_{s}\,''(G)$是指$G$的所有符号边控制函数的最小权.本文对完全多部图的符号边控制数进行研究.对于完全$r$-部图, 当$r$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界.  相似文献   
1
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号