зад 1: Твърди се, че най-дългият цикъл в H е с дължина 7. Не е вярно. И G, и H са Хамилтонови. В H, примерно, (1 6 7 4 0 3 2 5 1) . зад 5: Връх u да е свързан с друг връх v НЕ Е СЪЩОТО като u и v да са съседи. Ако имате предвид, че u и v са съседи, но пишете "u е свързан с v", допускате грешка. зад 7: Да се направи СъвДНФ на дадената ф-я, да се преобразува чрез диз. --> + и негация-u --> (u+1), да се отворят скобите и изразът да се опрости максимално, е мисията невъзможна в ограниченото време на изпита. зад 3: Целта на деф. на h(S) е да се обобщи нотацията "h( )" ЗА ПРОИЗВОЛНА ФУНКЦИЯ h и за МНОЖЕСТВО от елементи. Ние сме учили какво е h(a), където a е един елемент на домейна. Не сме въвеждали нотация "h(S)", където S е множество от елементи (от домейна). В зад. 3 се дефинира "h(S)" по най-естествения начин -- това е м-вото от елементите на кодомейна, които са образи на елементите на S. И така, решение на зад 3, което казва "разглеждаме ф-ята h(S) = ...", е безсмилица. По отношение на A, B и f, нито h е дефинирана, нито S е дефинирано. В дефиницията в началото, h и S са под квантор (неявно), като действието на квантора е до края на третия ред. Още веднъж: h НЕ Е ЧАСТ ОТ УСЛОВИЕТО НА ЗАДАЧАТА. зад 1: Не е достатъчно да се разгледат разстоянията d(1, x) за всеки връх x на G и H. Това, че връх 1 е нарисуван най-горе в рисунките на G и H по никакъв начин не задава смислено съответствие между връх 1 от G и връх 1 от H. Така че, ако се върви по този път, трябва да се разгледат разстоянията по всички върхове на единия от графите. Което е прекалено голямо усилие. В интерес на истината, посоченото решение е ОК предвид факта, че тези графи са върхово-транзитивни https://mathworld.wolfram.com/Vertex-TransitiveGraph.html но това е сложно нещо, излизащо извън рамките на курса. Ние не сме изучавали теорията, позволяваща да се разглеждат само d(1, x) в G и d(i, x) в H, за кой да е връх i. зад 5: Удивително много решения изразяват долните граници (за дължина на път и на цикъл) чрез n, а не чрез $\delta(G)$. Защо? В условието е чрез $\delta(G)$. По-лошо, много решения говорят за път с дължина поне n и цикъл с дължина поне n+1. В прост граф ТОВА Е НЕВЪЗМОЖНО. зад 2: Няколко решения съставят рекурентно уравнение |T(n)| = 3|T(n-1)| + 3|T(n-2)| + 4^(n-2) с начални условия 0 и 1. Не е това уравнението. Неговите решения започват с 0,1,7,40, а истинските започват с 0,1,8,48. Разсъжденията за +3|T(n-1)| и +4^(n-2) са коректни, но другото събираемо е +|T(n-1)|, а не 3|T(n-2)|. зад 5: $\delta(G) \geq 2$ НЕ ВЛЕЧЕ, че G е свързан. Контрапример: два K_3 без общи върхове. зад 6: Няколко решения на задача 6 са с брутална сила -- за всяка пресечна точка се намира броя на начините да се стигне до нея, съобразявайки се със забраните отсечки. Абстрактно говорейки, решението е коректно, ако сметките са коректни, но като алгоритъм то е неадекватно. Тоест, то е прекалено бавен алгоритъм. По същество това решение е запълване на част от триъгълника на Паскал, бавно, тромаво и систематично отгоре надолу. Това работи в тази задача само защото числата са малки. Ако мрежата беше 1000 на 500 с 4 забранени отсечки, решението с вкл/изкл щеше да е също толкова бърз алгоритъм (игнорирайки факта, че биномните коеф. щяха да са огромни и неизчислими на ръка), колкото и примерното решение. Докато тромавото решение щеше да е драстично бавно. На решения от този вид давам само 9 точки. Това е 1/3 от пълния брой. И то само ако са верни числено. Владеенето на метода на вкл/изкл е едно важно умение, което този курс се опитва да учи. Тромавият метод е нещо, което всеки със здрав разум би приложил от общи съображения. Методът с вкл/изкл е нещо неочевидно и МНОГО по-ефикасно като алгоритъм. Ако решавате задачата с тромавия метод, допускам, че не умеете да прилагате вкл/изкл. зад 1: Няколко решения отбелязват, че в H има 5-цикъл, а в G няма 5-цикъл, като посочват 5-цикъл в H, но не дават никаква аргументация на твърдението, че в G няма 5-цикъл. Това дава само 5 точки. Все пак, някаква аргументация за твърдението за G е необходима. Най-кратката арг. е, че G е двуделен с посочване на дяловете и на теоремата НДУ за двуделност. Някои колеги не са се изразили чрез двуделност, а методично са изследвали възможността в G да има нечетен цикъл и са установили, че не може. Това носи пълен брой точки, ако е направено коректно, но е времеемко, което пречи за останалите задачи. Но без абсолютно никаква аргументация, само 5т. На листовете с условията пише "... всичко друго трябва да се обоснове добре". "Очевидно е" не е добра обосновка. Същото и за решение, което забелязва, че G е планарен (това Е очевидно) и казва, че H не е планарен без д-во. H наистина не е планарен (този граф се нарича Mobius Ladder не случайно), но това трябва да се докаже чрез теоремата на Куратовски. H има подграф, хомеоморфен на K_{3,3}. Ако се посочи такъв, решението носи пълен брой точки. Без д-во за непланарността на H, само 5т зад 1: Няколко решения посочват несъответствия между двата графа, основаващи се на дадените имена на върховете. Това не работи. За да стане по този начин, трябва да разгледате всички 8! биекции : V(G) --> V(H) и да установите, че при всяка от тях има несъотвествие. Това няма как да стане на ръка. зад 5: Много решения доказват, че има път с дължина поне 2 и цикъл с дължина поне 3. В тази задача се иска нещо по-силно: път с дължина поне \delta(G) и цикъл с дължина поне \delta(G)+1. Това, че е казано, че \delta(G) \geq 2 НЕ ОЗНАЧАВА, че може да свалите долната граница на 2.