Дискретна математика и теория на графите - задачи с решения

Решение:
В прост граф (без примки и кратни ребра) всеки връх може да е съседен само на останалите [tex]n-1[/tex] върха, затова степента на всеки връх принадлежи на множеството [tex]\{0; 1; \ldots; n-1\}[/tex], което има [tex]n[/tex] елемента.
Стойностите [tex]0[/tex] и [tex]n-1[/tex] не могат да се срещнат едновременно: връх от степен [tex]n-1[/tex] е съседен на всички останали върхове и тогава няма връх от степен [tex]0[/tex]. Следователно [tex]n[/tex]-те степени приемат най-много [tex]n-1[/tex] различни стойности — от едно от множествата
[tex]\{0; 1; \ldots; n-2\}\text{ или }\{1; 2; \ldots; n-1\}[/tex]
По принципа на Дирихле два от [tex]n[/tex]-те върха имат равни степени.

Решение:
Използваме, че [tex]\overline{u}=u\oplus 1[/tex] и [tex]1\oplus 1=0[/tex]. Първо заместваме променливите с техните отрицания:
[tex]f(\overline{x},\overline{y})=(x\oplus 1)\oplus(y\oplus 1)\oplus 1=x\oplus y\oplus 1[/tex]
След това вземаме отрицанието на резултата:
[tex]f^*(x,y)=\overline{x\oplus y\oplus 1}=x\oplus y\oplus 1\oplus 1=x\oplus y[/tex]
Проверка с таблицата на истинност: при [tex](x; y)[/tex], равно на [tex](0; 0)[/tex], [tex](0; 1)[/tex], [tex](1; 0)[/tex], [tex](1; 1)[/tex], функцията [tex]f[/tex] приема стойностите [tex]1; 0; 0; 1[/tex], а [tex]f^*[/tex] — стойностите [tex]0; 1; 1; 0[/tex], т.е. [tex]f^*=\overline{f}[/tex].
Честа грешка е да се пресметне само [tex]f(\overline{x},\overline{y})[/tex] и да се пропусне външното отрицание; така се получава самата [tex]f[/tex], т.е. грешният отговор [tex]x\oplus y\oplus 1[/tex].

Решение:
Нека [tex]A[/tex] е матрицата на съседство на [tex]G[/tex]. Елементът [tex](A^k)_{ij}[/tex] е равен на броя на маршрутите с дължина [tex]k[/tex] от [tex]v_i[/tex] до [tex]v_j[/tex] (индукция по [tex]k[/tex]: маршрут с дължина [tex]k+1[/tex] е маршрут с дължина [tex]k[/tex], последван от още едно ребро). В частност [tex](A^2)_{ij}[/tex] е броят на общите съседи на [tex]v_i[/tex] и [tex]v_j[/tex] (степента на [tex]v_i[/tex] при [tex]i=j[/tex]). Множествата от съседи на върховете са:
[tex]N(v_1)=\{v_3,v_4,v_5\}; \quad N(v_2)=\{v_4,v_5\}; \quad N(v_3)=\{v_1,v_5\}[/tex]
[tex]N(v_4)=\{v_1,v_2,v_5\}; \quad N(v_5)=\{v_1,v_2,v_3,v_4\}[/tex]
Вторият ред на [tex]A^2[/tex] (общите съседи на [tex]v_2[/tex] с [tex]v_1,\ldots,v_5[/tex]) е [tex](2; 2; 1; 1; 1)[/tex], а петият стълб (общите съседи на [tex]v_5[/tex] с [tex]v_1,\ldots,v_5[/tex]) е [tex](2; 1; 1; 2; 4)[/tex]. Тъй като [tex]A^4=A^2A^2[/tex], получаваме
[tex](A^4)_{25}=\sum_{k=1}^{5}(A^2)_{2k}(A^2)_{k5}=2\cdot 2+2\cdot 1+1\cdot 1+1\cdot 2+1\cdot 4=13[/tex]

Решение:
Това е линейно нехомогенно рекурентно уравнение с постоянни коефициенти. Характеристичното уравнение [tex]r^2-3r+2=0[/tex] има корени [tex]r_1=1[/tex] и [tex]r_2=2[/tex], затова общото решение на хомогенното уравнение е [tex]C_1+C_2\cdot 2^n[/tex].
Дясната страна е константата [tex]1=1\cdot 1^n[/tex], а [tex]1[/tex] е прост корен на характеристичното уравнение, затова търсим частно решение във вида [tex]p_n=Cn[/tex] (една константа би се погълнала от решението на хомогенното уравнение):
[tex]Cn=3C(n-1)-2C(n-2)+1=Cn+C+1\Rightarrow C=-1[/tex]
Следователно [tex]a_n=C_1+C_2\cdot 2^n-n[/tex]. От началните условия:
[tex]\begin{cases}C_1+2C_2-1=1\\ C_1+4C_2-2=2\end{cases}\Rightarrow C_2=1; \ C_1=0[/tex]
Значи [tex]a_n=2^n-n[/tex]. Проверка:
[tex]a_3=3\cdot 2-2\cdot 1+1=5=2^3-3; \qquad a_4=3\cdot 5-2\cdot 2+1=12=2^4-4[/tex]

Решение:
Да допуснем, че [tex]G[/tex] не съдържа цикъл. Нека [tex]u[/tex] е единственият връх от степен [tex]1[/tex], а [tex]K[/tex] е компонентата на свързаност на [tex]G[/tex], която съдържа [tex]u[/tex]; тя съдържа поне реброто между [tex]u[/tex] и неговия съсед. Тъй като [tex]K[/tex] е крайна, в нея има най-дълъг път
[tex]P=w_0w_1\ldots w_k,\quad k\ge 1[/tex]
Нека [tex]x[/tex] е съсед на [tex]w_0[/tex], различен от [tex]w_1[/tex]. Ако [tex]x[/tex] лежи на [tex]P[/tex], т.е. [tex]x=w_j[/tex] при [tex]j\ge 2[/tex], то [tex]w_0w_1\ldots w_jw_0[/tex] е цикъл. Ако [tex]x[/tex] не лежи на [tex]P[/tex], то [tex]xw_0w_1\ldots w_k[/tex] е по-дълъг път. И двете са невъзможни, затова [tex]w_0[/tex] няма други съседи освен [tex]w_1[/tex] и степента му е [tex]d(w_0)=1[/tex]. Аналогично [tex]d(w_k)=1[/tex].
Тъй като [tex]k\ge 1[/tex], върховете [tex]w_0[/tex] и [tex]w_k[/tex] са различни и [tex]G[/tex] има поне два върха от степен [tex]1[/tex], което противоречи на условието. Следователно [tex]G[/tex] съдържа цикъл.