9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min Jméno: Místnost: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 1 20 bodů Vašim úkolem je sestrojit a nakreslit všechny neisomorfní lesy (jednoduché acyklické grafy) na 6 vrcholech. Rozepište ve stručných a srozumitelných bodech, jak jste postupovali. Všechny kroky také správně zdůvodněte. (Kromě správnosti a úplnosti odpovědí se hodnotí také systematičnost vašeho přístupu k sestrojení požadovaných grafů, ze kterého musí vyplývat, že jste prošli všechny možnosti.) Řešení: Tento příklad kupodivu nepůsobil až takové problémy, jaké jsem čekal. Vedli jste si obecně velmi dobře a systematicky. Celkový počet lesů byl 20. Pokud některý výjimečně chyběl, strhlo se pár bodů, ale mnohem větší ztráty byly důsledkem (poměrně řídkých) chyb v systematičnosti. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min Jméno: Místnost: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 2 20 bodů Je dán jednoduchý graf na 12 vrcholech: s s s s ss s s s s ss Vašim úkolem je zodpovědět správně následující čtyři otázky o tomto grafu. V odpovědi nestačí uvést jen správný výsledek, ale nutné je i stručné zdůvodnění jeho správnosti (na přiloženém obrázku). a) Vyznačte v grafu některou Hamiltonovskou kružnici (procházející všemi vrcholy). b) Jaká je barevnost tohoto grafu? c) Jakou velikost má největší nezávislá množina v tomto grafu? d) Jaká je nejdelší indukovaná cesta v tomto grafu? Řešení: a) Obvykle jste správně nalezli Hamiltonovskou kružnici. b) Barevnost grafu je 3, menší být nemůže kvůli přítomnosti trojúhelníku. c) Nezávislá množina je velikosti nejvýše 5, ale problémy často dělalo správné zdůvodnění. V těchto případech bylo nejjednodušší si celý graf rozdělit na vhodné 3 disjunktní podgrafy a zdůvodňovat podle nich. . . d) Nejdelší indukovaná cesta má délku 7 a šikovně zdůvodnit, že delší není, je možné například vhodnou kombinací úvah o trojúhelnících ­ z každého může indukovaná cesta využít jen jednu hranu. Části byly hodnoceny po 5 bodech, přičemž zhruba polovina byla za zdůvodnění. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min Jméno: Místnost: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 3 20 bodů Z přednášek víme, že každý jednoduchý rovinný graf musí obsahovat vrchol stupně menšího než 6. a) Sestrojte jednoduchý rovinný graf, který má více než 10 vrcholů, ale jen méně než 10 jeho vrcholů má stupně menší než 6. b) Zjistěte, pro jaké nejmenší číslo b platí, že existuje jednoduchý rovinný graf s minimálním stupněm 3 a maximálním stupněm aspoň 6, v němž nejvýše b vrcholů má stupně menší než 6. Svou odpověď matematicky dokažte (včetně zdůvodnění, proč menší b není možné). Řešení: a) Obvykle jste nalézali dost podobné grafy, ale to je tím, že bylo docela přirozené a snadné je nalézt. Za správný graf bylo 5 bodů, přičemž plný počet ale dostal jen ten, kdo i slovně okomentoval, proč graf splňuje podmínku zadání. (Jen obrázek bez popisu je nejvýše za 4.) b) Nejmenší možné b je 4. Za nalezení příslušného příkladu bylo až 5 bodů a zbylých 10 bylo pro ty, kteří nalezli správné zdůvodnění, že menší b není možné. Ve variantě B bylo nalezení správného příkladu mnohem snažší, a proto jsem ve variantě A uděloval body i za nalezení horšího příkladu s b = 5. (Příklad grafu s b = 4 nalezl snad jen jediný z vás, je to třeba graf čtyřstěnu s každou stěnou rozdělenou na 4 trojúhelníky.) Dolní odhad správně zdůvodnili jen někteří. Není to přitom vůbec těžké, stačí dosadit počty vrcholů jednotlivých stupňů do omezení 3v - 6 pro počet hran jednoduchého rovinného grafu. Na druhou stranu žádné pokusy zdůvodňovat správnost b tím, že zrovna do vašeho obrázku už nelze vrcholy či hrany přidávat, nejsou korektní a nebyly honorovány. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min Jméno: Místnost: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 4 20 bodů Mějme libovolný konečný graf G = (V, E). O množině hran F E řekneme, že je nezávislá, pokud každá souvislá komponenta podgrafu G = (V, F) obsahuje nejvýše jednu kružnici. (Je to tedy jiná definice nezávislosti hran v grafu, než jsme měli na přednášce u matroidů.) Vašim úkolem je dokázat, že množina E hran grafu G spolu s touto definicí nezávislosti tvoří matroid. (Neboli musíte vypsat a ověřit tři axiomy nezávislých množin matroidu podle této definice.) Řešení: Je vidět, že tento příklad byl pro vás nejobtížnější, třebaže v něm nejde o moc více než správně aplikovat definice. Kdo správně vypsal všechny tři axiomy matroidu, získal 1 bod (za to není důvod udělovat více, zvláště když jste je mohli mít zapsanou na taháku). Kdo k těm axiomům správně doplnil důkaz prvních dvou v daném případě, získal celkem až 5 bodů ­ přitom tato část byla velmi jednoduchá. Zbylých 15 bodů pak bylo pro ty, kteří se poperou s důkazem splnění třetího (výměnného) axiomu, ale zůstaly u všech skoro nevyužity. Zde naznačím, jak se třeba v důkaze třetího axiomu dá postupovat (a jsou mnohé jiné možnosti): * Uvažujme obecně multigraf G na vrcholech V . Máme |A| < |B| a obě tyto množiny hran v G jsou nezávislé. Klíčové je si všimnout, že pokud kontrahujeme libovolnou hranu v A, co není smyčkou, zůstane A nezávislá. * Nechť tedy f = uv je hranou A, ne smyčkou, na vrcholech V . Potom i A = A - {f} na V = V - {v} (tj. výsledek kontrakce f) je nezávislá. Na druhou stranu, pokud B má cyklickou komponentu obsahující u ­ zmíněný konec f, odstraníme kružnici této komponenty vypuštěním některé hrany f B, tj. B = B - {f}. (Jinak snadno B = B.) I zde je pak po ztotožnění v s u bude množina B na V nezávislá. Postupujeme indukcí podle počtu vrcholů, takže nyní už máme hranu e B - A takovou, že A {e} na V je nezávislá. Lze dokázat, že i před kontrakcí f byla A {e} nezávislá. To přesně potřebujeme. * Zbývá dodělat základ indukce, kdy všechny hrany A jsou smyčky. Jelikož |A| < |B| a B je také nezávislá, musí hrany B pokrýt i některé vrcholy, které nejsou pokryty smyčkami z A. Takovou hranu lze do A přidat. Pokud se někdo k takto (či ekvivalentně) podanému důkazu ve svém řešení blížil a já si toho nevšiml, může se mi s podrobným zdůvodněním ozvat a může dostat přidáno. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min Jméno: Místnost: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 1 20 bodů Vašim úkolem je sestrojit a nakreslit všechny neisomorfní stromy (jednoduché souvislé acyklické grafy) na 7 vrcholech. Rozepište ve stručných a srozumitelných bodech, jak jste postupovali. Všechny kroky také správně zdůvodněte. (Kromě správnosti a úplnosti odpovědí se hodnotí také systematičnost vašeho přístupu k sestrojení požadovaných grafů, ze kterého musí vyplývat, že jste prošli všechny možnosti.) Řešení: Tento příklad kupodivu nepůsobil až takové problémy, jaké jsem čekal. Vedli jste si obecně velmi dobře a systematicky. Celkový počet stromů byl 11. Pokud některý výjimečně chyběl, strhlo se pár bodů, ale mnohem větší ztráty byly důsledkem (poměrně řídkých) chyb v systematičnosti. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min Jméno: Místnost: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 2 20 bodů Je dán jednoduchý graf na 12 vrcholech: s s s s ss s s s s ss Vašim úkolem je zodpovědět správně následující čtyři otázky o tomto grafu. V odpovědi nestačí uvést jen správný výsledek, ale nutné je i stručné zdůvodnění jeho správnosti (na přiloženém obrázku). a) Vyznačte v grafu některou Hamiltonovskou kružnici (procházející všemi vrcholy). b) Jaká je barevnost tohoto grafu? c) Jakou velikost má největší nezávislá množina v tomto grafu? d) Jaká je nejdelší indukovaná cesta v tomto grafu? Řešení: a) Obvykle jste správně nalezli Hamiltonovskou kružnici. b) Barevnost grafu je 3, menší být nemůže kvůli přítomnosti trojúhelníku. c) Nezávislá množina je velikosti nejvýše 4, ale problémy často dělalo správné zdůvodnění. V těchto případech bylo nejjednodušší si celý graf rozdělit na vhodné 3 disjunktní podgrafy a zdůvodňovat podle nich. . . d) Nejdelší indukovaná cesta má délku 7 a šikovně zdůvodnit, že delší není, je možné například vhodnou kombinací úvah o trojúhelnících ­ z každého může indukovaná cesta využít jen jednu hranu. Části byly hodnoceny po 5 bodech, přičemž zhruba polovina byla za zdůvodnění. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min Jméno: Místnost: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 3 20 bodů Z přednášek víme, že každý jednoduchý rovinný graf musí obsahovat vrchol stupně menšího než 6. a) Sestrojte jednoduchý rovinný graf, který má více než 10 vrcholů, ale jen méně než 10 jeho vrcholů má stupně menší než 6. b) Zjistěte, pro jaké nejmenší číslo b platí, že existuje jednoduchý rovinný graf s minimálním stupněm 4 a maximálním stupněm aspoň 6, v němž nejvýše b vrcholů má stupně menší než 6. Svou odpověď matematicky dokažte (včetně zdůvodnění, proč menší b není možné). Řešení: a) Obvykle jste nalézali dost podobné grafy, ale to je tím, že bylo docela přirozené a snadné je nalézt. Za správný graf bylo 5 bodů, přičemž plný počet ale dostal jen ten, kdo i slovně okomentoval, proč graf splňuje podmínku zadání. (Jen obrázek bez popisu je nejvýše za 4.) b) Nejmenší možné b je 6. Za nalezení příslušného příkladu bylo až 5 bodů a zbylých 10 bylo pro ty, kteří nalezli správné zdůvodnění, že menší b není možné. Ve variantě B bylo nalezení správného příkladu mnohem snažší, a proto jsem ve variantě A uděloval body i za nalezení horšího příkladu s b = 5. Dolní odhad správně zdůvodnili jen někteří. Není to přitom vůbec těžké, stačí dosadit počty vrcholů jednotlivých stupňů do omezení 3v - 6 pro počet hran jednoduchého rovinného grafu. Na druhou stranu žádné pokusy zdůvodňovat správnost b tím, že zrovna do vašeho obrázku už nelze vrcholy či hrany přidávat, nejsou korektní a nebyly honorovány. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min Jméno: Místnost: Souřadnice: list učo body Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 4 20 bodů Mějme libovolný konečný graf G = (V, E). O množině hran F E řekneme, že je nezávislá, pokud každá souvislá komponenta podgrafu G = (V, F) obsahuje nejvýše jednu kružnici. (Je to tedy jiná definice nezávislosti hran v grafu, než jsme měli na přednášce u matroidů.) Vašim úkolem je dokázat, že množina E hran grafu G spolu s touto definicí nezávislosti tvoří matroid. (Neboli musíte vypsat a ověřit tři axiomy nezávislých množin matroidu podle této definice.) Řešení: Je vidět, že tento příklad byl pro vás nejobtížnější, třebaže v něm nejde o moc více než správně aplikovat definice. Kdo správně vypsal všechny tři axiomy matroidu, získal 1 bod (za to není důvod udělovat více, zvláště když jste je mohli mít zapsanou na taháku). Kdo k těm axiomům správně doplnil důkaz prvních dvou v daném případě, získal celkem až 5 bodů ­ přitom tato část byla velmi jednoduchá. Zbylých 15 bodů pak bylo pro ty, kteří se poperou s důkazem splnění třetího (výměnného) axiomu, ale zůstaly u všech skoro nevyužity. Zde naznačím, jak se třeba v důkaze třetího axiomu dá postupovat (a jsou mnohé jiné možnosti): * Uvažujme obecně multigraf G na vrcholech V . Máme |A| < |B| a obě tyto množiny hran v G jsou nezávislé. Klíčové je si všimnout, že pokud kontrahujeme libovolnou hranu v A, co není smyčkou, zůstane A nezávislá. * Nechť tedy f = uv je hranou A, ne smyčkou, na vrcholech V . Potom i A = A - {f} na V = V - {v} (tj. výsledek kontrakce f) je nezávislá. Na druhou stranu, pokud B má cyklickou komponentu obsahující u ­ zmíněný konec f, odstraníme kružnici této komponenty vypuštěním některé hrany f B, tj. B = B - {f}. (Jinak snadno B = B.) I zde je pak po ztotožnění v s u bude množina B na V nezávislá. Postupujeme indukcí podle počtu vrcholů, takže nyní už máme hranu e B - A takovou, že A {e} na V je nezávislá. Lze dokázat, že i před kontrakcí f byla A {e} nezávislá. To přesně potřebujeme. * Zbývá dodělat základ indukce, kdy všechny hrany A jsou smyčky. Jelikož |A| < |B| a B je také nezávislá, musí hrany B pokrýt i některé vrcholy, které nejsou pokryty smyčkami z A. Takovou hranu lze do A přidat. Pokud se někdo k takto (či ekvivalentně) podanému důkazu ve svém řešení blížil a já si toho nevšiml, může se mi s podrobným zdůvodněním ozvat a může dostat přidáno. Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.