Title: Theory / Unimportant / CS / Fundamental / Graph / Bondy - Murty / 16 Matching
Tags: examplesSwitchExample1 hasNotNewEffectReturnsMeaning algoToProblem computer_to_instruction fromAlgorithm hasSeenConjDef oldAlgoNewName

Name: A matching
Definition: A set of pairwise nonadjacent links
Page: 413
Chapter: 16
Section: 1
Variables: \(G\) a graph
Denoted by: \(M\)

Name: An element matched under \(M\)
Definition: A ends of an edge of \(M\)
Page: 413
Chapter: 16
Section: 1
Variables: \(G\) a graph,
\(M\) a matching

Name: An element covered by \(M\)
Definition: A vertex incident with an edge of \(M\)
Page: 414
Chapter: 16
Section: 1
Variables: \(G\) a graph,
\(M\) a matching

Name: A perfect matching
Definition: A matching covering each vertex
Page: 414
Chapter: 16
Section: 1
Variables: \(G\) a graph,
\(M\) a matching

Name: A maximum matching
Definition: A matching maximum for cardinality
Page: 414
Chapter: 16
Section: 1
Variables: \(G\) a graph,
\(M\) a matching

Name: A maximal matching
Definition: \(\subseteq\)-maximal
Page: 414
Chapter: 16
Section: 1
Variables: \(G\) a graph,
\(M\) a matching
Definition2: obtained by any greedy algorithm
Conjdef: A matching, equivalently

Name: A matchable graph
Definition: A graph admitting a perfect matching
Page: 414
Chapter: 16
Section: 1

Page: 414
Effect: Find a maximum matching \(M\)
Chapter: 16
Section: 1
Variables: \(G\) a graph
Extra: Problem
Name: The Maximum Matching Problem
Kind: Prob

Page: 414
Implementation: Maximum matching problem
Section: 1
Chapter: 16
Name: The Assignment Problem
Returns: A certain number of jobs are available to be filled. Given a group of applicants for these jobs, fill as many of them as possible, assigning applicants only to jobs for which they are qualified.
Index: 2
Kind: Prop