Shortest path problemIn graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment.
Empty setIn mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other theories, its existence can be deduced. Many possible properties of sets are vacuously true for the empty set. Any set other than the empty set is called non-empty. In some textbooks and popularizations, the empty set is referred to as the "null set".
Stable marriage problemIn mathematics, economics, and computer science, the stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a bijection from the elements of one set to the elements of the other set. A matching is not stable if: In other words, a matching is stable when there does not exist any pair (A, B) which both prefer each other to their current partner under the matching.
Cayley's formulaIn mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer , the number of trees on labeled vertices is . The formula equivalently counts the number of spanning trees of a complete graph with labeled vertices . Many proofs of Cayley's tree formula are known. One classical proof of the formula uses Kirchhoff's matrix tree theorem, a formula for the number of spanning trees in an arbitrary graph involving the determinant of a matrix.
Prüfer sequenceIn combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm. Prüfer sequences were first used by Heinz Prüfer to prove Cayley's formula in 1918. One can generate a labeled tree's Prüfer sequence by iteratively removing vertices from the tree until only two vertices remain. Specifically, consider a labeled tree T with vertices {1, 2, .
Disjoint-set data structureIn computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or different sets.
Vertex (geometry)In geometry, a vertex (: vertices or vertexes) is a point where two or more curves, lines, or edges meet. As a consequence of this definition, the point where two lines meet to form an angle and the corners of polygons and polyhedra are vertices. The vertex of an angle is the point where two rays begin or meet, where two line segments join or meet, where two lines intersect (cross), or any appropriate combination of rays, segments, and lines that result in two straight "sides" meeting at one place.
Swap (finance)In finance, a swap is an agreement between two counterparties to exchange financial instruments, cashflows, or payments for a certain time. The instruments can be almost anything but most swaps involve cash based on a notional principal amount. The general swap can also be seen as a series of forward contracts through which two parties exchange financial instruments, resulting in a common series of exchange dates and two streams of instruments, the legs of the swap.
Horn-satisfiabilityIn formal logic, Horn-satisfiability, or HORNSAT, is the problem of deciding whether a given set of propositional Horn clauses is satisfiable or not. Horn-satisfiability and Horn clauses are named after Alfred Horn. A Horn clause is a clause with at most one positive literal, called the head of the clause, and any number of negative literals, forming the body of the clause. A Horn formula is a propositional formula formed by conjunction of Horn clauses. The problem of Horn satisfiability is solvable in linear time.
List of set identities and relationsThis article lists mathematical properties and laws of sets, involving the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion. It also provides systematic procedures for evaluating expressions, and performing calculations, involving these operations and relations. The binary operations of set union () and intersection () satisfy many identities. Several of these identities or "laws" have well established names.
