Tuttův párovací teorém

Tuttův párovací teorém je graf-teoretický výrok, který dává nezbytnou a postačující podmínku pro existenci dokonalé shody v grafu ; zobecňuje svatební teorém pro bipartitní grafy a je speciálním případem vzorce Tatta-Berge .

Tvrzení věty: graf má dokonalou shodu právě tehdy, když pro každou podmnožinu vrcholů , podgraf indukovaný pomocí již nemá žádné spojené komponenty s lichým počtem vrcholů . $G=(V,E)$ $U\subseteq V$ $V\setminus U$ $|U|$

Instaloval William Tutt .

Literatura

Bondy, JA Teorie grafů s aplikacemi (neopr.) . New York: American Elsevier Pub. Co., 1976. - ISBN 0-444-19451-7 .
Lovasz, Laszlo. Teorie párování (neopr.) . - Amsterdam: North-Holland, 1986. - ISBN 0-444-87916-1 .