Дискретни структури, Информатика, пролет 2022

1) Има решения на графовата задача, използващи ойлеров цикъл. Това е добре, но ойлеров цикъл може да не съществува в целия граф, понеже никъде не е казано, че графът е свързан. НДУ за съществуване на ойлеров цикъл е конюнкция от две съждения: всички върхове са от четна степен и графът е свързан. Решение с ойлеров цикъл е напълно валидно, ако се ограничи до свързаната компонента, която съдържа моста, чието съществуване сме допуснали.

2) В задачата за броя на булевите функции доста решения казват, че техният общ брой (при 20 променливи без други ограничения) е 2^(20^n). Това е безсмислица. 20 е на "втория етаж" (2^2^20), а n не е дефинирано.