Сделай Сам Свою Работу на 5

Серия задач по комбинаторике на различные методы решения





 

1. При одном бросании монеты возможно 2 исхода: орел или решка. Сколько исходов возможно при 5 бросаниях монеты?

2. На конференции каждый из 30 участником обменялся рукопожатием со всеми остальными. Сколько было сделано рукопожатий?

3. Сколько диагоналей в 100-угольнике?

4. Сколько делителей у числа ?

5. Сколькими нулями оканчивается число 100!? (имеется в виду факториал).

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

7. На сколько частей делят плоскость 20 прямых, никакие две из которых не параллельны и никакие три не пересекаются в одной точке?

8. На какое наибольшее количество частей можно разделить круг n прямыми?

9. На какое наименьшее число прямых можно разделить круг n прямыми?

10. Сколько вариантов трехцветного флага из трех горизонтальных полос можно составить, если имеется выбор из шести цветов материи?

11. Пять писем разложены по пяти конвертам, по одному в каждом. Сколько способов разложить их так, чтобы ровно два письма попали не в тот конверт?

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

13. Есть 10 школьников: 5 мальчиков и 5 девочек. Сколько способов рассадить их на 10 стульев, стоящих в ряд, чтобы мальчики чередовались с девочками?



14. Сколько существует шестизначных чисел, в записи которых все цифры нечетны?

15. Сколько существует шестизначных чисел, в записи которых есть хотя бы одна четная цифра?

 

Ответы к серии задач на различные сюжеты.

 

1. .

2. .

3.

4. делителей.

5. 24.

6. .

7. 211.

8. .

9. Ответ: n + 1.

10. .

11. .

12. Ни одного способа.

13. .

14. .

15. .

 

Материалы для семинаров

(Задача 6 – это ознакомительный материал!)

 

ОТВЕТЫ ДЛЯ САМОКОНТРОЛЯ

 

В задаче номер 4 решение аналогично решению для систем счисления (вспомните тему «Целые числа»!), а в задаче номер 3 надо воспользоваться правилом произведения, а в некоторых случаях – и правилом перехода к дополнению.

 

 

Графы (ДОПОЛНИТЕЛЬНЫЙ МАТЕРИАЛ)

 

Определение

 

Граф — это совокупность непустого множества вершин и множества пар его вершин.

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



 

Граф называют ориентированным, если отмечено направление всех дуг (от одной вершины к другой).

 

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

 

Пример.

Квадрат с диагоналями является планарным графом (проверьте!). А пятиугольник с диагоналями не является планарным графом.

 

Деревья *

 

Дерево или древовидный граф – это связный граф без циклов.

Такое название дано потому, что любой древовидный граф можно нарисовать так, что он будет похож на дерево-растение. На таком изображении видны «корень» и «ветви». Листьями в дереве называются вершины, соединённые с графом только одной дугой.

 

В деревьях число вершин всегда на единицу меньше числа дуг. В самом деле, если мы будем отстригать от дерева листья вместе с дугами, на которых они висят, то разность между числом вершин и числом дуг меняться не будет. В конце стрижки останется одинокая вершина. Следовательно, эта разность равна единице.

 

В ориентированном дереве, в котором дуги идут от корня к ветвям, выходящие дуги связывают родительскую вершину с дочерними, а входящие – с родительскими.

 

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

 

Применение древовидных графов.

 

1. Древовидная файловая система, или дерево директорий.

 

2. Дерево поиска, при котором все потомки с левой стороны всегда меньше родителя, а в правом не меньше.



 

3. Дерево для вычисления математических формул – например, префиксной и постфиксной формы записи.

 

Задачи по теме «Деревья»

1. Какое максимальное количество листьев может быть у дерева из n вершин? А минимальное?

2. Могут ли в дереве две вершины соединяться двумя различными путями?

3. Существует ли дерево, у которого одна вершина является и листом, и корнем?

4. Докажите, что в ориентированном дереве у каждой вершины не более одного родителя.

 

Связные графы

Определение

 

Если из каждой вершины можно попасть в каждую, то граф отношения называют связным.

 

Подмножество графа, в котором из каждой вершины можно попасть в каждую, называют компонентой связности.

 

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

 

Двудольные графы

Определение

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

Определение: неориентированный граф G = (W,E) называется двудольным, если множество его вершин можно разбить на две части , | U | > 0, | V | > 0, так, что ни одна вершина в U не соединена с вершинами в U и ни одна вершина в V не соединена с вершинами в V.

Пример: решётка, вершины которой раскрашены в 2 цвета в шахматном порядке.

Двудольный граф называется полным, если для каждой пары вершин существует ребро . Для | U | = i, | V | = j такой граф называется Ki,j

Упражнение 1. Приведите пример двудольного графа с 6 вершинами.

Упражнение 2. Докажите признаки двудольных графов:

1) Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины.

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

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

На рисунках вершины двудольного графа часто располагают на параллельных прямых.

С двудольными графами связана задача о назначениях. Пусть — множество претендентов на рабочие места, — множество рабочих мест. Необходимо каждого из претендентов обеспечить работой в соответствии с его профессиональной подготовкой.

Булевы функции

 

Определение. Функцию от одной или нескольких переменных, аргументы и значение которой могут принимать только значения 0 или 1, называют булевой функцией (в честь английского математика Джорджа Буля (1815 - 1864), одного из основателей математической логики).

 

Примеры.

 

Конъюнкция: = 1 тогда и только тогда, когда x и y оба равны 1.

Дизъюнкция: = 1 тогда и только тогда, когда x и y оба равны 1.

 

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

При этом значения наборов переменных располагают в лексикографическом порядке. Сначала набор из одних нулей, затем правый ноль заменяют 1, и так далее, до набора из одних единиц. Например:

 

x y

 

 

x y

 

Эквивалентность: (Значение выражения равно 1, если значения x и y совпадают)

x y

 

Симметрическая разность: (Значение выражения равно 1, если значения x и y не совпадают)

x y

 

Импликация: (Мнемоническое правило: из нуля следует что угодно – и ноль, и единица)

x y

 

Отрицание:

 

x

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.