|
Gain Graph
A gain graph is a graph whose edges are labelled "invertibly", or "orientably", by elements of a group ''G''. This means that, if an edge ''e'' in one direction has label ''g'' (a group element), then in the other direction it has label ''g'' −1. The label function ''φ'' therefore has the property that it is defined differently, but not independently, on the two different orientations, or directions, of an edge ''e''. The group ''G'' is called the gain group, ''φ'' is the gain function, and the value ''φ''(''e'') is the gain of ''e'' (in some indicated direction). A gain graph is a generalization of a signed graph, where the gain group ''G'' has only two elements. See Zaslavsky (1989, 1991). A gain should not be confused with a weight on an edge, whose value is independent of the orientation of the edge. Applications Some reasons to be interested in gain graphs are their connections to network flow theory in combinatorial optimization, to geometry, and to physic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph (discrete Mathematics)
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' means that ''A'' owes money to ''B'', ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hyperplane
In geometry, a hyperplane is a subspace whose dimension is one less than that of its '' ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyperplanes are the 1-dimensional lines. This notion can be used in any general space in which the concept of the dimension of a subspace is defined. In different settings, hyperplanes may have different properties. For instance, a hyperplane of an -dimensional affine space is a flat subset with dimension and it separates the space into two half spaces. While a hyperplane of an -dimensional projective space does not have this property. The difference in dimension between a subspace and its ambient space is known as the codimension of with respect to . Therefore, a necessary and sufficient condition for to be a hyperplane in is for to have codimension one in . Technical description In geometry, a hyperplane of an ''n''-dime ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Thomas Zaslavsky
Thomas Zaslavsky (born 1945) is an American mathematician specializing in combinatorics. Zaslavsky's mother Claudia Zaslavsky was a high school mathematics teacher and an ethnomathematician in New York; his father Sam Zaslavsky (from Manhattan) was an electrical engineer. Thomas Zaslavsky graduated from the City College of New York. At M.I.T. he studied hyperplane arrangements with Curtis Greene and received a Ph.D. in 1974. In 1975 the American Mathematical Society published his doctoral thesis. Zaslavsky has been a professor of mathematics at the Binghamton University, New York since 1985. He has published papers on matroid theory and hyperplane arrangements. He has also written on coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied ..., lattice point counting, and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matroid Theory
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 Brylaw ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Voltage Graph
In graph theory, a voltage graph is a directed graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used in topological graph theory as a concise way to specify another graph called the derived graph of the voltage graph. Typical choices of the groups used for voltage graphs include the two-element group ℤ2 (for defining the bipartite double cover of a graph), free groups (for defining the universal cover of a graph), ''d''-dimensional integer lattices ℤ''d'' (viewed as a group under vector addition, for defining periodic structures in ''d''-dimensional Euclidean space),; ; . and finite cyclic groups ℤ''n'' for ''n'' > 2. When is a cyclic group, the voltage graph may be called a ''cyclic-voltage graph''. Definition Formal definition of a -voltage graph, for a given group : * Begin with a digraph ''G''. (The direction is solely for convenience in notation.) * A -voltage on an arc of '' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Embedding
In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of ,1/math>) are associated with 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, 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 can be embedded in 2-dimensional Euclidean space \mathbb^2. Often, an embedding is regarded as an equivalence class ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Topological Graph Theory
In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in a surface means that we want to draw the graph on a surface, a sphere for example, without two edges intersecting. A basic embedding problem often presented as a mathematical puzzle is the three utilities problem. Other applications can be found in printing electronic circuits where the aim is to print (embed) a circuit (the graph) on a circuit board (the surface) without two connections crossing each other and resulting in a short circuit. Graphs as topological spaces To an undirected graph we may associate an abstract simplicial complex ''C'' with a single-element set per vertex and a two-element set per edge. The geometric realization , ''C'', of the complex consists of a copy of the unit interval ,1per edge, with the endpoints ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spin Glass
In condensed matter physics, a spin glass is a magnetic state characterized by randomness, besides cooperative behavior in freezing of spins at a temperature called 'freezing temperature' ''Tf''. In ferromagnetic solids, component atoms' magnetic spins all align in the same direction. Spin glass when contrasted with a ferromagnet is defined as " disordered" magnetic state in which spins are aligned randomly or without a regular pattern and the couplings too are random. The term "glass" comes from an analogy between the ''magnetic'' disorder in a spin glass and the ''positional'' disorder of a conventional, chemical glass, e.g., a window glass. In window glass or any amorphous solid the atomic bond structure is highly irregular; in contrast, a crystal has a uniform pattern of atomic bonds. In ferromagnetic solids, magnetic spins all align in the same direction; this is analogous to a crystal's lattice-based structure. The individual atomic bonds in a spin glass are a mixt ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group Action (mathematics)
In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism group of the structure. It is said that the group ''acts'' on the space or structure. If a group acts on a structure, it will usually also act on objects built from that structure. For example, the group of Euclidean isometries acts on Euclidean space and also on the figures drawn in it. For example, it acts on the set of all triangles. Similarly, the group of symmetries of a polyhedron acts on the vertices, the edges, and the faces of the polyhedron. A group action on a vector space is called a representation of the group. In the case of a finite-dimensional vector space, it allows one to identify many groups with subgroups of , the group of the invertible matrices of dimension over a field . The symmetric group acts on any se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Biased Graph
{{Short description, Graph with a list of distinguished cycles In mathematics, a biased graph is a graph with a list of distinguished circles (edge sets of simple cycles), such that if two circles in the list are contained in a theta graph, then the third circle of the theta graph is also in the list. A biased graph is a generalization of the combinatorial essentials of a gain graph and in particular of a signed graph. Formally, a biased graph Ω is a pair (''G'', ''B'') where ''B'' is a linear class of circles; this by definition is a class of circles that satisfies the theta-graph property mentioned above. A subgraph or edge set whose circles are all in ''B'' (and which contains no half-edges) is called balanced. For instance, a circle belonging to ''B'' is ''balanced'' and one that does not belong to ''B'' is ''unbalanced''. Biased graphs are interesting mostly because of their matroids, but also because of their connection with multiary quasigroups. See below. Technica ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group (mathematics)
In mathematics, a group is a set and an operation that combines any two elements of the set to produce a third element of the set, in such a way that the operation is associative, an identity element exists and every element has an inverse. These three axioms hold for number systems and many other mathematical structures. For example, the integers together with the addition operation form a group. The concept of a group and the axioms that define it were elaborated for handling, in a unified way, essential structural properties of very different mathematical entities such as numbers, geometric shapes and polynomial roots. Because the concept of groups is ubiquitous in numerous areas both within and outside mathematics, some authors consider it as a central organizing principle of contemporary mathematics. In geometry groups arise naturally in the study of symmetries and geometric transformations: The symmetries of an object form a group, called the symmetry group of th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Generalized Network
In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. Definition A network is a graph , where is a set of vertices and is a set of 's edges – a subset of – together with a non-negative function , called the capacity function. Without loss of generality, we may assume that ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
