Tutts matchende teorem

Tutts matchende sætning er et grafteoretisk udsagn, der giver en nødvendig og tilstrækkelig betingelse for eksistensen af en perfekt matchning i en graf ; generaliserer bryllupssætningen for todelte grafer og er et specialtilfælde af Tatta-Berge-formlen .

Udtalelse af sætningen: en graf har en perfekt match , hvis og kun hvis, for hver delmængde af hjørner , subgrafen induceret af ikke har flere forbundne komponenter med et ulige antal hjørner . $G=(V,E)$ $U\subseteq V$ $V\setminus U$ $|U|$

Installeret af William Tutt .

Litteratur

Bondy, JA Grafteori med applikationer (neopr.) . New York: American Elsevier Pub. Co., 1976. - ISBN 0-444-19451-7 .
Lovasz, Laszlo. Matchingsteori (neopr.) . - Amsterdam: Nord-Holland, 1986. - ISBN 0-444-87916-1 .