共查询到19条相似文献，搜索用时 312 毫秒
1.
用邻矩阵生成加权有向图 总被引：1，自引：0，他引：1
1IntroductionWith rapid development of computer technology,re-search onthe graphtheory has provided a great deal ofadvanced results .However ,one can not find manyre-searches on visual build of graphs based on adjacencymatrix or relationship matrix of the graph , althoughsuch research is useful in the teaching of graph theoryand other practical applications .Take weighted direct-ed graph as an example , only after building a graphusing adjacency or relationship matrix ,can one visual-ly and ef… 相似文献
2.
MOGHANI Ghorban Ali ASHRAFI Ali Reza HAMADANIAN Masood 《Journal of Zhejiang University. Science. B》2005,(3)
INTRODUCTION The simplicity and elegance of some of theapplications of graph theory to chemistry can perhapsonly be compared with the results from group theorydealing with symmetry as a basic quality of a system.In some problems connectivity and symmetry arecombined and the question of determining symmetryproperties of graph becomes important. Given here are some definitions and notations.An automorphism of a graph G is a permutation g ofthe vertex set of G with the property that, for an… 相似文献
3.
This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given. 相似文献
4.
图的符号全划分数 总被引：1，自引：0，他引：1
Let G = （V, E） be a graph, and let f ： V →{-1, 1} be a two-valued function. If ∑x∈N（v） f（x） ≥ 1 for each v ∈ V, where N（v） is the open neighborhood of v, then f is a signed total dominating function on G. A set {fl, f2,… fd} of signed d total dominating functions on G with the property that ∑i=1^d fi（x） ≤ 1 for each x ∈ V, is called a signed total dominating family （of functions） on G. The maximum number of functions in a signed total dominating family on G is the signed total domatic number on G, denoted by dt^s（G）. The properties of the signed total domatic number dt^s（G） are studied in this paper. In particular, we give the sharp bounds of the signed total domatic number of regular graphs, complete bipartite graphs and complete graphs. 相似文献
5.
For an arbitrary subset P of the reals, a function f ： V →P is defined to be a P-dominating function of a graph G = （V, E） if the sum of its function values over any closed neighbourhood is at least 1. That is, for every v ∈ V, f（N[v]） ≥ 1. The definition of total P-dominating function is obtained by simply changing ‘closed＇ neighborhood N[v] in the definition of P-dominating function to ‘open＇ neighborhood N（v）. The （total） P-domination number of a graph G is defined to be the infimum of weight w（f） = ∑v ∈ V f（v） taken over all （total） P-dominating function f. Similarly, the P-edge and P-star dominating functions can be defined. In this paper we survey some recent progress on the topic of dominating functions in graph theory. Especially, we are interested in P-, P-edge and P-star dominating functions of graphs with integer values. 相似文献
6.
图的整数值控制函数 总被引：1，自引：0，他引：1
For an arbitrary subset P of the reals,a function f:V→P is defined to be a P-dominating function of a graph G=(V,E) if the sum of its function values over any closed neighbourhood is at least 1.That is,for every v∈V, f(N[v])≥1.The definition of total P-dominating function is obtained by simply changing‘closed’neighborhood N[v]in the definition of P-dominating function to‘open’neighborhood N(v).The (total) P-domination number of a graph G is defined to be the infimum of weight w(f) =∑_(v∈V)f(v) taken over all (total) P-dominating function f.Similarly,the P-edge and P-star dominating functions can be defined.In this paper we survey some recent progress oil the topic of dominating functions in graph theory.Especially,we are interested in P-,P-edge and P-star dominating functions of graphs with integer values. 相似文献
7.
基于蚁群优化的多水平图划分算法 总被引：1，自引：0，他引：1
Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration (VLSI) design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed withits guidance function. During the refinement phase, the vertex gain is exploited as ant’s heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute (ANSI) C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks. 相似文献
8.
The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known vertex covering and dominating set problems in graph theory. In this paper, it was shown that the power domination number of an outerplanar graph with the diameter two or a 2-connected outerplanar graph with the diameter three is precisely one. Upper bounds on the power domination number for a general planar graph with the diameter two or three were determined as an immediate consequences of results proven by Dorfling, et al. Also, an infinite family of outerplanar graphs with the diameter four having arbitrarily large power domination numbers were given. 相似文献
9.
In this paper,the control of complex delayed networks with different nodes is proposed.Firstly,the stabilization of coupled networks with time delay is investigated.By constructing a Lyapunov function,a linear feedback controller design procedure for the networks is converted to the problem of solving a set of linear matrix inequalities.Then the results are extended to networks with both delayed dynamical nodes and delayed couplings.It is shown that the stabilization of complex networks is determined by the dynamics of each uncoupled node,coupling matrix and feedback gain matrix of networks.Two examples are simulated.In the first example,a network with 10 nodes consisting of Lorenz systems and systems proposed by Zhang in 2009 is given.It is found that the network states are divergent without control,and convergent under designed linear feedback controllers.In the second example,a larger network with 100 nodes consisting of delayed Chen systems and delayed Lorenz systems is given.The proposed method is also effective for large scale networks. 相似文献
10.
Given a graph G,a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and |C|≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as TC (G), is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K (G), is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F={G|K(G) is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus TC (G)/|G|≤1/2 for all G ∈ F. 相似文献
11.
MOGHANI Ghorban Ali ASHRAFI Ali Reza HAMADANIAN Masood 《Journal of Zhejiang University. Science. B》2005,(3)
Let G be a weighted graph with adjacency matrixA=[aij]. An Euclidean graph associated with a molecule is defined by a weighted graph with adjacency matrix D=[dij], where for i≠j, dij is the Euclidean distance between the nuclei i andj. In this matrix dij can be taken as zero ifall the nuclei are equivalent. Otherwise, one may introduce different weights for different nuclei. Balasubramanian (1995) computed the Euclidean graphs and their automorphism groups for benzene, eclipsed and staggered forms of ethane and eclipsed and staggered forms of ferrocene. This paper describes a simple method, by means of which it is possible to calculate the automorphism group of weighted graphs. We apply this method to compute the symmetry of tetraammine platinum(Ⅱ) with C2v and C4v point groups. 相似文献
12.
任秋道 《内江师范学院学报》2009,24(10):26-29,54
设圈C=v1v2…vmv1,m≥3．在圈C的顶点vi1,vi2,…,vil分别悬挂一条路Pk1,Pk2,…,Pkl的图记为Cili2…il（Pk1,Pk2,…,Pkl）,1≤ij≤m,1≤j≤l．顶点vm悬挂l条Pk1,Pk2,…,Rkl的图简记为Cm^l（Pk1,Pk2,…,Pkl）．在圈C=v1v2…vmv1的顶点i,上悬挂l条路Pkl,Pk2,…,Pkl的图的最大特征值不小于将l条路分别悬挂在l个顶点i1,i2,…,il的图的最大特征值,即λ1（Gi1^l（Pk1,Pk2,…,Pkl））≥λ1（Ci1i2…il（Pk1,Pk2,…Pkl）,1≤ij≤m-1,j=1,2,…,l． 相似文献
13.
主要考虑简单图,其特征值定义为它的邻接矩阵的特征值.在所有给定阶数且支配数为2的连通图中,完全刻画了最小特征值达到极小的图. 相似文献
14.
连通性是图的基本性质之一,由定义来判断顶点数和边数较大的图的连通性和连通分支数比较困难。结合图的邻接矩阵,给出判断图的连通性的两个充要条件,并给出判断图的连通分支数的一个充要条件和非负对称不可约矩阵的一个充要条件。 相似文献
15.
张爱华 《中国教育技术装备》2011,(30):34-35
图的矩阵表示法,有着重要的意义。一般离散数学教材中对邻接矩阵的概念及其作用的介绍是零散的,学生感觉不到其重要性,也不知如何应用。为了让学生掌握如何利用矩阵来解决图论中的一些问题的知识,对邻接矩阵的作用进行有意义的总结和归类,并对教学内容进行设计,在教学实践中取得好的效果。 相似文献
16.
何梅芝 《湖南科技学院学报》2006,27(11):60-62
设G_1和G_2分别是n阶与m阶顶点互不相邻的简单图,G_1G_2称为G_1与G_2的冠,是通过将G_2复制n个后,把G_1的第i-个顶点与G2的第i-复制的每一个顶点相连而得到的图。本文讨论了一些特殊图类的冠的邻接矩阵的秩,主要是当G2为完全图,完全二部图,Petersens图和CP(k)时两个图的冠。 相似文献
17.
This paper proposes an algorithm for building weighted directed graph, defmes the weighted directed relationship matrix of the graph, and describes algorithm implementation using this matrix. Based on this algorithm, an effective way for building and drawing weighted directed graphs is presented, forming a foundation for visual implementation of the algorithm in the graph theory. 相似文献
18.
任秋道 《绵阳师范学院学报》2007,26(11):14-17
图G的特征值是图的一个重要不变量。在量子化学和理论化学中有大量的应用。当图G的顶点数较大时,其邻接矩阵的阶数较大,计算特征值较困难。分块降阶是通常的方法。本文针对一些特殊图的邻接矩阵进行分块降阶求特征值。如果在V(G)上有一个一一映射φ,使得φ(vi)=vn-i 1,i=1,2,…,n,那么G的点v1仅与G的点v1重合的图G G的特征值中有G-V1的特征值。 相似文献
19.
设j,k和m是3个正整数.给定一个图G.设f：V（G）→{0,1,…,m-1}是一个映射.如果对图G的任意一对相邻顶点u和v都有f（u）-f（v）m≥j,对任意一对距离为二的顶点都有f（u）-f（v）m≥k,其中a-bm=min{a-b,m-a-b},则称f是图G的一个圆m-L（j,k）-标号.使得图G有圆m-L（j,k）-标号的最小的正整数m称为图G的圆L（j,k）-标号数,记为σj,k（G）.对任意2个满足j≤k的正整数,确定了树以及2个完全图的笛卡尔乘积图和直积图的圆L（j,k）-标号数. 相似文献