Generation of directed cotrees formulated in Wang's algebra

The construction of a directed graph for a network described by an impedance matrix is presented. This graph has a structure similar to that of the network. The analysis is based on the generation of directed cotrees, which are dual to the directed trees.     

Pathset enumeration of directed graphs by the set theoretic method

The set theoretic method developed by the author in a previous paper for enumeration of pathsets of non-directed graphs has been modified in this paper and applied to directed graphs. The directed graph is represented mathematically by an expression using vertex sets defined in the text. Set operations like union and intersection are applied to the vertex set terms of this expression and these terms are gradually converted to complete pathsets of the directed graph. The developed method has been explained in the text using illustrations.     

Simple enumeration of minimal cutsets of acyclic directed graph

Two methods are given that use combinations of nodes to enumerate all minimal cutsets. One simply has to enumerate all combinations of orders 1 to N-3 of nodes from 2 to N-1, where N is the total number of nodes. Collecting only those symbols of links of first row of adjacency matrix and in the rows given in a combination that are not in the columns of the combination, a cutset of an acyclic directed graph having all adjacent nodes is obtained. To obtain the cutsets of a general acyclic directed graph, four rules are given for deletion of those combinations that yield redundant and nonminimal subsets. The rules provide a reduced set of combinations, which then gives rise to minimal cutsets of a general graph. Three examples illustrate the algorithms     

有向图上k步可达查询处理

给定一个有向图,一个k步可达查询u→?kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径。k步可达查询是一种基本的图操作并在过去十年间被广泛地研究。已有的k步可达查询算法仍存在许多弊端,例如不可达查询效率低,索引规模大和索引构建时间长等。本文针对上述问题提出了2种优化方法,分别是基于互逆拓扑序号以及基于等价顶点的图压缩方法.前者提高了不可达查询的效率,后者减少了索引规模和索引构建时间。实验结果表明,本文提出的方法可以有效地处理k步可达查询,并支持大规模数据的处理。     

Finding the most vital edges with respect to the number of spanningtrees

A most vital edge of a graph (w.r.t. the spanning trees) is an edge whose deletion most drastically decreases the number of spanning trees. We present an algorithm for determining the most vital edges based on Kirchoff's matrix-tree theorem whose asymptotic time-complexity can be reduced to that of the fastest matrix multiplication routine, currently O(n^2.376). The foundation for this approach is a more general algorithm for directed graphs for counting the rooted spanning arborescences containing each of the arcs of a digraph. A network can be modeled as a probabilistic graph. Under one such model proposed by Kel'mans, the all-terminal network reliability, maximizing the number of spanning trees is critical to maximizing reliability when edges are very unreliable. For this model, the most vital edges characterize the locations where an improvement of the reliability of the link most improves the reliability of the network     

AN EFFICIENT CIRCUIT VECTOR SPACE ALGORITHM FOR GENERATING ALL DIRECTED CIRCUITS OF A DIGRAPH

An efficient circuit vector space algorithm is presented for enumerating directed circuits ofa directed graph,by which every directed circuit is generated by the ring sum of a fundamental circuit anda subset of the obtained directed circuits,and can be expressed as a linear combination of a basic set of thedirected circuits.     

Alternate forms of the generalized composite scattering matrix

The author reconciles the differences in three forms of generalized composite scattering matrix derivations. Star matrix multiplication conversion of a generalized composite transmission matrix to its scattering equivalent and signal flow graph analysis are reviewed and analyzed     

Identifying and locating-dominating codes: NP-completeness results for directed graphs

Let G=(V, A) be a directed, asymmetric graph and C a subset of vertices, and let B/sub r//sup -/(v) denote the set of all vertices x such that there exists a directed path from x to v with at most r arcs. If the sets B/sub r//sup -/(v) /spl cap/ C, v /spl isin/ V (respectively, v /spl isin/ V/spl bsol/C), are all nonempty and different, we call C an r-identifying code (respectively, an r-locating-dominating code) of G. In other words, if C is an r-identifying code, then one can uniquely identify a vertex v /spl isin/ V only by knowing which codewords belong to B/sub r//sup -/(v), and if C is r-locating-dominating, the same is true for the vertices v in V/spl bsol/C. We prove that, given a directed, asymmetric graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r/spl ges/1 and remains so even when restricted to strongly connected, directed, asymmetric, bipartite graphs or to directed, asymmetric, bipartite graphs without directed cycles.     

Global Synchronization of Discrete-Time Dynamical Network With a Directed Graph

We investigate synchronization of linearly coupled map lattices with asymmetric and irreducible coupling matrices. In terms of graph terminology, the coupling matrix represents a directed graph. In case the uncoupled map satisfies Lipschitz conditions, a criterion of global synchronization of the linearly coupled map lattices is derived. With this criterion, we investigate how synchronizability depends on the coupling matrix as well as graph topology. Furthermore, we also prove that a directed graph can synchronize some chaotic map if and only if the graph contains a spanning tree     

Duality principle for asynchronous control circuits for directed graphs

The directed graph provides a means of analysing parallel computer structures, whether implemented in hardware or software. This letter discusses the asynchronous circuit modules used to implement the control section of such systems, and indicates a duality principle that permits a wider variety of control functions to be envisaged.     

Marked graphs and hamiltonian graphs

In this paper we present an algorithm using a sign incidence matrix to enumerate all the subsets of places of a marked graph which are both siphon and trap, whose input transitions equal the output transitions and where both of them equal the set of all transitions. An iterative procedure to find a set of places in a marked graph whose removal ensures the resulting marked graph does not have a subset of places which are both siphon and trap, is given. This iterative procedure employs a siphon-trap matrix. As an application, using the algorithm given earlier, we have obtained all Hamiltonian circuits of a given directed graph. We have also found the minimal feedback edge set of a given directed graph. A characterization for Hamiltonian graphs is obtained in terms of siphons and traps.     

基于有向无环图的区间覆盖率求解算法

给定一个有向无环图,回答可达性查询是图的基本操作之一.虽然很多方法使用树区间来加速可达查询的处理速度,但并不明确使用多少个区间比较合适.本文提出一种快速计算区间覆盖率的算法,该方法通过使用有效的剪枝策略来支持高效的覆盖率计算.基于所得到的区间覆盖率,可针对不同数据图确定合适的区间个数,以便在加速查询处理的同时,降低索引...     

有向矩阵的广义讯号流图

本文把讯号流图推广到有向矩阵系统，提出一种广义的讯号流图定义及其拓扑法则，并给出了复杂网络系统的若干应用实例。     

二值化身份感知图卷积神经网络北大核心CSCD

针对有限的内存资源导致图神经网络(graph neural network, GNN)无法完全加载属性图的问题,文中提出了二值化身份感知图卷积神经网络(binary identify-aware graph convolutional network, BID-GCN)。该网络通过在消息传递过程中递归地考虑节点的信息,为了获得一个给定的节点的嵌入,BID-GCN将提取以该节点为中心的自我网络,并进行多轮的异构消息传递,在自我网络的中心节点上应用与其他节点不同的参数。在消息传递过程中,对网络参数和输入节点特征进行二值化,并将原始的矩阵乘法修改为二值化以加速运算。通过理论分析和实验评估,BID-GCN可以减少网络参数和输入数据的平均约36倍的内存消耗,并加快引文网络上平均约49倍的推理速度,可以提供与全精度基线相当的性能,较好地解决内存资源有限的问题。     

Simple algorithm for determining the existence of a linear graph from a given edge matrix

In this letter, a simple algorithm for determining the existence of a linear graph from a given edge matrix is given. The algorithm not only provides a means of determining the existence of a linear graph, but also suggests ways by which the given edge matrix must be modified to enable a graph to exist.     

基于"矩阵乘法"的网络最短路径算法

 网络最短路径问题可以作为许多实际应用问题的模型,但传统的求解算法其迭代过程复杂.本文描述了基于矩阵乘法的最短路算法,其时间复杂度与Dijkstra算法相同.在给定的一个网络图中,在不改变网络图中的最短路的条件下,删除"多余"的结点或边,可以达到简化网络图和提高求解速度的目的,从而降低计算复杂性.最后,研究了该方法在最短路径问题和旅行商问题中的应用.实例表明,这种算法与传统的动态规划技术相比,具有运算简便、易于理解的优点.     

分形图像编码的矩阵表示和收敛性分析

分形解码迭代过程的收敛是保证解码正确实现的条件,要研究迭代过程的收敛性首先要把分形编码中的映射用矩阵来表示出来.本文针对Jacqain的分块算法给出了数字灰度图像分形编码的矩阵表示,并提出了一种利用求有向图强连通分量来求矩阵谱半径的方法.     

Enumeration of all simple paths in a directed graph using Petri net: A systematic approach

The determination of all simple (or success) paths between two specified nodes in a directed graph finds various applications in graph theory, reliability evaluation of a system, etc. Many attempts at the problem of determining the S-T paths (simple or success paths between specified nodes S and T) have appeared in the literature [1–3]. The present paper, which utilizes the concept of the Petri net (PN), is yet another attempt at the same problem. The proposed technique is simple and tackles the problem in a systematic way. It is amenable to computer implementation.     

Enumeration of minimal cutsets from matrix representation of directed/undirected networks

This paper describes an algorithm for finding the minimal cutsets between a specified source and terminal nodes of directed/undirected networks. Adjacent nodes of a source node/merged node are determined by the collection of node numbers of columns corresponding to non-zero elements of the first row of the adjacency matrix to form the reduced adjacency matrix (RAM) corresponding to merged nodes. Connectivity of RAM has been checked to obtain the minimal cutsets.