Tuttin sovituslause

Tuttin sovituslause on graafiteoreettinen lause, joka antaa välttämättömän ja riittävän ehdon täydellisen sovituksen olemassaololle graafissa ; yleistää häälauseen kaksiosaisille kaavioille ja on Tatta-Bergen kaavan erikoistapaus .

Lauseen väite: Graafilla on täydellinen yhteensopivuus silloin ja vain, jos kullekin pisteiden osajoukolle : n indusoima aligraafi ei enää sisällä toisiinsa liittyviä komponentteja , joissa on pariton määrä pisteitä . $G=(V,E)$ $U\subseteq V$ $V\setminus U$ $|U|$

Asentaja William Tutt .

Kirjallisuus

Bondy, JA Graafiteoria sovelluksilla (neopr.) . New York: American Elsevier Pub. Co., 1976. - ISBN 0-444-19451-7 .
Lovasz, László. Vastaavuusteoria ( uuspr .) . - Amsterdam: Pohjois-Hollanti, 1986. - ISBN 0-444-87916-1 .