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

Решение:
В простом графе (без петель и кратных рёбер) каждая вершина может быть смежна только с остальными [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] содержит цикл.