Teória grafov – prednášky a úloha o párení v grafoch
Dodatočné prednášky
Uskutočnili sa dve dodatočné prednášky. Prvá sa týkala párenia v bipartitných grafoch. Najdôležitejšie boli
Königova minmaxová veta a Hallova podmienka.
Počas druhej sme riešili párenie vo všeobecnom grafe, kde sme sa snažili dokázať Tuttovu vetu, ktorá hovorí
o nutnej a postačujúcej podmienke existencie 1-faktoru vo všeobecnom grafe. Na dôkaz sme použili inú, o niečo
silnejšiu vetu.
Všetky dôkazy môžete nájsť v knihe Graph Theory od Reinharda Diestela. Prednášky sa držali tejto knihy.
Jediná výnimka, ktorú priniesli tieto prednášky bolo vysvetlenie algoritmu na hľadanie párenia a vrcholového pokrytia
v bipartitnom grafe. Tieto dve témy nájdete spísané v tomto dokumente.
Programátorská domáca úloha
Za túto domácu úlohu sa dajú získať až 4 body. Termín odovzdania je 22.12.2017 do polnoci.
Na jej riešenie musíte ísť na túto stránku testovac.ksp.sk a registrovať sa.
Ako username použite vaše priezvisko.
Po prihlásení by ste nemali problém nájsť úlohu z teórie grafov.
Zvyšné úlohy si nevšímajte, nijak nesúvisia s týmto predmetom.
Cez rozhranie na stránke odovzdávate odladený program. Za úlohu získate iba tie body, čo vám dal testovač, bez ohľadu na to ako blízko ste boli k riešeniu.
Samozrejme, ak máte akýkoľvek problém, či už s testovačom, alebo vôbec netušíte čo môžete robiť zle, tak mi napíšte.
Je super, ak sa ti podarí úlohu vyriešiť bez pomoci, ak si však zaseknutý(á) na tom, že nevieš čo robiť, tak tieto hinty ti snáď pomôžu:
Hint 1
Na dodatočných prednáškach sme si hovorili len dva algoritmy, takže táto úloha bude asi súvisieť s párením a vrcholovým pokrytím.
Hint 2
Cesta dĺžky 1 tam neexistuje, lebo vrcholy nie sú spojené hranou. Ako odstrániš cesty dĺžky 2? Máš na výber?
Hint 3
Keď si odstránil cesty dĺžky 2, zostali ti iba tie dĺžky 3. Ako vyzerajú tieto cesty medzi a a b? Vidíš tam ten bipartitný graf?
Hint 4 (už pomerne vysvetľujúci)
Susedia vrchola a vytvoria jednu partíciu, susedia vrchola b druhú. Spoločných susedov si odstránil už v Hinte 2. Zamysli sa, prečo hľadáš minimálne vrcholové pokrytie v tomto značne zjednodušenom grafe.
Implementačné rady
Neponáhľaj sa so zostrojovaním grafu. Najskôr si zisti, ktoré vrcholy sú susedia len a, len b, ktoré sú susedia obom a ktoré s tým nemajú nič spoločné (čo sú aj vrcholy a a b).
Až keď vieš toto, zostroj graf, ktorý bude obsahovať iba tie zaujímavé hrany (tie vedúce medzi partíciami). Dokonca nemusíš ani nijak prečíslovávať vrcholy alebo ich odstraňovať. Stačí tam dať správne hrany
a vedieť, ktoré vrcholy patria do prvej a ktoré do druhej partície.
Kontakt
Meno: Michal Anderle
Email: zaba@ksp.sk