China 
Africa 
Explore chapters and articles related to this topic
Matchings in graphs
Published in V. K. Balakrishnan, Network Optimization, 2019
A matching M in an undirected graph is a perfect matching if every vertex in the graph is incident to an edge in M. If a perfect matching exists for G, then any algorithm to obtain a maximum cardinality matching can be applied to obtain a perfect matching in G. Unlike the cardinality matching algorithm, there is no efficient algorithm to determine whether an arbitrary graph has a perfect matching even though there is a necessary and sufficient condition for the existence of a perfect matching in a graph due to Tuttee (1947). Suppose W is a set of vertices in a graph G = (V, E). Let Φ(G − W) denote the number of components of G − W with an odd number of vertices. If there is a perfect matching in the graph, then every odd component of G − W has a vertex u which is joined by a matched edge to a vertex in W. So a necessary condition for a perfect matching to exist is that Φ(G − W) ⩽ |W| for any set W of vertices. If this inequality holds for every set, then it holds for the empty set and so this necessary condition implies that the number of vertices in the graph is even. Tuttee’s perfect matching theorem (proved in 1947) asserts that this inequality is a sufficient condition for the existence of a perfect matching in an arbitrary undirected graph. An elegant, independent proof of this theorem was given by Lovász (1975), and the reader is referred to that paper for details.
Graph Algorithms II
Published in R. Balakrishnan, Sriraman Sridharan, Discrete Mathematics, 2019
R. Balakrishnan, Sriraman Sridharan
A matching M of the graph G is a maximum matchingmaximum matching, if there is no matching M′ of G such that |M′| > |M|. Here, |M| stands for the number of edges in M. A perfect matchingperfect matchingM is a matching which saturates every vertex of the graph G. Perfect matchings are also called 1-factor1-factors. Every perfect matching is a maximum matching but the converse is not always true. Note that the number of edges in a perfect matching is exactly n/2 where n is the number of vertices. Hence the minimal condition for the existence of a perfect matching is that the number of vertices of the graph must be even.
Alternating Paths and Matchings
Published in Kenneth H. Rosen, Graphs, Algorithms, and Optimization, 2005
For example, in Figure 7.1, |M1| = 3 and |M2| = 4. Since |G| = 8, M2 is a maximum matching. A matching which saturates every vertex is called a perfect matching. Obviously a perfect matching is always a maximum matching. M1 is not a maximum matching, but it is a maximal matching; namely M1 cannot be extended by the addition of any edge uv of G. However, there is a way to build a bigger matching out of M1. Let P denote the path (u1, u2,...,u6) in Figure 7.1.
Conditional strong matching preclusion of the pancake graph
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
A matching in a graph is a set M of pairwise nonadjacent edges. A perfect matchingM in G is a matching such that every vertex in G is incident to exactly one edge in M. An almost-perfect matchingM in G is a set of edges such that every vertex in G except one is incident with exactly one edge in M, and the exceptional vertex is incident to none. If G has a perfect matching, then G has an even number of vertices; if G has an almost-perfect matching, then G has an odd number of vertices. We say that the graph G is matchable if it has a perfect matching or an almost-perfect matching. Otherwise, it is called unmatchable.
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 .