|
Sachs Subgraph
In graph theory, a Sachs subgraph of a given graph is a subgraph in which all connected components are either single edges or cycles. These subgraphs are named after Horst Sachs, who used them in an expansion of the characteristic polynomial of the adjacency matrix of graphs. A similar expansion using Sachs subgraphs is also possible for permanental polynomials of graphs. Sachs subgraphs and the polynomials calculated with their aid have been applied in chemical graph theory, for instance as part of a test for the existence of non-bonding orbitals in hydrocarbon structures. A spanning Sachs subgraph, also called a -factor, is a Sachs subgraph in which every vertex of the given graph is incident to an edge of the subgraph. The union of two perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set ... [...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] |
Subgraph (graph Theory)
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B C D E F G H I K L M N O ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cycle (graph Theory)
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an ''acyclic graph''. A directed graph without directed cycles is called a ''directed acyclic graph''. A connected graph without cycles is called a ''tree''. Definitions Circuit and cycle * A circuit is a non-empty trail in which the first and last vertices are equal (''closed trail''). : Let be a graph. A circuit is a non-empty trail with a vertex sequence . * A cycle or simple circuit is a circuit in which only the first and last vertices are equal. Directed circuit and directed cycle * A directed circuit is a non-empty directed trail in which the first and last vertices are equal (''closed directed trail''). : Let be a directed graph. A directed circuit is a non-empty directed trail with a vertex sequence ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Horst Sachs
Horst Sachs (27 March 1927 – 25 April 2016) was a German mathematician, an expert in graph theory, a recipient of the Euler Medal (2000). He earned the degree of Doctor of Science (Dr. rer. nat.) from the Martin-Luther-Universität Halle-Wittenberg in 1958. Following his retirement in 1992, he was professor emeritus at the Institute of Mathematics of the Technische Universität Ilmenau. His encyclopedic book in spectral graph theory, ''Spectra of Graphs. Theory and Applications'' (with Dragos Cvetković and Michael Doob) has several editions and was translated in several languages.Review by P. Rowlinson (1996), ''Proceedings of the Edinburgh Mathematical Society (Series 2)'' 39: 188–189, . Two theorems in graph theory bear his name. One of them relates the coefficients of the characteristic polynomial of a graph to certain structural features of the graph. Another one is a simple relation between the characteristic polynomials of a graph and its line graph In the math ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Characteristic Polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The characteristic polynomial of an endomorphism of a finite-dimensional vector space is the characteristic polynomial of the matrix of that endomorphism over any base (that is, the characteristic polynomial does not depend on the choice of a basis). The characteristic equation, also known as the determinantal equation, is the equation obtained by equating the characteristic polynomial to zero. In spectral graph theory, the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. Motivation In linear algebra, eigenvalues and eigenvectors play a fundamental role, since, given a linear transformation, an eigenvector is a vector whose direction is not changed by the transformation, and the corresponding eigenva ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Adjacency Matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected (i.e. all of its edges are bidirectional), the adjacency matrix is symmetric. The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory. The adjacency matrix of a graph should be distinguished from its incidence matrix, a different matrix representation whose elements indicate whether vertex–edge pairs are incident or not, and its degree matrix, which contains information about the degree of each vertex. Definition For a simple graph with vertex set , the adjacency matrix is a square matrix such that its element is one when there is an edge from vertex to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chemical Graph Theory
Chemical graph theory is the topology branch of mathematical chemistry which applies graph theory to mathematical modelling of chemical phenomena. The pioneers of chemical graph theory are Alexandru Balaban, Ante Graovac, Iván Gutman, Haruo Hosoya, Milan Randić and Nenad Trinajstić (also Harry Wiener and others). In 1988, it was reported that several hundred researchers worked in this area, producing about 500 articles annually. A number of monographs have been written in the area, including the two-volume comprehensive text by Trinajstić, ''Chemical Graph Theory'', that summarized the field up to mid-1980s. The adherents of the theory maintain that the properties of a chemical graph (i.e., a graph-theoretical representation of a molecule) give valuable insights into the chemical phenomena. Others contend that graphs play only a fringe role in chemical research.D.H. Rouvray, "Combinatorics in Chemistry", pp. 1955-1982, in: Ronald Graham, Martin Grötschel, László Lovász (E ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Non-bonding Orbital
A non-bonding orbital, also known as ''non-bonding molecular orbital'' (NBMO), is a molecular orbital whose occupation by electrons neither increases nor decreases the bond order between the involved atoms. Non-bonding orbitals are often designated by the letter n in molecular orbital diagrams and Molecular electronic transition, electron transition notations. Non-bonding orbitals are the equivalent in molecular orbital theory of the lone pairs in Lewis structures. The energy level of a non-bonding orbital is typically in between the lower energy of a valence shell bonding orbital and the higher energy of a corresponding antibonding orbital. As such, a non-bonding orbital with electrons would commonly be a HOMO (highest occupied molecular orbital). According to molecular orbital theory, molecular orbitals are often modeled by the linear combination of atomic orbitals. In a simple diatomic molecule such as hydrogen fluoride (chemical formula: HF), one atom may have many more elec ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hydrocarbon
In organic chemistry, a hydrocarbon is an organic compound consisting entirely of hydrogen and carbon. Hydrocarbons are examples of group 14 hydrides. Hydrocarbons are generally colourless and hydrophobic, and their odors are usually weak or exemplified by the odors of gasoline and lighter fluid. They occur in a diverse range of molecular structures and phases: they can be gases (such as methane and propane), liquids (such as hexane and benzene), low melting solids (such as paraffin wax and naphthalene) or polymers (such as polyethylene and polystyrene). In the fossil fuel industries, ''hydrocarbon'' refers to the naturally occurring petroleum, natural gas and coal, and to their hydrocarbon derivatives and purified forms. Combustion of hydrocarbons is the main source of the world's energy. Petroleum is the dominant raw-material source for organic commodity chemicals such as solvents and polymers. Most anthropogenic (human-generated) emissions of greenhouse gases are carbon di ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Perfect Matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly one edge in . A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs: : In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched. A perfect matching is also a minimum-size edge cover. If there is a perfect matching, then both the matching number and the edge cover number equal . A perfect matching can only occur when the graph has an even num ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
