Blossom (mathematics)

From Wikipedia, the free encyclopedia

In mathematics, the word blossom refers to a functional in numerical analysis, and to a special type of subgraph in graph theory.

[edit] Numerical analysis

In numerical analysis, a blossom is a functional that can be applied to any polynomial, but is mostly used for Bezier and spline curves and surfaces. The blossom of a polynomial f is often denoted \mathcal{B}[f].

The Blossom of a functional is completely characterised by the three properties:

  1. It is a symmetric function of its arguments. \mathcal{B}[f](u_1,\dots,u_d) = \mathcal{B}[f]\big(\pi(u_1,\dots,u_d)\big), (where \pi(\cdot) means any permutation of its arguments).
  2. It is affine in each of its arguments. \mathcal{B}[f](s\alpha + t\beta,\dots) = s\mathcal{B}[f](\alpha,\dots) + t\mathcal{B}[f](\beta,\dots),~s,t \in \mathbb{R}.
  3. It satisfies the diagonal property. \mathcal{B}[f](u,\dots,u) = f(u).

[edit] Graph theory

In graph theory, a blossom is a subgraph of a given graph with an odd number of vertices, in which there exists a matching that matches any subset of all but one vertex. Blossoms play a key role in Jack Edmonds' algorithms for maximum matching and minimum weight perfect matching in nonbipartite graphs.

In general, a graph with n vertices in which any subset of n-1 vertices has a perfect matching is called a factor-critical graph. A blossom is thus a factor-critical subgraph of any graph.

[edit] References

  • Farin, Gerald (2001). Curves and Surfaces for CAGD: A Practical Guide, fifth edition, Morgan Kaufmann. ISBN 1-55860-737-4. 


 This mathematics-related article is a stub. You can help Wikipedia by expanding it.