Párování grafu
From Wikipedia, the free encyclopedia
Párování grafu je v teorii grafů taková podmnožina hran grafu, že žádné dvě hrany z této množiny nemají společný vrchol.
Idea je taková, že vrcholy grafů dáváme do párů. Pár může vzniknout jen tam, kde byla hrana. Přitom každý vrchol může být jen v jednom páru. Řadu praktických problémů lze převést na algoritmizované hledání jistého typu párování v grafu.