|
Xuong Tree
In graph theory, a Xuong tree is a spanning tree T of a given graph G with the property that, in the remaining graph G-T, the number of connected components with an odd number of edges is as small as possible. They are named after Nguyen Huy Xuong, who used them to characterize the cellular embeddings of a given graph having the largest possible genus. According to Xuong's results, if T is a Xuong tree and the numbers of edges in the components of G-T are m_1,m_2,\dots, m_k, then the maximum genus of an embedding of G is \textstyle\sum_^k\lfloor m_i/2\rfloor. Any one of these components, having m_i edges, can be partitioned into \lfloor m_i/2\rfloor edge-disjoint two-edge paths, with possibly one additional left-over edge. An embedding of maximum genus may be obtained from a planar embedding of the Xuong tree by adding each two-edge path to the embedding in such a way that it increases the genus by one. A Xuong tree, and a maximum-genus embedding derived from it, may be found in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Xuong Tree
In graph theory, a Xuong tree is a spanning tree T of a given graph G with the property that, in the remaining graph G-T, the number of connected components with an odd number of edges is as small as possible. They are named after Nguyen Huy Xuong, who used them to characterize the cellular embeddings of a given graph having the largest possible genus. According to Xuong's results, if T is a Xuong tree and the numbers of edges in the components of G-T are m_1,m_2,\dots, m_k, then the maximum genus of an embedding of G is \textstyle\sum_^k\lfloor m_i/2\rfloor. Any one of these components, having m_i edges, can be partitioned into \lfloor m_i/2\rfloor edge-disjoint two-edge paths, with possibly one additional left-over edge. An embedding of maximum genus may be obtained from a planar embedding of the Xuong tree by adding each two-edge path to the embedding in such a way that it increases the genus by one. A Xuong tree, and a maximum-genus embedding derived from it, may be found in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spanning Tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about spanning forests below). If all of the edges of ''G'' are also edges of a spanning tree ''T'' of ''G'', then ''G'' is a tree and is identical to ''T'' (that is, a tree has a unique spanning tree and it is itself). Applications Several pathfinding algorithms, including Dijkstra's algorithm and the A* search algorithm, internally build a spanning tree as an intermediate step in solving the problem. In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., people often use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in the process of finding the minimum spanning tree. The Internet and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Connected Component (graph Theory)
In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices. In random graphs, a frequently occurring phenomenon is the incidence of a giant component, one component that is significantly larger than the others; and of a percolation threshold, an edge probability above which a giant component exists and below which it does not. The components of a graph can be constructed in linear time, and a special case of the problem, connected-component labeling, is a basic technique in image analysis. Dynamic co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Embedding
In topological graph theory, an embedding (also spelled imbedding) of a Graph (discrete mathematics), graph G on a surface (mathematics), surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with graph theory, vertices and simple arcs (Homeomorphism, homeomorphic images of [0,1]) are associated with graph theory, edges in such a way that: * the endpoints of the arc associated with an edge e are the points associated with the end vertices of e, * no arcs include points associated with other vertices, * two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact space, compact, connected space, connected 2-manifold. Informally, an embedding of a graph into a surface is a drawing of the graph on the surface in such a way that its edges may intersect only at their endpoints. It is well known that any finite graph can be embedded in 3-dimensional Euclidean space \mathbb^3.. A planar graph is one that ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Genus (mathematics)
In mathematics, genus (plural genera) has a few different, but closely related, meanings. Intuitively, the genus is the number of "holes" of a surface. A sphere has genus 0, while a torus has genus 1. Topology Orientable surfaces The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected. It is equal to the number of handles on it. Alternatively, it can be defined in terms of the Euler characteristic ''χ'', via the relationship ''χ'' = 2 − 2''g'' for closed surfaces, where ''g'' is the genus. For surfaces with ''b'' boundary components, the equation reads ''χ'' = 2 − 2''g'' − ''b''. In layman's terms, it's the number of "holes" an object has ("holes" interpreted in the sense of doughnut holes; a hollow sphere would be considered as having zero holes in this sense). A torus has 1 such h ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expresse ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice. Matroid theory borrows extensively from the terminology of both linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in geometry, topology, combinatorial optimization, network theory and coding theory. Definition There are many equivalent ( cryptomorphic) ways to define a (finite) matroid.A standard source for basic definitions and results about matroids is Oxley (1992). An older standard source is Welsh (1976). See Brylawsk ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matroid Parity Problem
In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem. Matroid parity can be solved in polynomial time for linear matroids. However, it is NP-hard for certain compactly-represented matroids, and requires more than a polynomial number of steps in the matroid oracle model. Applications of matroid parity algorithms include finding large planar subgraphs and finding graph embeddings of maximum genus. These algorithms can also be used to find connected dominating sets and feedback vertex sets in graphs of maximum degree three. Formulation A matroid can be defined from a finite set of elements and from a notion of what it means for subsets of elements to be independent, subject to the following constraints: *Every subset of an ind ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Matroid
In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures (matroids and groups respectively) with concrete descriptions in terms of linear algebra. A linear matroid is a matroid that has a representation, and an ''F''-linear matroid (for a field ''F'') is a matroid that has a representation using a vector space over ''F''. Matroid representation theory studies the existence of representations and the properties of linear matroids. Definitions A (finite) matroid (E,\mathcal) is defined by a finite set E (the elements of the matroid) and a non-empty family \mathcal of the subsets of E, called the independent sets of the matroid. It is required to satisfy the properties that every subset of an independent set is itself independent, and that if one ind ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Journal Of The ACM
The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is Venkatesan Guruswami. The journal was established in 1954 and "computer scientists universally hold the ''Journal of the ACM'' in high esteem". See also * ''Communications of the ACM ''Communications of the ACM'' is the monthly journal of the Association for Computing Machinery (ACM). It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members. Articles are intended for readers with ...'' References External links * Publications established in 1954 Computer science journals Association for Computing Machinery academic journals Bimonthly journals English-language journals {{compu-journal-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spanning Tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about spanning forests below). If all of the edges of ''G'' are also edges of a spanning tree ''T'' of ''G'', then ''G'' is a tree and is identical to ''T'' (that is, a tree has a unique spanning tree and it is itself). Applications Several pathfinding algorithms, including Dijkstra's algorithm and the A* search algorithm, internally build a spanning tree as an intermediate step in solving the problem. In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., people often use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in the process of finding the minimum spanning tree. The Internet and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
