WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 | 4 |

3.7. Дано множество U из n элементов и в нем подмножества A из k элементов и B из l элементов, причем | A B | m. Найти число подмножеств X U, удовлетворяющих условию:

1) X A, X B ; 3) A B X A ;

2) X A, X B ; 4) X A B.

3.8. Сколько раз в десятичной записи всех натуральных чисел, меньших 10n, встречается цифра 9 Цифра 0 3.9. Сколько делителей у числа 2048 2310 2880 Сколько делителей имеет k ks число p11...ps, где p1,..., ps –различные простые числа, k1,...,ks – целые неотрицательные 3.10. Сколько слов длины n в q –буквенном алфавите, в которых любые две соседние буквы различны 3.11. Каким числом способов можно на обычной шахматной доске разместить белую и черную ладьи так, чтобы они не атаковали друг друга 3.12. Каким числом способов можно на шахматной доске поместить черного и белого королей так, чтобы они не атаковали друг друга 3.13. Сколько матриц с n столбцами и m попарно различными строками можно составить из элементов 0 и 1 3.14. Сколько имеется перестановок из элементов 1,2,...,n, в которых 1) 1 стоит раньше 2 2) 1 и 2 не стоят рядом 3) между 1 и 2 расположены k других элементов 4) 1 стоит не на первом месте, 2 – не на втором 3.15. Сколькими способами можно расставить восемь ладей на обычной шахматной доске так, чтобы они не угрожали друг другу, т.е. чтобы никакие две из них не стояли на одной вертикали или горизонтали 3.16. Сколько имеется пятизначных десятичных чисел, у которых 1) все цифры различны;

2) есть одинаковые цифры;

3) все цифры различны, причем последняя не 0;

4) все цифры различны, причем первая не 9, а последняя не 0;

5) две первых цифры различны, а две последних –одинаковы;

6) сумма цифр четна 3.17. Сколько отношений линейного порядка можно определить на множестве из n элементов 3.18. Каким числом способов можно разместить n различных предметов по k различным ящикам Сколько таких размещений, если в каждый ящик укладывается не более одного предмета 3.19. Сколько существует отображений множества A в множество B, если | A | n, | B | m Сколько среди них инъективных Биективных 3.20. Сколько имеется вариантов выбора трех призеров среди n участников конкурса 1) с указанием занимаемых ими мест 2) без указания мест 3.21. Имеется n1 разных книг одного автора, n2 – второго и n3 – третьего. Каким числом способов можно выбрать 1) две книги одного автора;

2) три книги одного автора;

3) одну книгу первого автора, две – второго и три – третьего 3.22. Каким числом способов можно разделить 10 юношей на две баскетбольные команды по 5 человек в каждой 3.23. На плоскости расположены n точек, никакие три из которых не лежат на одной прямой. Сколько существует треугольников с вершинами в данных точках 3.24. На одной из двух параллельных прямых зафиксировано n точек, а на другой m точек. Сколько имеется треугольников (четырехугольников) с вершинами в данных точках 3.25. Дано множество U из n элементов и в нем подмножество A из k элементов. Определите число подмножеств B U, удовлетворяющих условию:

1) | B A | 2 ;

2) B A 3, A B 4; 3) A B 1.

3.26. Из колоды, содержащей 52 карты, вынули 10 карт. Сколькими способами это можно сделать В скольких случаях среди этих карт окажется:

1) хотя бы один туз;

2) ровно один туз;

3) ровно четыре туза;

4) не менее двух тузов;

5) ровно два туза 3.27. Имеется колода из 4n карт четырех мастей, по n карт каждой масти, занумерованных числами 1,2,...,n. Каким числом способов можно выбрать пять карт так, чтобы среди них оказались:

1) пять карт одной масти с последовательными номерами;

2) четыре карты с одинаковыми номерами;

3) три карты с одним номером и две карты с другим;

4) пять карт одной масти;

5) пять карт с последовательными номерами;

6) три карты с одинаковыми номерами;

7) две карты с одинаковыми, остальные с разными номерами.

3.28. Сколько имеется пятизначных десятичных чисел, у которых 1) цифры идут слева направо в возрастающем порядке;

2) ровно три цифры четные;

3) не менее двух четных цифр 3.29. Каким числом способов из 10 человек можно выбрать три комиссии, если в первой и во второй комиссиях должно быть по 3 человека, а в третьей человек, и ни один из членов первой комиссии не должен входить во вторую и третью 3.30. Каким числом способов можно расположить n нулей и k единиц в последовательность так, чтобы никакие две единицы не стояли рядом 3.31. Каким числом способов можно распределить n одинаковых монет между k лицами так, что каждый получает 1) не более одной монеты;

2) не менее одной монеты 3.32. Каким числом способов можно рассадить n мужчин и m женщин вдоль одной стороны прямоугольного стола так, чтобы никакие две женщины не сидели рядом 3.33. Траекторией назовем ломаную линию на плоскости, состоящую из отрезков, параллельных координатным осям, причем длины отрезков – целые числа, а при движении вдоль ломаной от начальной точки каждый вертикальный отрезок проходится снизу вверх, а горизонтальный – слева направо. Найдите число траекторий, начинающихся в точке (0,0), а оканчивающихся 1) в точке (m, n) ;

2) на прямой x y n.

3.34. Сколько диагоналей у выпуклого n -угольника Найдите число точек пересечения этих диагоналей (не считая вершин), если известно, что в каждой из этих точек пересекаются только две диагонали 3.35. В множестве U из n элементов найдите число пар подмножеств ( A, B), удовлетворяющих условиям:

1) B A; 4) | A B | m, | A B | k ;

2) A B ;

5) A B B A k ;

3) | A B | k ; 6) | A B | 1.



3.36. Сколькими способами можно выбрать 6 карт из колоды, содержащей карты, так, чтобы среди них были карты каждой масти 3.37. Каким числом способов можно составить букет из n цветов трех видов, если все цветы одного вида одинаковы и имеется неограниченный запас цветов каждого вида 3.38. Сколько имеется пятизначных десятичных чисел, у которых цифры идут слева направо в неубывающем порядке 3.39. Определите число целых положительных (целых неотрицательных) решений уравнения x1 x2... xk n.

3.40. Каким числом способов можно распределить n одинаковых монет между k лицами 3.41. Сколько различных слов можно составить, переставляя буквы в слове “математика” 3.42. Каким числом способов можно разместить 7 студентов в трех комнатах общежития, если 1) в одной комнате имеется одно, в другой – два, в третьей – четыре свободных места;

2) в одной комнате имеется два, в другой – три, в третьей – четыре свободных места 3.43. Код замка состоит из пяти десятичных цифр. Известно, что среди них один раз встречается цифра 0 и дважды цифра 3. Сколько комбинаций нужно перебрать, чтобы наверняка открыть замок 3.44. Каким числом способов можно разбить 14 человек на 7 пар 3.45. Чему равен коэффициент при x4 y8 в разложении 1 x y20 3.46. Каким числом способов можно kn различных предметов разложить по n одинаковым (неразличимым) ящикам так, чтобы в каждом ящике оказалось ровно k предметов 3.47. Среди сотрудников фирмы семнадцать человек знают английский язык, десять – немецкий, семеро – французский. Три человека знают английский и французский, два – немецкий и французский, четверо – английский и немецкий.

1) Сколько человек работает в фирме, если каждый знает хотя бы один язык, а два человека знают все три языка 2) Сколько сотрудников, не знающих ни одного иностранного языка, если в фирме работает тридцать человек и никто из них не знает всех трех языков 3.48. На одной из кафедр университета работают тринадцать человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро – немецкий, шестеро – французский. Пятеро знают английский и немецкий, четверо – английский и французский, трое – немецкий и французский.

1) Сколько человек знают все три языка 2) Сколько человек знают ровно два языка 3) Сколько человек знают только английский язык 3.49. Сколько имеется натуральных чисел, не превосходящих 1000, которые 1) делятся на 3 или на 5;

2) не делятся ни на одно из чисел 2, 3, 5 3.50. Из 100 опрошенных студентов 50 программируют на алгоритмическом языке Си++, 53 - на Паскале, 42 - на Бейсике, 15 студентов могут программировать на Си++ и на Бейсике, 20 студентов - на Паскале и Бейсике, 25 - на Си++ и Паскале, а 5 студентов программируют на всех трех языках.

1) Сколько студентов не могут программировать ни на одном из перечисленных языков 2) Сколько студентов программируют хотя бы на одном из перечисленных языков 3) Сколько студентов программируют только на Паскале 4) Сколько студентов не программируют ни на Си++, ни на Паскале 3.51. Дано множество U из n элементов. Каким числом способов в нем можно выбрать три подмножества A, B, C так, чтобы выполнялись заданные условия:

1) n 7, | (A B) C | 6, | C (A B) | 2;

2) n 6, | A B | 5, | A (B C) | 1;

3) n 7, | (A B) C | 4, | C (A B) | 1;

4) n 6, | (A B) C | 4, | A B C | 1;

5) n 8, | A B C | 4, | A B | 1.

3.52. Рассматриваются слова в алфавите a1,a2,,aq. Через ni обозначается число вхождений буквы ai в слово. Требуется подсчитать число слов длины n, удовлетворяющих данным условиям:

1) q 5, n 8, n1 n2 n3 2 ;

2) q 4, n 8, n2 n1 2 ;

3) q 3, n 9, n1 n2 n3;

4) q 3, n 9, 2n1 n2 n3 ;

5) q 5, n 7, n1 n2 n3 2, n4 3.

3.53. Сколькими способами можно переставить буквы слова:

1) «периметр», чтобы «е» шла непосредственно после «р»;

2) «поговорка», чтобы согласные шли в алфавитном порядке;

3) «профессор», чтобы не менялся порядок гласных букв;

4) «корректор», чтобы три буквы «р» не шли подряд.

4. Теория графов Терминология и обозначения Граф G (V, E) задается непустым множеством вершин V и множеством ребер E, состоящим из пар элементов V. Если рассматриваются неупорядоченные пары, граф называется неориентированным, если упорядоченные – ориентированным. Если ребро a,b принадлежит графу, то вершины a и b называют смежными. Ребро вида (a,a) называется петлей. Неориентированный граф без петель называют обыкновенным. Во всех задачах этого раздела, где термин “граф” употребляется без уточнения, имеются в виду обыкновенные графы.

Графы G1 (V1, E1) и G2 (V2, E2) называют изоморфными, если существует биекция f : V1 V2, такая, что для любых a,bV1 a,b E1 тогда и только тогда, когда f (a), f (b) E2. Эта биекция f называется изоморфизмом графа G1 на граф G2. Если графы G1 и G2 изоморфны, то пишем, что G1 G2. Отношение изоморфизма графов есть отношение эквивалентности, так как оно рефлексивно, симметрично и транзитивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны.

Степень вершины a – количество смежных с ней вершин, обозначается через d(a). Набор степеней графа – упорядоченная по неубыванию последовательность степеней вершин.

Для графа G (V, E) справедливо соотношение d(a) 2m, где m - число aV ребер графа.

Дополнительный граф к графу G (V, E) – такой граф G (V, E ), у кото рого V V, а a,b E тогда и только тогда, когда a,b E.





Подграф графа G (V, E) – такой граф G' (V ', E'), что V ' V, E' E.

Остовный подграф графа G (V, E) – такой граф G' (V ', E'), у которого V 'V, E' E, т.е. остовный подграф получается из исходного графа удалением только ребер без удаления вершин.

Порожденный подграф графа G (V, E) – такой граф G' (V ', E'), у которого V ' V, E' { (a,b) E a,bV '}, т.е. порожденный подграф получается из исходного графа удалением вершин и всех ребер, инцидентных удаленным вершинам.

Последовательность вершин a1,a2,...,ak, такая, что ai,ai1 E для всех i 1,...,k 1, называется маршрутом, соединяющим вершины a1 и ak. Длина маршрута – число ребер k 1.

Путь - это маршрут, в котором все ребра различны. Простой путь – путь, в котором все вершины различны.

Цикл – это замкнутый путь, в котором a1 ak и все ребра различны. Простой цикл – цикл, в котором вершины a1,...,ak1 различны.

Связный граф – такой граф, в котором для любых двух вершин имеется маршрут, соединяющий эти вершины.

Компонента связности графа – связный подграф, не содержащийся в большем связном подграфе.

Перешеек – ребро, при удалении которого увеличивается число компонент связности.

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

Диаметр графа – максимальный среди всех эксцентриситетов вершин.

Радиус графа – минимальный среди всех эксцентриситетов вершин.

Центральная вершина – вершина, эксцентриситет которой равен радиусу графа. Центр графа – множество всех центральных вершин.

Эйлеров цикл – цикл, проходящий через все ребра графа. Граф, который имеет эйлеров цикл, называется эйлеровым графом.

Критерий эйлеровости графа. Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

Гамильтонов цикл – простой цикл, проходящий через все вершины графа.

Граф, который имеет гамильтонов цикл, называется гамильтоновым графом.

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

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

Дерево – связный граф, не имеющий циклов. Лес – граф, не имеющий циклов. Лист в дереве – вершина степени 1.

Пусть T - дерево с n вершинами. Будем считать, что его вершинами являются натуральные числа 1, 2,…, n. Пусть a1 — наименьший лист в T, а b1 — смежная с ним вершина. Удалив из T вершину a1 и ребро e1 (a1, b1), получим дерево T1, к которому также применим описанную процедуру. Повторяем ее до тех пор, пока после удаления вершины an2 и ребра en2 (an2,bn2) не получим дерево Tn2, состоящее из одного ребра en1 (an1,bn1). Дереву T ставим в соответствие упорядоченный набор чисел p(T ) b1,..., bn2, который называется кодом Прюфера.

Пусть V 1, 2,...,n, n 3. Опишем процедуру восстановления по коду Прюфера p(T ) b1,...,bn2, где bi V для всех i 1,...,n 2, дерева T, вершинами которого являются элементы множества V. Находим наименьший элемент a1 множества V, не содержащийся среди элементов последовательности p(T ), и восстанавливаем ребро (a1,b1) дерева. Далее удаляем a1 из V и первую компоненту b1 из последовательности p(T ). Продолжаем процедуру для оставшихся чисел, пока не будут удалены все компоненты последовательности p(T ). Два оставшихся элемента множества V - есть последнее ребро дерева T.

Корневое дерево - дерево с выделенной вершиной, которая называется корнем дерева.

Kn – полный граф с n вершинами, т.е. граф, в котором любые две вершины смежны. On – пустой граф с n вершинами, т.е. граф, в котором никакие две вершины не смежны.

K – полный двудольный граф. В нем множество вершин можно разбить p,q на две части V1 и V2, причем |V1 | p, |V2 | q, и две вершины смежны тогда и только тогда, когда они принадлежат разным долям.

Qn –n-мерный куб. Вершинами этого графа являются все двоичные наборы длины n и две вершины смежны тогда и только тогда, когда соответствующие наборы отличаются ровно в одной позиции.

Pn - простой путь с n вершинами.

Cn - простой цикл с n вершинами.

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

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

Для связного плоского графа G (V, E) с n вершинами и m ребрами имеет место формула Эйлера n f m 2, где f - общее число граней графа.

Во всяком связном планарном графе с n ( n 3) вершинами и m ребрами имеет место неравенство m 3 (n 2).

Во всяком связном планарном графе с n ( n 3) вершинами и m ребрами, не содержащем циклов длины три, имеет место неравенство m 2 (n 2).

Во всяком связном планарном графе с n ( n 3) вершинами и m ребрами, не содержащем циклов длины меньше k (k 3), имеет место неравенство k m (n 2).

k Операция подразбиения ребра (a,b) в графе G (V, E) состоит в удалении ребра (a,b) и добавлении двух новых ребер (a,c), (c,b), где c - новая вершина.

Графы G и G называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ребер.

Pages:     | 1 || 3 | 4 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.