|
Covering Graph
In the mathematical discipline of graph theory, a graph is a covering graph of another graph if there is a covering map from the vertex set of to the vertex set of . A covering map is a surjection and a local isomorphism: the neighbourhood of a vertex in is mapped bijectively onto the neighbourhood of in . The term lift is often used as a synonym for a covering graph of a connected graph. Though it may be misleading, there is no (obvious) relationship between covering graph and vertex cover or edge cover. The combinatorial formulation of covering graphs is immediately generalized to the case of multigraphs. In the case of a multigraph with a 1-dimensional cell complex, a covering graph is nothing but a special example of covering spaces of topological spaces, so the terminology in the theory of covering spaces is available; say covering transformation group, universal covering, abelian covering, and maximal abelian covering. Definition Let ''G'' = (''V''1, ''E''1) and ' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Forbidden Graph Characterization
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph and the complete bipartite graph . For Kuratowski's theorem, the notion of containment is that of graph homeomorphism, in which a subdivision of one graph appears as a subgraph of the other. Thus, every graph either has a planar drawing (in which case it belongs to the family of planar graphs) or it has a subdivision of at least one of these two graphs as a subgraph (in which case it does not belong to the planar graphs). Definition More generally, a forbidden grap ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Planar Graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points. Every graph that can be drawn on a plane can be drawn on the sphere as well, and vice versa, by means of stereographic projection. Plane graphs can be encoded by combinatorial maps or rotation systems. An equivalence class of topologically equivalent drawings on the sphere, usually with additional assumptions such as the absence of isthmuses, is called a pl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Planar Cover
In graph theory, a planar cover of a finite undirected graph, graph ''G'' is a finite covering graph of ''G'' that is itself a planar graph. Every graph that can be graph embedding, embedded into the projective plane has a planar cover; an unsolved conjecture of Seiya Negami states that these are the only graphs with planar covers., p. 1 The existence of a planar cover is a graph minor, minor-closed graph property,, Proposition 1, p. 2 and so can be characterized by finitely many forbidden graph characterization, forbidden minors, but the exact set of forbidden minors is not known. For the same reason, there exists a polynomial time algorithm for testing whether a given graph has a planar cover, but an explicit description of this algorithm is not known. Definition A ''covering map'' from one graph ''C'' to another graph ''H'' may be described by a function ''f'' from the vertices of ''C'' onto the vertices of ''H'' that, for each vertex ''v'' of ''C'', gives a bijection ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
