# D1 Definitions - Matchings; Route Inspection

HideShow resource information
• Created by: Cam
• Created on: 19-05-15 19:27
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.

Maximal matching

### Card 3

#### Front

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

### 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.

### Card 5

#### Front

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