---
tag: F19GHK405Q
kind: concept
name: Priority matching
sources:
  - wikipedia: en:65198326@r1187569693
    locator: Priority matching
    note: adopted
    mention: wikipedia://en/65198326
    sections: [Summary]
same_as:
  wikidata: Q104854318
  wikipedia: Priority matching
inventory: [GM6B25S0DY]
---

## Summary

In graph theory, a **priority matching** (also called: **maximum priority matching**) is a [[matching|0MJ04A50QW]] that maximizes the number of high-priority vertices that participate in the matching. Formally, we are given a [[graph|00C0BR7D7H]] $G = (V, E)$, and a partition of the vertex-set $V$ into some $k$ subsets, $V_{1}, \ldots, V_{k}$, called *priority classes*. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from $V_{1}$; subject to this, it saturates the largest number of vertices from $V_{2}$; subject to this, it saturates the largest number of vertices from $V_{3}$; and so on.