Дискретная математика. Задачи

Полужирным  выделены задачи и  ответы.

Курсивом  выделены комментарии, непосредственно  не относящиеся к  решению. 

2. Какие из трех  указанных графов  являются изоморфными,  а какие – неизоморфными?  Для изоморфных  графов указать  соответствие вершин, сохраняющее смежность. Для неизоморфных пояснить причину.  

 

Граф G называется изоморфным графу H, если существует биекция φ из множества вершин графа G во множество вершин графа H, сохраняющая отношение смежности (т.е. если две вершины a и b были смежны в G, то вершины φ(a) и φ(b) будут смежны в H).

В данном случае будут изморфны первый и второй графы и неизоморфны между собой первый и третий, а значит и второй и третий графы.

Изоморфизм первого (A) и второго (B) графа можно показать, например, такой нумерацией вершин:

Покажем изоморфизм: вершина 1 смежна (соединяется рёбрами) с вершинами 2, 4 и 5 в графе A, и вершина 1 смежна с 2, 4 и 5 в графе B. Аналогично:

Т.е. смежные  в A вершины смежны и в B.

Для первого  и третьего графа такой нумерации (т.е. такого изоморфизма) построить  не удаётся, а значит нет её и для второго и третьего графа (иначе можно было бы перевести второй граф в первый, а затем в третий). В частности мешают переставленные вершины 5 и 8 (см. граф A).

(Комментарий: проблема установки изоморфизма графа – NP-полная задача, а значит решается просто перебором. Можно увидеть, что первый граф можно «вывернуть» во второй, двигая его вершины по плоскости, а в третий его «вывернуть» не получится). 

4. Два колеса, степень  центральных вершин  которых равна  a и b, соединены ребром. Найти вершинное хроматическое число полученного графа для a=15, b=18.

Хроматическое число графа – наименьшее количество красок, которое требуется для  раскраски вершин графа так, чтобы  никакие две смежные вершины  не были раскрашены в одинаковые цвета (вместо цветов часто просто нумеруют вершины).

Граф «колесо» выглядит так:

В данном случае степень центральной вершины 8 (она соединена с 8-мью вершинами на «ободе»). Любое «колесо» с четной степенью центральной вершины (в том числе и 18) можно раскрасить тремя красками, например, так (1,2,3 – номера красок):

По «ободу»  краски чередуются, а центральная  вершина имеет свою раскраску.

Любое «колесо» с нечетной степенью центральной  вершины (в том числе и 15) можно  раскрасить четырьмя красками, например, так:

Краски по «ободу»  чередуются, но последней вершине  в чередовании требуется своя краска, чтобы отличаться от первой, предпоследней и центра.

Соединив два  колеса с чётной и нечётной степенью центральной вершины (a=15, b=18), получим следующий граф:

Хроматическое число графа будет наибольшим хроматическим числом всех компонент  этого графа. Левое колесо с a=15 имеет  хроматическое число 4, а значит и  весь граф имеет хроматическое число 4. На рисунке представлена такая раскраска графа четырьмя красками.

Ответ: χ=4. 

5. Найти число векторов (х₁,…. x_n), координаты которых выбираются из множеств:

а)

б)

в) и . 

а) первый элемент  вектора x₁ может быть выбран k способами (в множестве {0,1,…, k-1} ровно k элементов). Второй элемент тоже можно выбрать k способами. Третий тоже и тд. Все элементы вектора независимы друг от друга, поэтому число векторов будет k*k*…*k (n раз) = kⁿ. (формула для числа размещений из комбинаторики).

Ответ: kⁿ

б) первый элемент  вектора может быть выбран k₁ способами, второй – k₂, третий – k₃ и тд. Элементы вектора независимы друг от друга, поэтому число векторов будет k₁*k₂*…*k_n= . (если бы k₁=k₂=…=k_n, то получили бы предыдущий случай)

Ответ: .

в) очевидно, что  сумма x₁+x₂+…+x_n из нулей и единиц может быть равна r тогда и только тогда, когда в ней ровно r единичных элементов (а остальные n-r – нули). Всего необходимо выбирать n таких элементов. Число способов разместить r элементов (r единиц) в n координат вектора называется числом размещений без повторений и обозначается , или A(n,r). По формуле для числа размещений без повторений A(n,r)= .

Ответ:. 

6. Найти n, если в разложении (х + 1)ⁿ коэффициенты при х⁵ и х¹² равны. 

Выражение (x+1)ⁿ можно разложить по формуле для бинома Ньютона:

Коэффициенты  разложения C(n,i) называются биномиальными  коэффициентами. Для них выполняется  следующее свойство: C(n,m)=C(n,n-m) (можно проверить, если записать C(n,m)=).

Нам известно теперь, что C(n,5)=C(n,12). Используя свойство, получаем, что C(n,5)=C(n,n-5)=C(n,12). Откуда n-5=12, а значит n=17.

Ответ: n=17. 

7. Найти число целых  положительных чисел,  не превосходящих 1000 и не делящихся ни на одно из чисел: 6, 9, 17.

Количество чисел, делящихся на 6 и небольших 1000, будет 166 (166*6=996, а уже 167*7=1002).

Количество чисел, делящихся на 9 и небольших 1000, будет  111 (111*9=999).

Количество чисел, делящихся на 17 и небольших 1000, будет 58 (58*17=986).

Если мы отнимем  от 1000 все количества 166, 111 и 58, то получится, что мы, например, два раза вычтем те числа, которые делятся и на 6, и на 9.

Если число  делится и на 6, и на 9, то оно  делится и на 18 (на 3, на 3 и на 2). Количество чисел, делящихся на 18, будет 55 (55*18=990).

Если число  делится и на 6, и на 17, то оно  делится на 102 (на 2, на 3 и на 17). Количество таких чисел 9 (9*102=918).

Если число  делится и на 9, и на 17, то оно  делится на 153 (на 3, на 3 и на 17). Количество таких чисел 6 (6*153=918).

Теперь, если мы к разности добавим эти числа 18, 9 и 6, то мы добавим и числа, которые  делятся на 6, на 9 и на 17. Если число  делится на 6, на 9 и на 17, то оно  делится на 306 (на 2, на 3, на 3 и на 17). Количество таких чисел 3 (ну, собственно, это числа 306, 612 и 918).

В итоге, получаем количество чисел не превосходящих 1000 и не делящихся ни на 6, ни на 9, ни на 17: N=1000-(166+111+58)+(55+9+6)-3=732. В этом случае каждое делящееся число будет учтено ровно один раз.

Ответ: 732 числа. 

8. Найти решение  рекуррентного соотношения

Подставляя в рекуррентное соотношение a₀=1 и a₁=3, получаем значение для a₂:

a₂+2*3+1=0

a₂=-7

Аналогично, подставляя в соотношение a₁=3 и a₂=-7, получаем значения для a₃:

a₃+2*(-7)+3=0

a₃=11

Точно также  получим, что a₄=-15, a₅=19, a₆=-23, a₇=27 и тд.

Таким образом, получили ряд чисел: 3, -7, 11, -15, 19, -23, 27, -31, 35, -39, …

Знаки в этом ряду чередуются, значит знак n-ного числа  можно записать как (-1)^n-1, поскольку для начинается с положительного числа. Каждое последующее число отличается от предыдущего на 4, поэтому модуль каждого числа можно записать как 4*n-1. В итоге формула для a_n=(-1)^n-1(4n-1) и будет решением этого рекуррентного соотношения. Проверить можно, вычислив по этой формуле любой элемент, например, a₅=(-1)^5-1(4*5-1)=19, что совпадает со значением, вычисленным через подстановку.

Ответ: a_n=(-1)^n-1(4n-1).