Saturation (graph theory)

Saturation (graph theory)

Let G(V,E) be a graph and M a matching in G. A vertex vin V(G) is said to be saturated by M if there is an edge in M incident to v. A vertex vin V(G) with no such edge is said to be unsaturated by M. We also say that M saturates v.

ee also

* Hall's marriage theorem
* bipartite matching
* matching

planetmath|id=4735|title=saturate


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Saturation (magnetic) — Magnetization curves of 9 ferromagnetic materials, showing saturation. 1.Sheet steel, 2.Silicon steel, 3.Cast steel, 4.Tungsten steel, 5.Magnet steel, 6.Cast iron, 7.Nickel, 8.Cobalt, 9.Magnetite[1] Seen in some magnetic materials, saturation is… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Saturate — can mean:* Saturate (album), an album by Breaking Benjamin * Saturation (chemistry), in chemistry, the state of a solution in which no more solute can be dissolved * Saturate (graph theory), in mathematics * Saturate, a song by The Chemical… …   Wikipedia

  • climate — /kluy mit/, n. 1. the composite or generally prevailing weather conditions of a region, as temperature, air pressure, humidity, precipitation, sunshine, cloudiness, and winds, throughout the year, averaged over a series of years. 2. a region or… …   Universalium

  • Decompression (diving) — Divers decompressing in the water at the end of a dive Decompression in the context of diving derives from the reduction in ambient pressure experienced by the diver during the ascent at the end of a dive or hyperbaric exposure and refers to both …   Wikipedia

  • Hysteresis — Not to be confused with Hysteria. Fig. 1. Electric displacement field D of a ferroelectric material as the electric field E is first decreased, then increased. The curves form a hysteresis loop. Hysteresis is the dependence of a system not… …   Wikipedia

  • Advertising Adstock — is a term coined by Simon Broadbent [Broadbent, S. (1979) One Way TV Advertisements Work , Journal of the Market Research Society Vol. 23 no.3.] to describe the prolonged or lagged effect of advertising on consumer purchase behavior. It is also… …   Wikipedia

  • Spreading activation — is a method for searching associative networks, neural networks, or semantic networks. The search process is initiated by labeling a set of source nodes (e.g. concepts in a semantic network) with weights or activation and then iteratively… …   Wikipedia

  • Electromagnet — An electromagnet is a type of magnet in which the magnetic field is produced by the flow of electric current. The magnetic field disappears when the current is turned off. Electromagnets are widely used as components of other electrical devices,… …   Wikipedia

  • Cardiac output — (Q or or CO ) is the volume of blood being pumped by the heart, in particular by a left or right ventricle in the time interval of one minute. CO may be measured in many ways, for example dm3/min (1 dm3 equals 1000 cm3 or 1 litre). Q is… …   Wikipedia

Share the article and excerpts

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