Blossom tree (graph theory)

A blossom tree, in the context of graph theory, specifically within the Edmonds' blossom algorithm for finding a maximum matching in a general graph (which may contain cycles), is a data structure used to represent the structure of blossoms (alternating cycles) discovered during the algorithm's execution. It is not a specific type of tree in the conventional sense, but rather a tree-like structure built from nodes and edges, where nodes represent vertices in the original graph and edges represent matched or unmatched edges.

The tree is constructed incrementally as the algorithm progresses. When an augmenting path is found, it's integrated into the blossom tree. Importantly, the tree efficiently encodes information about the relationships between vertices within blossoms, allowing the algorithm to contract blossoms and continue the search for augmenting paths in a more manageable representation of the graph.

Each node in a blossom tree may represent a single vertex or an entire blossom (a subgraph which is an even-length cycle with exactly one matched edge). The edges in the blossom tree correspond to edges in the original graph and maintain information about whether they are matched or unmatched. The root of the blossom tree is always a free vertex (a vertex not currently matched in any existing matching).

During the algorithm, when a blossom is detected, it is contracted into a single node within the blossom tree. This contraction simplifies the search for augmenting paths, as the algorithm can treat the entire blossom as a single unit. After finding an augmenting path, the blossoms are expanded recursively to update the matching in the original graph.

The key advantage of using a blossom tree is its ability to efficiently manage the complexity introduced by cycles in the graph. By representing blossoms as single nodes, the algorithm avoids the need to explicitly track the internal structure of each cycle while still maintaining essential information for finding a maximum matching. The structure allows for efficient update operations as the algorithm progresses.