Изпит - дискретна математика

[cowwando]

Здравейте!

Имам изпит в Петък по Дискретна Математика и имам примерния вариант със задачите, които ще ми бъдат дадени.
Ако има желаещи да ги решат - предлагам заплащане!

Поздрави,
Антоан!

[cowwando]

Страница 2 от изпита.

[ptj]

1-ва е задача за 6-ти клас:
Отговора е "не", защото графа съдържа 2 върха от нечетна степен (A,I).

По-точно:
За всеки "път в граф" преминаването през връх, съдържа точно две ребра и съответно намаля с 2 степента на този връх. Тогава от съществуването на връх от нечетна степен следва, че всеки възможен ойлеров цикъл в графа може да започва и свършва само в него. Т.е. от наличието на 2 върха от нечетна степен следва несъществуването на ойлеров цикъл в графа.

[ptj]

4-та също е елементарна:
[tex]А^3=\{000;001;010;011;100;101;110;111\}[/tex]- двоичното представяне на числата от 0 до [tex]2^3-1[/tex].
[tex]М^2=\{010010\}[/tex]
[tex]L^2=\{00;001;010;100;0101;0110;1001;1010\}[/tex] (думата [tex]010[/tex] се получава по 2 начина, затова броя на думите е [tex]3^2-1[/tex])

[tex]\alpha=\{010\}^2=\{01\}\{0\}^2\{10\}\Rightarrow \alpha\in (M^2\cap L^4)\Rightarrow \alpha\in (M^*\cap L^*)[/tex]

[ptj]

3-та:
Алгоритъма на Дейкстра е с индукция по броя на върховете.
За всеки връх пазиш стойността на най-късия път до него и списък с върхове, съответстващи на този път. Когато прибавяш нов връх, просто намираш най-късия път до него като сума от вече наличните ти пътища до останалите върхове и реброто свързващо новия връх. Алгоритъма свършва с изчерпване множеството на върховете.

[ptj]

2-рата задача е с лошо формулирано условие. Не е ясно дали се търси минимално покриващо дърво, минимален хамилтонов цикъл или минимален път през всички върхове, не съдържащ цикли.