|
Fractional Matching
In graph theory, a fractional matching is a generalization of a Matching (graph theory), matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices. Definition Given a graph (discrete mathematics), graph ''G'' = (''V'', ''E''), a fractional matching in ''G'' is a function that assigns, to each edge ''e'' in ''E'', a fraction ''f''(''e'') in [0, 1], such that for every vertex ''v'' in ''V'', the sum of fractions of edges adjacent to ''v'' is at most 1: \forall v\in V: \sum_f(e)\leq 1 A matching in the traditional sense is a special case of a fractional matching, in which the fraction of every edge is either 0 or 1: ''f''(''e'') = 1 if ''e'' is in the matching, and ''f''(''e'') = 0 if it is not. For this reason, in the context of fractional matchings, usual matchings are sometimes called ''integral matchings''. The size of an integral matching is the number of edges in the matching, and the matching number \nu(G) of a ... [...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 with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
