内部节点受限的最小生成树问题算法研究

研究内部节点受限的最小生成树问题：给定一个赋权无向完全图[G=V,E],假定[w:E→R+]为边集[E]的权重函数且满足三角不等式,给定点集[V]的一个子集[RR?V],目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小的生成树。由于该问题是[NP-]困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。     

关于图的分数k-因子存在性的一些结果

设g(x)≤f(x)是定义在V(G)上的两个整数值函数,h(e)∈[0,1]是定义在图G的边集E(G)上的函数。令dGh(x)=移e∈Exh(e),其中Ex={xy:xy∈E(G)}。若对所有的x∈V(G)都有g(x)≤dGh(x)≤f(x)成立,称h是G的一个(g,f)-表示函数。Gh是图G的一个支撑子图使得E(Gh)={e:e∈E(G),h(e)≠0},则称Gh是G的一个分数(g,f)-因子。文章给出,若对V(G)中的任意两个顶点u和v,G-{u,v}有分数k-因子存在。则G有一个分数k-因子不含图G中任意给定的边e∈E(G);当G有分数1-因子F=Gh存在时,对任意e∈F,G-V(e)有分数k-因子存在,则G有分数k-因子。     

极大限制边连通网络的充分条件

限制边连通度是度量网络可靠性的重要参数。设[G]是一个边集为[E]的连通网络。称一个边集合[S?E]是一个限制边割,如果[G-S]是不连通的且每个分支至少有两个顶点。网络[G]的限制边连通度,记为[λ'],定义为[G]的最小限制边割的基数。设[d(v)]表示顶点[v]的度,[ξ=min{d(u)+d(v)-2:uv∈E}]表示[G]的最小边度。称网络[G]是极大限制边连通的,如果[λ'=ξ]。给出了网络是极大限制边连通的一些充分条件。     

(0,mf-m+1)图的正交(0,f)因子分解

设G是一个图,f是定义在V(G)上的整数值函数,且对坌x∈V(G),有2k≤f(x),设H1,H2,…,Hk是G的k个顶点不相交的子图,且|E(Hi)|=m,1≤i≤k,证明了每个(0,mf-m+1)图有一个(0,f)因子分解正交于Hi(i=1,2,…,k)。     

图的极小顶剖的有效枚举算法

设G=(V,E)是无向连通单图,S为G的一个顶子集,G[S]为S的导出子图。若G[V-S]不连通,则称S为G的一个顶剖;若S是G的顶剖,而S的任意真子集都不是G的顶剖,则称S为G的一个极小顶剖。a,b为G中任意两个不相邻的顶,若a,b分别处在G[V-S]的不同连通片中,则称S是G的一个(a,b)顶剖;若S是G的(a,b)顶剖,而S的任意真子集都不是G的(a,b)顶剖,则称S为G的一个极小的(a,b)顶剖。枚举图中所有极小(a,b)顶剖和所有极小顶剖是图论中的一个基本枚举问题,这个问题在网络的可靠性分析和运筹学等方面有着极大的应用价值,已     

联图[K1,1,3∨Cn]的交叉数

联图[G∨H]表示将[G]的每个顶点与[H]的每个顶点连边得到的图。在Klesc给出的联图[K1,1,2∨Cn]的交叉数为[Z(4,n)+n2+3]的基础上,根据联图的相关性质,运用反证法和排除法,得到了联图[K1,1,3∨Cn]与[{K1,1,3+e}∨Cn]的交叉数均为[Z(5,n)+n+n2+4]。并假设在Zarankiewicz猜想成立的前提下,提出对[K1,1,m∨Cn(m≥4)]的交叉数的一个猜想：[cr?(K1,1,m∨Cn)≥Z(m+2,n)+m+12m2n2+m2m-12n2+][m+1,m≥4]。     

I形图的并的匹配等价图数

两个图[G]和[H]的匹配多项式相等,则称它们匹配等价。用[δ(G)]表示图[G]的所有不同构的匹配等价图的个数。[In(n6)]表示由路[Pn-4]的两个端点分 别粘接一个[P3]的2度点后得到的图。计算了一些[I]形图并图的匹配等价图的个数,即[δi∈AIi],这里[A]是一些大于等于6的整数组成的可重集。     

图的分数[a,b]-因子存在的一个条件

图G的孤立韧度定义为I(G)=min｛｜S｜/i(G-S):S!V(G),i(G-S)≥2｝,若G不是完全图;否则,令I(G)=∞。论文给出了图的分数[a,b]-因子的存在性与图的孤立韧度的关系。证明若δ(G)≥I(G)≥a-1+a/b,则图G有分数[a,b]-因子,其中a相似文献   

图与子图的概念

<正> 定义1: 图G是由一个非空集合V={v_i}及V中元素的无序对的一个集合E={e_k}所构成的二元组(V_1E)。 V中的元素v_i,称为顶点。 E中的元素e_k称为边。 举例:图1中的图G,顶点v_1,v_2……,v_5     

边故障[k]元[n]立方体的超级哈密顿交织性

[k]元[n]立方体（记为[Qkn]）是优于超立方体的可进行高效信息传输的互连网络之一。[Qkn]是一个二部图当且仅当[k]为偶数。令[G[V0,V1]]是一个二部图,若（1）任意一对分别在不同部的顶点之间存在一条哈密顿路,且（2）对于任意一点[v∈Vi],其中[i∈{0,1}],[V1-i]中任意一对顶点可以被[G[V0,V1]-v]中的一条哈密顿路相连,则图[G[V0,V1]]被称为是超级哈密顿交织的。因为网络中的元件发生故障是不可避免的,所以研究网络的容错性就尤为重要。针对含有边故障的[Qkn],其中[k4]是偶数且[n2],证明了当其故障边数至多为[2n-3]时,该故障[Qkn]是超级哈密顿交织图,且故障边数目的上界[2n-3]是最优的。     

混合图的H-Estrada指标

混合图的Hermitian邻接矩阵是共轭矩阵,其全体特征值称为混合图的H-谱。借助该矩阵的许多性质能更有效地研究混合图。基于H-谱引出混合图的一个重要拓扑指标--H-Estrada指标。拟用数学分析的方法,对其性质做数理研究。     

给定匹配数的单圈图的最小值

图[G]的广义Randic指标定义为[Rα（G）=uv∈E（G）（dudv）α],其中[α]为任意实数,[du]为顶点[u]的度。顶点数等于边数的简单图称为单圈图。在匹配数等于边数的情况下,通过分类讨论,给出当[-1.39≤a≤-1]时,相应单圈图的广义Randic指标的最小值,并给出相应的结构图。     

直径为4的整树新类

整图是指图的邻接矩阵的特征值全为整数的图。研究了直径为4的整树。通过求某些特定的丢番图方程,构造了具有无穷多个这样的整树新类。     

随机图的点可区别V-全染色算法

图[G]的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求所有顶点的色集合也不相同,所用的最少颜色数称为图[G]的点可区别V-全色数。根据点可区别V-全染色的约束规则,设计了一种启发式的点可区别V-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果,对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明,该算法有很好的执行效率并可以得到给定图的点可区别V-全色数,并且算法的时间复杂度不超过[O(n3)]。     

Structure Indicators for Transportation Graph Analysis I: Planar Connected Simple Graphs

The paper deals with the representation of a transportation infrastructure by a planar connected simple graph and aims at studying its features through the analysis of graph properties. All planar and connected graphs with 4 up to 7 edges are analysed and compared to extract the most suitable parameters to investigate some network features. Then, a set of 41 graphs representing some actual underground networks are also analysed. Besides, as a third scenario, the underground network of Milan, along its development in years, is proposed in order to apply the proposed methodology. Many parameters are taken into consideration. Some of them are already discussed in literature, such as the eigenvalues and gaps of adjacency matrix or such as the “classical” parameters α, β, γ. Others, such as the first two Betti numbers, are new for these applications. In order to overcome the problem of comparing features of graphs with different size, the normalisation of these parameters is considered. Some relationships between Betti numbers, eigenvalues, and classical parameters are also investigated. Results show that the eigenvalues and gaps of the adjacency matrix well represent some features of the graphs while combining them with the Betti numbers, a more significant interpretation can be achieved. Particularly, their normalised values are able to describe the increasing complexity of a graph.     

Partial orders and Jordan normal form

Consideration is given to the relation between the structure of the acyclic binary relation and the adjacency matrix of its corresponding graph. In this case, the existing methods for studying the binary relations and their corresponding graphs in terms of the spectrum, that is, the set of eigenvalues, of the adjacency matrix are inapplicable because for the acyclic relations this matrix is nilpotent and its spectrum is identically zero. Therefore, a more refined characteristic of the matrix is required. The present paper considers the Jordan normal form (JNF) as such.     

Characterization of quantum circulant networks having perfect state transfer

In this paper we answer the question of when circulant quantum spin networks with nearest-neighbor couplings can give perfect state transfer. The network is described by a circulant graph G, which is characterized by its circulant adjacency matrix A. Formally, we say that there exists a perfect state transfer (PST) between vertices ${a,b\in V(G)}$ if |F(τ) _ab | = 1, for some positive real number τ, where F(t) = exp(i At). Saxena et al. (Int J Quantum Inf 5:417–430, 2007) proved that |F(τ) _aa | = 1 for some ${a\in V(G)}$ and ${\tau\in \mathbb {R}^+}$ if and only if all eigenvalues of G are integer (that is, the graph is integral). The integral circulant graph ICG _n (D) has the vertex set Z _n = {0, 1, 2, . . . , n ? 1} and vertices a and b are adjacent if ${\gcd(a-b,n)\in D}$ , where ${D \subseteq \{d : d \mid n, \ 1 \leq d < n\}}$ . These graphs are highly symmetric and have important applications in chemical graph theory. We show that ICG _n (D) has PST if and only if ${n\in 4\mathbb {N}}$ and ${D=\widetilde{D_3} \cup D_2\cup 2D_2\cup 4D_2\cup \{n/2^a\}}$ , where ${\widetilde{D_3}=\{d\in D\ |\ n/d\in 8\mathbb {N}\}, D_2= \{d\in D\ |\ n/d\in 8\mathbb {N}+4\}{\setminus}\{n/4\}}$ and ${a\in\{1,2\}}$ . We have thus answered the question of complete characterization of perfect state transfer in integral circulant graphs raised in Angeles-Canul et al. (Quantum Inf Comput 10(3&4):0325–0342, 2010). Furthermore, we also calculate perfect quantum communication distance (distance between vertices where PST occurs) and describe the spectra of integral circulant graphs having PST. We conclude by giving a closed form expression calculating the number of integral circulant graphs of a given order having PST.     

图同构的矩阵初等变换判定及算法设计

判断图同构的一种有用的方法是对图的邻接矩阵进行初等变换,变成另一个图的邻接矩阵。不幸的是,当初等变换后两个矩阵不能相等时,并不能说明两个图不同构,因为可能存在另一种变换途径,使得两个矩阵相等。另一方面,这种穷尽变换途径的方法有n!种可能(n为图的顶点个数);当n太大时,尝试每一种可能来说明两个图是否同构是不可行的,是一个NP难问题。文章提出了一个简单有效的判断图同构的方法。首先,利用邻接矩阵生成行码距异或矩阵和行码距同或矩阵;其次,寻找邻接矩阵、行码距异或矩阵、行码距同或矩阵间保持行元素一样的行-行置换;如果这种置换存在,则图同构,否则不同构。最后,根据行-行置换确定出同构函数,它给出了两个图的顶点间具有保持相邻关系的一一对应。     

Supereulerian graphs with small matching number and 2-connected hamiltonian claw-free graphs

Motivated by the Chinese Postman Problem, Boesch, Suffel, and Tindell [The spanning subgraphs of Eulerian graphs, J. Graph Theory 1 (1977), pp. 79–84] proposed the supereulerian graph problem which seeks the characterization of graphs with a spanning Eulerian subgraph. Pulleyblank [A note on graphs spanned by Eulerian graphs, J. Graph Theory 3 (1979), pp. 309–310] showed that the supereulerian problem, even within planar graphs, is NP-complete. In this paper, we settle an open problem raised by An and Xiong on characterization of supereulerian graphs with small matching numbers. A well-known theorem by Chvátal and Erdös [A note on Hamilton circuits, Discrete Math. 2 (1972), pp. 111–135] states that if G satisfies α(G)≤κ(G), then G is hamiltonian. Flandrin and Li in 1989 showed that every 3-connected claw-free graph G with α(G)≤2 κ(G) is hamiltonian. Our characterization is also applied to show that every 2-connected claw-free graph G with α(G)≤3 is hamiltonian, with only one well-characterized exceptional class.