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.     

一种由基本割集矩阵求网络图的方法

对于一个给定的网络图,可以确定对应的网络矩阵。同样,如果给定网络矩阵,也能够画出对应的网络图。本文讨论由基本割集矩阵求网络图的方法,该方法利用基本割集矩阵Q和降价关联矩阵A的关系,由Q得到A,进而画出对应的网络图。本文的讨论可供从事电路教学的教师参考。     

Formulation of the state equations by signal-flow graphs

The method of drawing the signal-flow graph of an active RLC network is discussed and a method to obtain the state equations directly from the signal-flow graph of the network is given.     

On the analysis of active networks containing voltage, operational, and differential-input operational amplifiers

A method of drawing by inspection the signal-flow graph of an active network containing voltage, operational, and differential-input operational amplifiers is given and it is shown that the network functions can easily be determined from the signal-flow graph.     

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.     

任意有向图的最小K边连通扩充

本文研究了以最小边集扩充一个任意有向图为K边连通有向图这一优化问题。提出了一个复杂度O(|V|5)的有效算法。该算法为可靠网络的计算机辅助设计打下了基础。     

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     

On generation of trees without duplications

It is shown that, in a given graph, the set of trees not containing a given branch can be obtained from the set of trees containing the given branch without duplications. Based on this, a simple derivation of Mayeda and Seshu's technique on generation of trees without duplications is given.     

Uniformly random tree generation

A simple procedure is described for generating a uniformly random tree in a given graph. The probability of obtaining such a tree in a complete graph is given together with the mean number of edge-set selections required and the associated variance.<>     

Optimal design of switching networks A topological approach†

The given functions specifications are represented as a reduced n-cell graph, and its incidence matrix is constructed. The prime implicant table for the given functions is then obtained by a systematic search of the matrix for sub-graphs satisfying certain properties. This table is represented as a linear graph, and the trees of this graph are tagged with a cost depending on the prime implicants in them. The tree with the minimum cost generates the desired optimal network.     

Signal-flow-graph gain with respect to the general node of a graph

A new formula for the graph gain is given, which is more general than Mason's formula and enables the graph gain to be solved with respect to the general node of the graph that may also be the loop node.     

Analysis of active networks using flow-graph technique

A simplified Coates flow-graph technique, applied to the analysis of an arbitrary active network, is presented. Flow-graph representations of building blocks of active networks are given, which permit construction of the graph from the given network. A flow-graph formula for the sensitivity investigation is also given.     

Modeling and analysis of temporal constraints in communication protocols

Reachability analysis is the most popular and the most used method in protocol validation. It consists in constructing a graph called reachability graph, describing the communication of communicating machines exchanging messages through fifa channels. The states and structure of this graph are then analysed according to given properties to validate the corresponding communication protocol. In this paper, we go from the communicating machines used in the classical reachability analysis, to design temporal communicating machines allowing to specify quantitative temporal aspects of communication protocols. A temporal reachability graph describing the global behaviour of temporal communicating machines is then defined. After that, we show how this graph can be used to analyse general properties of communication protocols submitted to temporal constraints and we establish several complexity results dealing with this approach.     

基于回波包络的非相参低分辨率雷达的目标架数判别方法

分析了非相参低分辨率雷达目标回波的起伏特性和调制特性,提供了目标三维图、方位分层图、距离分层图和俯视图等人工辅助判别方法。通过对目标回波的处理,实现了目标架数的自动识别。最后给出了它们在实际应用中的结果。     

不确定网络条件可信近邻查询

不确定因素在现实世界中普遍存在,因此研究不确定网络条件可信近邻查询具有重要意义。该文给出一种新的解决方法。将不确定网络建模为不确定赋权图,定义不确定图的样本图,样本图指数,基础网络,可达路径长度及可达路径期望长度,并给出基于不确定理论的高效不确定图条件可信近邻查询算法。将不确定网络上的近邻查询等价地转化为基础网络上的近临查询问题。理论分析和实验结果表明所提可信近邻查询算法能够从非确定角度解决不确定网络环境下的近邻查询问题。     

Scheduling tests for VLSI systems under power constraints

This paper considers the problem of testing VLSI integrated circuits in minimum time without exceeding their power ratings during test. We use a resource graph formulation for the test problem. The solution requires finding a power-constrained schedule of tests. Two formulations of this problem are given as follows: (1) scheduling equal length tests with power constraints and (2) scheduling unequal length tests with power constraints. Optimum solutions are obtained for both formulations. Algorithms consist of four basic steps. First, a test compatibility graph is constructed from the resource graph. Second, the test compatibility graph is used to identify a complete set of time compatible tests with power dissipation information associated with each test. Third, from the set of compatible tests, lists of power compatible tests are extracted. Finally, a minimum cover table approach is used to find an optimum schedule of power compatible tests     

Construction of the fundamental circuit matrix from a given tree set

A new method for constructing the fundamental circuit matrix from a given tree set is presented. The geometry of the graph is not assumed a priori in the procedure.     

基于恒等子图搜索的点模式匹配算法

点模式匹配问题是计算机视觉和模式识别领域中的一个重要课题,但由于噪声、视场等因素始终难以完全解决.通过构建点模式关系图,把点模式匹配问题转化为关系图最大恒等子图搜索问题,由此给出图、子图、图同构和恒等、支持顶点对及支持顶点对集的概念并对它们满足的一些性质和定理进行了证明,最后提出了一种对最大恒等子图搜索的有效算法,在对...     

有向矩阵的广义讯号流图

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