China
Africa
Explore chapters and articles related to this topic
Discrete Mathematics
Published in Dan Zwillinger, CRC Standard Mathematical Tables and Formulas, 2018
matching: A matching in a graph is a set of edges, no two having a vertex in common. A maximal matching is a matching that is not a proper subset of any other matching. A maximum matching is a matching of greatest cardinality.
Decentralised fixed modes of networked MIMO systems
Published in International Journal of Control, 2018
Yuqing Hao, Zhisheng Duan, Guanrong Chen
In a directed graph, an edge (i, j) is directed from i to j, where i is the tail and j is the head of the edge. For node system i, define the sets of its in-neighbours and out-neighbours as Nini = {j ∈ {1, …, N}|βij ≠ 0} and Nouti = {j ∈ {1, …, N}|βji ≠ 0}, respectively. The in-degree and the out-degree of node i are the cardinalities of Nini and Nouti, respectively. A matching is a set of edges that do not share any common tail or common head. A maximum matching is a matching that contains the largest possible number of edges in the graph. A node is called a matched node if it is the head of an edge in a matching, otherwise it is an unmatched node. A perfect matching is a matching which matches all nodes in the graph, which is a certainly a maximum matching. A graph formed by a sequence of edges {(vi, vi + 1)|i = 1, 2,… , l − 1} with no repeated nodes is called a path, denoted as v1,… , vl, where v1 is the beginning and vl is the end of the path, and vl is said to be reachable from v1. If v1,… , vl is a path, then the graph formed by adding the edge (vl, v1) is a cycle. A graph without circles is called a tree. The node in a tree which can reach every other node is called the root of the tree. A leaf in a rooted tree is a node of degree 1 that is not the root. A chain is a tree with only one leaf.
The structural index of sensitivity equation systems
Published in Mathematical and Computer Modelling of Dynamical Systems, 2018
Atiyah Elsheikh, Wolfgang Wiechert
In the previous definition is clearly a bipartite graph and for well-determined systems of equations. The structural index is based on maximum matchings [49] of the corresponding computational bipartite graph defined as follows (Matching, perfect matching, weight of a matching, maximum matching): Given a graph , where and are sets of vertices and edges, respectively, and given as a weight function, a matching is a set of edges s.t. for any and and , i.e. no two edges are incident in a vertex. A perfect matching is a matching where all vertices are covered. The weight of a matching is given by A maximum matching of size is a matching where .
A new hybrid matheuristic optimization algorithm for solving design and network engineering problems
Published in International Journal of Management Science and Engineering Management, 2018
G. Chagwiza, B. C. Jones, S. D. Hove-Musekwa, S. Mtisi
Matching, as defined in graph theory, can assist in matching a maximum number of compatible nodes. Matching has been applied widely to solve combinatorial problems (Di Nardo et al., 2015; Lovasz, Pyber, Welsh, & Ziegler, 1996). If nodes are effectively matched, there is a high possibility that better cutting planes will be produced to solve the mixed integer programming (MIP) problem. The research has been motivated by the success of the Grotschel–Holland algorithm (Grotschel & Holland, 1985), which will be referred to as the G-H algorithm, to solve combinatorial problems.