Téma t6: Vrcholové pokrytí

Zadáno v čísle 25.3.

Zadání

V tomto témátku se budeme věnovat hledání minimálního vrcholového pokrytí. Máme-li graf definovaný jako množinu vrcholů a množinu hran mezi nimi, tak jeho vrcholové pokrytí je taková podmnožina vrcholů, že každá hrana má alespoň jeden svůj konec v té podmnožině. Minimální vrcholové pokrytí je potom takové vrcholové pokrytí, které obsahuje minimální možný počet vrcholů.

Pro minimální vrcholové pokrytí se umí spousta zajimavých triků, viz https://en.wikipedia.org/wiki/Vertex_cover.

Vzhledem k tomu, že v tomto témátku budeme občas pracovat s relativně velkými grafy, tak místo jejich kreslení se raději domluvíme na datovém formátu. Každý graf bude popsán samostatným textovým souborem. Na prvním řádku bude uveden počet vrcholů grafu N a počet hran M. Budeme předpokládat, že vrcholy jsou číslovány od 0 do N-1. Na následujících M řádcích budou uvedeny hrany - každý řádek bude odpovídat jedné hraně a bude obsahovat dvojici čísel vrcholů, které tato hrana spojuje. Na pořadí těchto čísel v rámci řádku ani na pořadí hran nezáleží.

Řešení pro jednotlivé grafy posílejte jako seznam čisel vrcholů, které tvoří vrcholové pokrytí. Také posílejte vaše pozorování o vlastnostech grafů, nápady na zlepšení algoritmů a obecně cokoliv, co může vám a vašim spoluřešitelům pomoct v hledání minimálních vrcholových pokrytí velkých grafů.

Poznámka: První graf by měl odpovídat obrázku z čísla. Kliknutím na graf získáte jeho datovou reprezentaci (viz výše).

Další grafy (minimálně prozatím) bez obrázků:

Graf 4

Graf 5

Graf 6

Graf 7

Graf 8

Graf 9

Graf 10