四正则图的交叉数

利用计算机对图的交叉数进行研究,给出了利用分支界限法计算图的交叉数的算法CCN(calculatecrossing number),并利用该算法计算出n≤12的所有四正则图的交叉数以及n≤16的随机四正则图的交叉数.同时计算出n≤12的所有四正则图的平均交叉数Aac(n)和n≤16的随机四正则图的平均交叉数Aac(n),根据计算结果提出四正则图的平均交叉数为O(n相似文献   

The k-in-a-Path Problem for Claw-free Graphs

The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s _i ,t _i ) for i=1,…,k and is to test whether G contain k mutually induced paths P _i such that P _i connects s _i and t _i for i=1,…,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs.     

含过程任务图的调度

我们在Ｆｏｒｔｒａｎ程序并行转换系统ＨＺＰＡＲＡ－Ⅱ的研究中遇到了含过程任务图的情形，对此我们提出了一种有效的调度方法。该方法可在Ｏ（ｎ＊ｅ）的时间内完成调度，调度结果可以与ＣＰ调度法相比     

迪卡尔乘积图到Cayley图中的嵌入

给出了一类图（迪卡尔乘积图）到另一类图（Ｃａｙｌｅｙ图的嵌入的一般方法,这些嵌入是这样实现的：首先把迪卡尔乘积图的每个“因子”图嵌入到主图中,然后取这些“因子”嵌入的积,进上步给出了一个定理,用来通过“因子”嵌入的性质来计算乘积嵌入的膨胀度。     

Recognizing d-Interval Graphs and d-Track Interval Graphs

A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing d-track interval graphs is NP-complete for any constant d≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the case d=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced d-track interval graphs, unit d-track interval graphs, and (2,…,2) d-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit d-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity.     

An Internal Presentation of Regular Graphs by Prefix-Recognizable Graphs

The study of infinite graphs has potential applications in the specification and verification of infinite systems and in the transformation of such systems. Prefix-recognizable graphs and regular graphs are of particular interest in this area since their monadic second-order theories are decidable. Although the latter form a proper subclass of the former, no characterization of regular graphs within the class of prefix-recognizable ones has been known, except for a graph-theoretic one in [2]. We provide here three such new characterizations. In particular, a decidable, language-theoretic, necessary and sufficient condition for the regularity of any prefix-recognizable graph is established. Our proofs yield a construction of a deterministic hyperedge-replacement grammar for any prefix-recognizable graph that is regular. Received July 19, 1999, and in revised form December 22, 2000, and in final form March 28, 2001. Online publication July 20, 2001.     

Embedding Cartesian Products of Graphs into de Bruijn Graphs

Given a Cartesian productG=G₁× … ×G_m(m≥ 2) of nontrivial connected graphsG_iand then-dimensional baseBde Bruijn graphD=D_B(n), it is investigated whether or notGis a spanning subgraph ofD. Special attention is given to graphsG₁× … ×G_mwhich are relevant for parallel computing, namely, to Cartesian products of paths (grids) or cycles (tori). For 2-dimensional de Bruijn graphsD, we present a theorem stating that certain structural assumptions on the factorsG₁, …,G_mensure thatG₁× … ×G_mis a spanning subgraph ofD. As corollaries, we obtain results improving previous results of Heydemannet al.(J. Parallel Distrib. Comput.23 (1994), 104–111) on embedding grids and tori into de Bruijn graphs. Specifically, we obtain that (i) any gridG=G₁× … ×G_mis a spanning subgraph ofD=D_B(2) provided that |G| = |D|, and (ii) any torusG=G₁× … ×G_mis a spanning subgraph ofD=D_B(2) provided that |G| = |D| and that theG_iare cycles of even length ≥4. We show that these results have consequences for the casen> 2, too: for evenn, we apply our results to obtain embeddings of grids and toriGinto de Bruijn graphsD_B(n) with dilationn/2, where the baseBis a fixed integer ≥2, andnis big enough to ensure |G| ≤ |D_B(n)|. We also contrast our results forn= 2 with nonexistence results forn≥ 3 and briefly describe experimental results in the area of parallel image processing.     

线框图形的计算机双色立体显示技术

系统地介绍了在计算机上采用双色法对线框图形进行了立体显示的原理和方法并编制了相应程序。此方法简单易行，能达到更好的视觉效果。     

VB中图形图像旋转的实现

举例探讨了用Visual Basic实现图形和图像旋转的方法。     

空间布局的约束图方法

空间布局的自动化是智能CAD领域的研究方向之一,旨在为设计师提供智能辅助工具，用于求解在建筑、厂房设备、大规模集成电路以及产品包装等等若干领域出现的布局问题.图论方法是空间布局研究的主要途径之一.以往的布局模型由于难以充分表达知识与约束,使得设计过程与结果难以控制.本文提出一种可应用于2D及3D布局的规范约束图及层次约束图模型,给出了约束图解的存在条件.该模型可以表示精细的布局知识与约束,在一定程度上克服了以往图模型不能充分表达布局知识与约束的不足.本文还给出了基于约束图的布局生成算法.     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m log n) time.     

The Readability of Path‐Preserving Clusterings of Graphs

Graph visualization systems often exploit opaque metanodes to reduce visual clutter and improve the readability of large graphs. This filtering can be done in a path‐preserving way based on attribute values associated with the nodes of the graph. Despite extensive use of these representations, as far as we know, no formal experimentation exists to evaluate if they improve the readability of graphs. In this paper, we present the results of a user study that formally evaluates how such representations affect the readability of graphs. We also explore the effect of graph size and connectivity in terms of this primary research question. Overall, for our tasks, we did not find a significant difference when this clustering is used. However, if the graph is highly connected, these clusterings can improve performance. Also, if the graph is large enough and can be simplified into a few metanodes, benefits in performance on global tasks are realized. Under these same conditions, however, performance of local attribute tasks may be reduced.     

Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals the structure in the graph. This paper discusses symmetric drawings of biconnected planar graphs. More specifically, we discuss geometric automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a drawing of G. Finding geometric automorphisms is the first and most difficult step in constructing symmetric drawings of graphs. The problem of determining whether a given graph has a non-trivial geometric automorphism is NP-complete for general graphs. In this paper we present a linear time algorithm for finding planar geometric automorphisms of biconnected planar graphs. A drawing algorithm is also discussed.     

Multicolorings of Series-Parallel Graphs

Let G be a graph, and let each vertex v of G have a positive integer weight (v). A multicoloring of G is to assign each vertex v a set of (v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.