|
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 ... [...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 wi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Imaginary Number
An imaginary number is a real number multiplied by the imaginary unit , is usually used in engineering contexts where has other meanings (such as electrical current) which is defined by its property . The square of an imaginary number is . For example, is an imaginary number, and its square is . By definition, zero is considered to be both real and imaginary. Originally coined in the 17th century by René Descartes as a derogatory term and regarded as fictitious or useless, the concept gained wide acceptance following the work of Leonhard Euler (in the 18th century) and Augustin-Louis Cauchy and Carl Friedrich Gauss (in the early 19th century). An imaginary number can be added to a real number to form a complex number of the form , where the real numbers and are called, respectively, the ''real part'' and the ''imaginary part'' of the complex number. History Although the Greek mathematician and engineer Hero of Alexandria is noted as the first to present a calculati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Double Factorial
In mathematics, the double factorial or semifactorial of a number , denoted by , is the product of all the integers from 1 up to that have the same parity (odd or even) as . That is, :n!! = \prod_^ (n-2k) = n (n-2) (n-4) \cdots. For even , the double factorial is :n!! = \prod_^\frac (2k) = n(n-2)(n-4)\cdots 4\cdot 2 \,, and for odd it is :n!! = \prod_^\frac (2k-1) = n(n-2)(n-4)\cdots 3\cdot 1 \,. For example, . The zero double factorial as an empty product. The sequence of double factorials for even = starts as : 1, 2, 8, 48, 384, 3840, 46080, 645120,... The sequence of double factorials for odd = starts as : 1, 3, 15, 105, 945, 10395, 135135,... The term odd factorial is sometimes used for the double factorial of an odd number. History and usage In a 1902 paper, the physicist Arthur Schuster wrote: states that the double factorial was originally introduced in order to simplify the expression of certain trigonometric integrals that arise in the derivation of t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction). Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull. Such a drawing is sometimes referred to as a mystic rose. Properties The complete graph on vertices is denoted by . Some sources claim that the letter in this notation stands for the German word , but the German name for a complete graph, , does not contain the letter , and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory. has edges ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
FKT Algorithm
The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, counting them remains #P-complete even for planar graphs. The key idea of the FKT algorithm is to convert the problem into a Pfaffian computation of a skew-symmetric matrix derived from a planar embedding of the graph. The Pfaffian of this matrix is then computed efficiently using standard determinant algorithms. History The problem of counting planar perfect matchings has its roots in statistical mechanics and chemistry, where the original question was: If diatomic molecules are adsorbed on a surface, forming a single layer, how many ways can they be arranged? The partition function is an important quantity that encodes the statistical properties of a system at equilibrium and can be used to answer the previous question. However, tr ... [...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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pieter Kasteleyn
Pieter Willem "Piet" Kasteleyn (12 October 1924 – 16 January 1996) was a Dutch physicist famous for his contributions to the field of statistical mechanics. Biography Pieter Willem Kasteleyn was born in Leiden on 12 October 1924. After finishing high school in 1942, Kasteleyn briefly studied chemistry in Amsterdam. After the war, Leiden University reopened, where he undertook the study of physics and graduated in 1951. He defended his Ph.D. thesis working under S.R. de Groot in 1956. In 1963 Kasteleyn was nominated Full Professor at the Lorentz Institute of Theoretical Physics in Leiden. In 1979 he was elected a member of the Royal Netherlands Academy of Arts and Sciences. From 1981 to 1985 he acted as secretary of the Physics Section of the Academy. From 1978 to 1984 he was chairman of the Commission for Theoretical Physics of the Dutch National Physics Foundation. He retired in 1985. He died on 16 January 1996, after an unexpected and short illness. Research While inves ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Biadjacency 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 v ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permanent (mathematics)
In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both are special cases of a more general function of a matrix called the immanant. Definition The permanent of an matrix is defined as \operatorname(A)=\sum_\prod_^n a_. The sum here extends over all elements σ of the symmetric group ''S''''n''; i.e. over all permutations of the numbers 1, 2, ..., ''n''. For example, \operatorname\begina&b \\ c&d\end=ad+bc, and \operatorname\begina&b&c \\ d&e&f \\ g&h&i \end=aei + bfg + cdh + ceg + bdi + afh. The definition of the permanent of ''A'' differs from that of the determinant of ''A'' in that the signatures of the permutations are not taken into account. The permanent of a matrix A is denoted per ''A'', perm ''A'', or Per ''A'', sometimes with parentheses around the argument. Minc uses Per(''A'') for the permanent of rectangular m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
♯P-complete
The #P-complete problems (pronounced "sharp P complete" or "number P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties: *The problem is in #P, the class of problems that can be defined as counting the number of accepting paths of a polynomial-time non-deterministic Turing machine. *The problem is #P-hard, meaning that every other problem in #P has a Turing reduction or polynomial-time counting reduction to it. A counting reduction is a pair of polynomial-time transformations from inputs of the other problem to inputs of the given problem and from outputs of the given problem to outputs of the other problem, allowing the other problem to be solved using any subroutine for the given problem. A Turing reduction is an algorithm for the other problem that makes a polynomial number of calls to a subroutine for the given problem and, outside of those calls, uses polynomial tim ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bipartite Graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V red, each edge has endpoints of differing colors, as is required in the graph coloring problem.. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. One often writes G=(U,V,E) to denote a bipartite graph whose partition has the parts U and V, with E denot ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maximum Cardinality Matching
Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible. An important special case of the maximum cardinality matching problem is when is a bipartite graph, whose vertices are partitioned between left vertices in and right vertices in , and edges in always connect a left vertex to a right vertex. In this case, the problem can be efficiently solved with simpler algorithms than in the general case. Algorithms for bipartite graphs Flow-based algorithm The simplest way to compute a maximum cardinality matching is to follow the Ford–Fulkerson algorithm. This algorithm solves the more general problem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
