This note is written in two languages, Chinese and English.

[1]Y. Wu and L. Zhong, “Fusion Blossom: Fast MWPM Decoders for QEC.” arXiv, May 14, 2023. Accessed: Sep. 21, 2023. [Online]. Available: http://arxiv.org/abs/2305.08307

最小权重完美匹配解码器

Minimum Weight Perfect Matching Decoder

完美匹配

图的完美匹配是指一个无向图中的一组边，使得每个顶点都恰好与其中的一条边相连。换句话说，每个顶点都与图中的某一条边配对，且每条边都只与一个顶点配对。

具体来说，对于一个无向图 G=(V, E)，其中 V 表示顶点的集合，E 表示边的集合。如果存在一个边的子集 M，满足下列条件，则称 M 为 G 的完美匹配：

1. M 中的边都是 G 中的边；
2. M 中的任意两条边互不相邻，即它们没有公共的顶点；
3. M 中的边覆盖了 G 中的每个顶点，即每个顶点都与 M 中的某条边相连。

在一个完美匹配中，每个顶点都有且只有一条边与之相连，且所有的顶点都被匹配上了。

⚠️ 匹配：是边的集合

Perfect Matching

A perfect matching in a graph refers to a set of edges in an undirected graph, in which each vertex is connected to exactly one of those edges. In other words, each vertex is paired with a specific edge in the graph, and each edge is only paired with one vertex.

Specifically, for an undirected graph G=(V, E), where V represents the set of vertices and E represents the set of edges. If there exists a subset M of edges that satisfies the following conditions, then M is called a perfect matching of G:

1. All edges in M are edges in G;