网络上两类物资联合最大流问题的极流特征

当网络上(诸如交通网络、通讯网络)有多种不同物资或信息同时分别从相应的发点输送到相应的收点,要求每条线路上各类物资或信息的输送量总和不超过线路的容量时,寻求所有物资的最大输送量的问题,就是所谓网络多种物资的最大流问题,这个问题在生产实际和理论上都有着重要的意义,1963年T.C.Hu提出了求两类物资联合最大流的标号方法,但是为了保证有限步达到最大流,要求边的容量是偶数。 本文是文献[3]的继续,用图论的语言描述了两类物资最大流问题极流的特征,并对标号方法作了一点修改,使得有限步得到最大流,或者在某一步得到极流后,保证以后的迭代是从极流到极流.这样因极流的个数是有限的,并且最大流总可以在极流上达到,从而保证了有限步内得到所要求的最大流,无须对边的容量作任何限制, 本文所提的算法是使图形特征很强的标号算法和线性规划的极点迭代结合起来,这就使得有可能把这种方法,推广到更大的一类问题中,例如,研究容量的改变对最大流量的影响。     

路的积图的边平衡性质

2009年, Kwong和Lee考虑了一个图论中新的标号问题—图的边平衡指标集.在本文中,通过利用嵌入标号图的方法,考察了路的积图的边平衡性质.     

城市公共交通流:一种新的建模与算法(英文)

交通拥塞是当前发展中国家的大多数城市所面临的共同问题。本文提出了一种应用于城市交通网络流最优分配的二次规划模型,并结合这一大型交通网络流配置问题的求解,研究了二次规划计算机算法特点,提出了一种改进算法。本模型及算法在中国一个大型城市的交通规划中得到应用。     

(n,m)-p-蜘蛛树的强优美性

给出了优美树、强优美树、边对称树以及对偶标号的概念,定义了一类蜘蛛树.证明了此类蜘蛛树是强优美树,蜘蛛树的强优美标号是对偶标号,并证明了蜘蛛树的边对称树仍然是强优美树.     

一种新的交通网络设计优化算法

交通网络设计问题是研究如何用定量的方法在已有交通网络上添加或扩容某些路段的问题.文章在回顾交通网络设计问题文献的基础上,提出了基于图论网络优化思想的解决该类问题的一种新思路,给出了启发式算法,并进行了算法复杂性分析,最后通过算例验证了其有效性.     

含回路网络的中心选址 Ⅰ.单回路情形

本文对单回路网络引入了一种新的双标号准则,借此给出了求其1-中心的O(n)阶算法。对边不交的多回路网络,在Ⅱ中将给出一个有效的去边准则。设网络G=(V,E)是一个无向连通图,V(G)和E(E)分别表示其顶点集和边集。在此,我们考虑如下的网络选址问题其中p∈G表示p也可取在边上。关于树网络的中心选址,有关文献[3]、[4]、[5]已做了深入的研究。本文对单回路网络引进了双标号准则,从而给出此类网络1-中心选址的O(n)阶算法。     

交通网络建设序列的动态规划方法

交通网络建设序列优化是交通规划中一个重要问题。文章对交通网络设计及其建设序列问题的研究现状进行了分析。按照网络建设中规划者和用户间的关系,以交通网络建设序列下的各阶段系统总费用作为上层规划,以各阶段的交通流用户平衡模型作为下层规划,建立了双层规划模型。并依照问题的特点,采用动态规划的求解方法进行探讨,而下层模型则采用了基于路径搜索的GP算法进行求解。并针对网络规划算例进行了计算,针对固定和变动客流OD两种情况下的结果进行了分析。计算的结果表明,问题的双层规划模型和动态规划求解算法能够为路网规划决策提供支持。     

有向图的距离标号边跨度

将无向图距离标号边跨度的概念引入到有向图.运用图的流（flow）及tension理论,确定了有向树和有向圈的边跨度,以及最长有向路长不超过3的有向二部图边跨度的可达上下界.     

三路树P(m,n,t)是边幻图的证明(Ⅱ)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V ∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

三路树P(m,n,t)是边幻图的证明(II)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

A novel approach based on recurrent neural networks applied to nonlinear systems optimization

This paper presents an efficient approach based on recurrent neural network for solving nonlinear optimization. More specifically, a modified Hopfield network is developed and its internal parameters are computed using the valid subspace technique. These parameters guarantee the convergence of the network to the equilibrium points that represent an optimal feasible solution. The main advantage of the developed network is that it treats optimization and constraint terms in different stages with no interference with each other. Moreover, the proposed approach does not require specification of penalty and weighting parameters for its initialization. A study of the modified Hopfield model is also developed to analyze its stability and convergence. Simulation results are provided to demonstrate the performance of the proposed neural network.     

Spectral methods for graph clustering - A survey

Graph clustering is an area in cluster analysis that looks for groups of related vertices in a graph. Due to its large applicability, several graph clustering algorithms have been proposed in the last years. A particular class of graph clustering algorithms is known as spectral clustering algorithms. These algorithms are mostly based on the eigen-decomposition of Laplacian matrices of either weighted or unweighted graphs. This survey presents different graph clustering formulations, most of which based on graph cut and partitioning problems, and describes the main spectral clustering algorithms found in literature that solve these problems.     

Dominating sets in social network graphs

This paper presents an approach to the study of the structure of social networks using dominating sets of graphs. A method is presented for partitioning the vertices of a graph using dominating vertices. For certain classes of graphs this is helpful in determining the underlying structure of the corresponding social network. An extension of this technique provides a method of studying the structure of directed graphs and directed social networks. Minimum dominating sets are related to statuses and structurally equivalent sets.     

An interactive graphical method for community detection in network data

The detection of community structures within network data is a type of graph analysis with increasing interest across a broad range of disciplines. In a network, communities represent clusters of nodes that exhibit strong intra-connections or relationships among nodes in the cluster. Current methodology for community detection often involves an algorithmic approach, and commonly partitions a graph into node clusters in an iterative manner before some stopping criterion is met. Other statistical approaches for community detection often require model choices and prior selection in Bayesian analyses, which are difficult without some amount of data inspection and pre-processing. Because communities are often fuzzily-defined human concepts, an alternative approach is to leverage human vision to identify communities. The work presents a tool for community detection in form of a web application, called gravicom, which facilitates the detection of community structures through visualization and direct user interaction. In the process of detecting communities, the gravicom application can serve as a standalone tool or as a step to potentially initialize (and/or post-process) another community detection algorithm. In this paper we discuss the design of gravicom and demonstrate its use for community detection with several network data sets. An “Appendix” describes details in the technical formulation of this web application built on the R package Shiny and the JavaScript library D3.     

Minimal comparability completions of arbitrary graphs

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes Π for which Π completion of arbitrary graphs can be achieved through such a vertex incremental approach.     

The swap graph of the finite soluble groups

A graph is reflexive if the second largest eigenvalue of its adjacency matrix is less than or equal to 2. In this paper, we characterize trees whose line graphs are reflexive. It turns out that these trees can be of arbitrary order—they can have either a unique vertex of arbitrary degree or pendant paths of arbitrary lengths, or both. Since the reflexive line graphs are Salem graphs, we also relate some of our results to the Salem (graph) numbers.     

A network-based futures method for strategic business planning

Many strategic decisions in business are made in a context which the decision makers perceive as uncertain, complex and opaque. A method, based on Rhyne's field anomaly relaxation technique, is described of generating a network of states which characterise the environment or context in which strategic decisions are to be made. These states represent possible future conditions for the business, and knowledge of them allows improved strategic understanding and decision making to be achieved. This paper describes the method, using a representative real-life application to illustrate the process.     

Multicriteria optimization with a multiobjective golden section line search

This work presents an algorithm for multiobjective optimization that is structured as: (i) a descent direction is calculated, within the cone of descent and feasible directions, and (ii) a multiobjective line search is conducted over such direction, with a new multiobjective golden section segment partitioning scheme that directly finds line-constrained efficient points that dominate the current one. This multiobjective line search procedure exploits the structure of the line-constrained efficient set, presenting a faster compression rate of the search segment than single-objective golden section line search. The proposed multiobjective optimization algorithm converges to points that satisfy the Kuhn-Tucker first-order necessary conditions for efficiency (the Pareto-critical points). Numerical results on two antenna design problems support the conclusion that the proposed method can solve robustly difficult nonlinear multiobjective problems defined in terms of computationally expensive black-box objective functions.     

A characterization of consistent marked graphs

A marked graph is obtained from a graph by giving each point either a positive or a negative sign. Beineke and Harary raised the problem of characterzing consistent marked graphs in which the product of the signs of the points is positive for every cycle. In this paper a characterization is given in terms of fundamental cycles of a cycle basis.