Factor-critical graph

Factor-critical graph

In graph theory, a mathematical discipline, factor-critical graph is a graph with "n" vertices in which any subset of "n" − 1 vertices has a perfect matching. For example, any odd-length cycle graph is factor-critical.

Factor-critical graphs must always have an odd number of vertices, and cannot be bipartite.

A blossom is a factor-critical subgraph of a graph. Blossoms play a key role in Jack Edmonds' algorithms for maximum matching and minimum weight perfect matching in non-bipartite graphs.

References

*cite journal | author=Edmonds, Jack | authorlink = Jack Edmonds | title=Paths, Trees and Flowers | journal=Canadian J. Math | volume=17 | year=1965 | pages=449–467 | id = MathSciNet | id = 0177907


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Critical graph — In general the notion of criticality can refer to any measure. But in graph theory, when the term is used without any qualification, it almost always refers to the chromatic number of a graph. Critical graphs are interesting because they are the… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Critical minimum effort theory — The critical minimum effort theory has been given by Harvey Leibenstein, in his book Economic Backwardness and Economic Growth. This theory relates to overpopulated and underdeveloped or developing nations such as India and Indonesia.This theory… …   Wikipedia

  • Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… …   Wikipedia

  • Compressibility factor — Thermodynamics …   Wikipedia

  • Mycielskian — In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph G is a graph μ(G) formed from G by a construction of Jan Mycielski (1955), who used it to show that there exist triangle free graphs with… …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Logarithm — The graph of the logarithm to base 2 crosses the x axis (horizontal axis) at 1 and passes through the points with coordinates (2, 1), (4, 2), and (8, 3) …   Wikipedia

  • Overpopulation — Graph of human population from 10,000 BC–2000 AD showing the unprecedented population growth since the 19th century Overpopulation is a condition where an organism s numbers exceed the carrying capacity of its habitat. The term often refers to… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”