930 resultados para Clique vertex irreducible graphs
Resumo:
We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.
Resumo:
CFD modelling of 'real-life' processes often requires solutions in complex three dimensional geometries, which can often result in meshes where aspects of it are badly distorted. Cell-centred finite volume methods, typical of most commercial CFD tools, are computationally efficient, but can lead to convergence problems on meshes which feature cells with high non-orthogonal shapes. The vertex-based finite volume method handles distorted meshes with relative ease, but is computationally expensive. A combined vertex-based - cell-centred (VB-CC) technique, detailed in this paper, allows solutions on distorted meshes that defeat purely cell-centred physical models to be employed in the solution of other transported quantities. The VB-CC method is validated with benchmark solutions for thermally driven flow and turbulent flow. An early application of this hybrid technique is to three-dimensional flow over an aircraft wing, although it is planned to use it in a wide variety of processing applications in the future.
Resumo:
A weighted variant of Hall's condition for the existence of matchings is shown to be equivalent to the existence of a matching in a lexicographic product. This is used to introduce characterizations of those bipartite graphs whose edges may be replicated so as to yield semiregular multigraphs or, equivalently, semiregular edge-weightings. Such bipartite graphs will be called semiregularizable. Some infinite families of semiregularizable trees are described and all semiregularizable trees on at most 11 vertices are listed. Matrix analogues of some of the results are mentioned and are shown to imply some of the known characterizations of regularizable graphs.
Resumo:
We are discussing certain combinatorial and counting problems related to quadratic algebras. First we give examples which confirm the Anick conjecture on the minimal Hilbert series for algebras given by $n$ generators and $\frac {n(n-1)}{2}$ relations for $n \leq 7$. Then we investigate combinatorial structure of colored graph associated to relations of RIT algebra. Precise descriptions of graphs (maps) corresponding to algebras with maximal Hilbert series are given in certain cases. As a consequence it turns out, for example, that RIT algebra may have a maximal Hilbert series only if components of the graph associated to each color are pairwise 2-isomorphic.
Resumo:
A ranking method assigns to every weighted directed graph a (weak) ordering of the nodes. In this paper we axiomatize the ranking method that ranks the nodes according to their outflow using four independent axioms. Besides the well-known axioms of anonymity and positive responsiveness we introduce outflow monotonicity – meaning that in pairwise comparison between two nodes, a node is not doing worse in case its own outflow does not decrease and the other node’s outflow does not increase – and order preservation – meaning that adding two weighted digraphs such that the pairwise ranking between two nodes is the same in both weighted digraphs, then this is also their pairwise ranking in the ‘sum’ weighted digraph. The outflow ranking method generalizes the ranking by outdegree for directed graphs, and therefore also generalizes the ranking by Copeland score for tournaments.
Resumo:
The new ammonium iodomercurates(II), (NH4)(7)[HgI4](2)[Hg2I7](H2O) (1) and (NH4)(3)[Hg2I7] (2) contain isolated tetrahedra and vertex-sharing double tetrahedra as the anions. The crystal structures were determined from single-crystal X-ray diffraction data: 1: orthorhombic, Pnma (no. 62), a = 2175.9(2), b = 1781.8(2), c = 1256.2(2) pm, Z = 4. R-1 [I-0 > 2 sigma(I-0)] = 0.0520; 2: monoclinic, P2(1)/c (no. 14), a = 1259.0(2), b = 773.2(1), c = 2172.4(3) pm, beta = 101.18(2)degrees, Z = 4, R, [I-0 > 2 sigma(I-0)] = 0.0308.
Resumo:
Hardware synthesis from dataflow graphs of signal processing systems is a growing research area as focus shifts to high level design methodologies. For data intensive systems, dataflow based synthesis can lead to an inefficient usage of memory due to the restrictive nature of synchronous dataflow and its inability to easily model data reuse. This paper explores how dataflow graph changes can be used to drive both the on-chip and off-chip memory organisation and how these memory architectures can be mapped to a hardware implementation. By exploiting the data reuse inherent to many image processing algorithms and by creating memory hierarchies, off-chip memory bandwidth can be reduced by a factor of a thousand from the original dataflow graph level specification of a motion estimation algorithm, with a minimal increase in memory size. This analysis is verified using results gathered from implementation of the motion estimation algorithm on a Xilinx Virtex-4 FPGA, where the delay between the memories and processing elements drops from 14.2 ns down to 1.878 ns through the refinement of the memory architecture. Care must be taken when modeling these algorithms however, as inefficiencies in these models can be easily translated into overuse of hardware resources.
Resumo:
We present and analyze an algorithm to measure the structural similarity of generalized trees, a new graph class which includes rooted trees. For this, we represent structural properties of graphs as strings and define the similarity of two Graphs as optimal alignments of the corresponding property stings. We prove that the obtained graph similarity measures are so called Backward similarity measures. From this we find that the time complexity of our algorithm is polynomial and, hence, significantly better than the time complexity of classical graph similarity methods based on isomorphic relations. (c) 2006 Elsevier Inc. All rights reserved.
Resumo:
We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples. (c) 2007 Elsevier Inc. All rights reserved.