D1 Definitions - Matchings; Route Inspection

HideShow resource information
Matching
1 to 1 pairing of some/all elements of a set, X, with another set, Y.
1 of 6
Maximal matching
A matching in which the number of arcs is as large as possible.
2 of 6
Complete Matching
1 to 1 pairing of all elements in a set, X with another set, Y, in a bipartite graph.
3 of 6
Alternating path
Path starting at an unmatched node on one side of a bipartite graph, and finishing at an unmatched node on the other side. It uses arcs that are alternatively 'not in' or 'in' the initial matching.
4 of 6
Eulerian graph
Graph in which all valencies are even; the graph is traversable.
5 of 6
Semi-Eulerian graph
Graph in which precisely two valencies are odd, and all the rest even; the graph is semi-traversable.
6 of 6

Other cards in this set

Card 2

Front

A matching in which the number of arcs is as large as possible.

Back

Maximal matching

Card 3

Front

1 to 1 pairing of all elements in a set, X with another set, Y, in a bipartite graph.

Back

Preview of the back of card 3

Card 4

Front

Path starting at an unmatched node on one side of a bipartite graph, and finishing at an unmatched node on the other side. It uses arcs that are alternatively 'not in' or 'in' the initial matching.

Back

Preview of the back of card 4

Card 5

Front

Graph in which all valencies are even; the graph is traversable.

Back

Preview of the back of card 5
View more cards

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Graphs and transformations resources »