Max-flow min-cut theoremIn computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink. This is a special case of the duality theorem for linear programs and can be used to derive Menger's theorem and the Kőnig–Egerváry theorem.
Space complexityThe space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely. This includes the memory space used by its inputs, called input space, and any other (auxiliary) memory it uses during execution, which is called auxiliary space. Similar to time complexity, space complexity is often expressed asymptotically in big O notation, such as etc.
Edge contractionIn graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation. The edge contraction operation occurs relative to a particular edge, . The edge is removed and its two incident vertices, and , are merged into a new vertex , where the edges incident to each correspond to an edge incident to either or .
Simple extensionIn field theory, a simple extension is a field extension which is generated by the adjunction of a single element, called a primitive element. Simple extensions are well understood and can be completely classified. The primitive element theorem provides a characterization of the finite simple extensions. A field extension L/K is called a simple extension if there exists an element θ in L with This means that every element of L can be expressed as a rational fraction in θ, with coefficients in K; that is, it is produced from θ and elements of K by the field operations +, −, •, / .
Linear searchIn computer science, linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n+1/2 comparisons, but the average case can be affected if the search probabilities for each element vary.
Cycle basisIn graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expressed as a symmetric difference of basis cycles. A fundamental cycle basis may be formed from any spanning tree or spanning forest of the given graph, by selecting the cycles formed by the combination of a path in the tree and a single edge outside the tree.
