сборник задач по дискретке другой вариант

20.Сколько имеется шестизначных чисел, у которых три цифры четные, а три — нечетные?

21.Сколько существует целых чисел от 0 до 999, которые не делятся ни на 5, ни на 7?

22.Среди всех чисел от 1 до 10n каких больше: тех, для записи которых используется цифра 9, или тех, которые записываются без нее?

23.Найти сумму четырехзначных чисел, получаемых при всевозможных перестановках цифр 1, 2, 3, 4.

24.Сколько способов разбить 12 человек на две группы по 7 и 5 человек так, чтобы:

а) два данных человека оказались в разных группах; б) в одной группе?

25.Сколькими способами можно посадить за круглый стол 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом?

26.Сколькими способами можно расставить 20 одинаковых (разных) книг в книжном шкафу с 5 полками (каждая полка может вместить все 20 книг), если

а) некоторые полки могут быть пустыми; б) на каждой полке должна быть хотя бы одна книга;

в) на каждой полке должно быть не менее трех книг?

27.Сколькими способами можно переставить n различных предметов так, чтобы ровно k (0 < k < n ) предметов остались на месте?

28.На конференции должны выступить докладчики A , B , C , D , E , F и G , причем B не может выступать раньше A . Сколькими

способами можно установить очередность выступлений?

29.На полке стоят k книг в черных переплетах и n книг в синих переплетах, причем все книги разные. Сколькими способами можно расставить книги так, чтобы книги в черных переплетах стояли рядом?

30.Сколькими способами можно расположить в ряд 10 белых и 4 черных шара так, чтобы черные шары не лежали рядом? Рассмотреть 2 случая: а) шары одного цвета неотличимы друг от друга, б) все шары разные.

61

31.Сколькими способами 4 черных шара, 5 белых шаров и 6 синих шаров могут быть разложены в 7 различных пакетов (некоторые пакеты могут быть пустыми), если а) шары одинаковые, б) шары разные?

32.Сколькими способами можно разложить 3 руб. и 10 полтинников в 4 различных пакета?

33.Сколько различных перестановок можно образовать из букв следующих слов: а) зебра, б) баран, в) водород, г) абракадабра?

34.Определить коэффициент k в одночлене ka3b4c3 многочлена (с приведенными подобными членами), получаемого из алгебраиче-

ского выражения (a + b + c)10 .

35. Определить коэффициент k в следующих членах многочлена (с приведенными подобными членами), получаемого из алгебраического выражения (a + b + c)2 (a2 + b2 + c2 )4 .

а) ka3b3c4 , б) ka2b4c4 , в) ka5b5 , г) ka2b2c6 .

37.Сколько делителей имеет число q = p1α1 p2α2 ...pnαn , где pi – различные простые числа, не равные единице, αi – некоторые натуральные числа? Чему равна сумма делителей?

38.Сколько существует целых чисел от 0 до 10n , в десятичной записи которых нет двух стоящих рядом одинаковых цифр?

39.Сколькими способами можно выбрать 6 карт из колоды, содержащей 52 карты, так, чтобы среди них были карты каждой масти?

40.Сколькими способами можно разместить n одинаковых шаров по m различным урнам при следующих условиях:

а) пустых урн нет; б) во второй урне k шаров;

s

в) в первых s урнах соответственно a1,a2 ,...as шаров (åak ≤ n);

k=1

г) в i -й урне не меньше чем ai , i =1,m шаров.

62

7.ТЕОРИЯ ГРАФОВ

1.Найдите все попарно неизоморфные графы третьего, четвертого порядка.

2.Среди приведенных на рисунке графов найдите все пары изоморфных графов.

3. Определите число ребер n- мерного куба.

64

4.Докажите, что сумма степеней всех вершин графа есть число, равное удвоенному числу ребер.

5.Докажите лемму о рукопожатиях: в любом графе число вершин нечетной степени четно.

6.Докажите, что не существует регулярного графа, порядок и степень которого нечетны.

7.Докажите, что в каждом графе найдутся две вершины с одинаковыми степенями.

8.Докажите следующие свойства маршрутов:

1). Всякий незамкнутый (u, v)- маршрут, содержит в себе простую (u, v)- цепь. В частности, любая (u, v)- цепь, содержит в себе простую (u, v)- цепь. Причем, если (u, v)- маршрут содержит в себе вершину w (w¹u и w¹v), то в общем случае, простая (u, v)- цепь может не содержать в себе вершину w.

2)Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.

3)Всякая непростая (u, v)- цепь, может быть разбита на простую (u, v)- цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.

4)Для любых трех вершин u, w, v из существования (u, w)- цепи их и (w, v)- цепи, следует существование (u, v)- цепи. Причем

может не существовать (u, v)- цепи, содержащей вершину w.

5)Объединение двух несовпадающих простых (u, v)- цепей содержит простой цикл.

6)Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.

9.Докажите, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)-маршрут.

65

10.Докажите, что, для любого графа либо он сам либо его дополнение является связным.

11.Пусть G –связный граф, eÎEG. Докажите, что граф G–e связен, если ребро e принадлежит какому-либо циклу графа G, иначе граф G–e имеет ровно две компоненты связности.

12.Докажите, что в (n, m)- графе, имеющем k компонент связности, выполняется неравенство n–k£m£(n–k)(n–k+1)/2.

13.Докажите, что если число ребер графа порядка n>2 больше, чем (n-1)(n-2)/2, то граф связен.

14.Докажите, что в связном графе любые две простые цепи максимальной длины имеют общую вершину.

15.Докажите, что если d(G)³(n–1)/2, то граф G связен.

16.В любом дереве порядка n³2 имеется не менее двух висячих вершин.

17.Граф, в котором число ребер не меньше, чем число вершин, содержит цикл.

18.Если в графе G порядка n³3, число висячих вершин равно числу ребер, то G либо не связен, либо дерево.

19.Доказать, что если у дерева есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина.

20.Доказать, что дерево, содержащее ровно две висячие вершины, является простой цепью.

21.Доказать, что лес из k деревьев, содержащий n вершин, имеет ровно n–k ребер.

22.Доказать, что граф содержит остовное дерево тогда и только тогда, когда он связен.

23.Докажите, что всякий ациклический подграф произвольного графа G содержится в некотором остове графа G.

24.Нарисуйте все попарно неизоморфные деревья седьмого порядка.

25.Найдите остовные деревья в графах K5, K3,3 и в графе Петерсона.

66

26.Докажите теорему Кёнига: для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечётной длины.

27.Докажите, что (n, m)- граф связен, если в нем отсутствуют циклы нечетной длины и m>(n–1)2/4.

28.Является ли граф, изображенный на рисунке, двудольным?

29.Докажите теорему Эйлера: для всякого связного плоского графа верно равенство: n–m+f=2, где n – число вершин графа, m – число ребер, f – число граней.

30.Докажите, что теорема Эйлера следующим образом обобщается на случай несвязного плоского (n, m)- графа: n–m+f=k+1, где k – число компонент связности графа.

31.Докажите, что число граней любой плоской укладки связного планарного (n, m)- графа постоянно и равно m–n+2.

32.Докажите, что для всякого планарного (n, m)-графа m£3n–6 при n≥3.

33.Докажите, что если в связном плоском (n, m)-графе граница каждой грани является r-циклом, r³3, то m(r–2)=r(n–2).

34.Для всякого связного планарного (n, m)- графа с n³3, обхват которого равен h³3, верно неравенство m(h–2)£h(n–2). Используя это соотношение, докажите что граф Петерсена непланарен.

35.Докажите, что для связного плоского (n, m)-графа с n³3, грани которого не являются треугольниками, верно неравенство m£2n–4.

36.Докажите, что всякая плоская триангуляция с n³3 вершинами имеет ровно 3n–6 ребер и 2n–4 грани.

37.Доказать, что графы K5 и K3,3 непланарны.

67

38.Доказать, что если число вершин плоской триангуляции не меньше четырех, то степень каждой вершины не менее трех.

39.Доказать, что всякий плоский граф является остовным подграфом некоторой плоской триангуляции.

40.Пусть G граф с n вершинами, причем 3<n<8, и G – его дополнительный граф, тогда, по крайней мере, один из них планарен.

41.Пусть G граф с n вершинами, причем n>11, и G – его дополнительный граф, тогда, по крайней мере, один из них непланарен.

42.Доказать, что всякий планарный граф с n³4 вершинами имеет по крайней мере 4 вершины со степенями, не превосходящими 5.

43.Докажите, что не существует плоского графа с пятью гранями, обладающего тем свойством, что любые две его грани имеют общее ребро.

44.Доказать, пользуясь теоремой Понтрягина-Куратовского, непланарность графа Петерсена и графов, приведенных ниже

45. При каких n графы порядка 2n, изображенные на рисунке, являются планарными?

68