Тема 2. Элементы дискретной математики

Занятие 1

1. Повторение определений основных понятий темы.

2. Даны множества: X={1, 5}, Y={1, 2, 4}, Z={2, 5}.

Найти следующие множества и начертить координатные диаграммы, иллюстрирующие их построение:

а) , б)

Проверить выполнение свойств коммутативности (пример а) и дистрибутивности (пример б) операции прямого произведения.

на дом .

3. Решить задачи.

а) В городе проходит футбольное первенство, в котором участвуют 8 команд. Разыгрываются золотые, серебряные и бронзовые медали (медаль каждого вида может получить только одна команда). Сколько различных вариантов распределения медалей существует?

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

в) В полуфинале первенства России по шахматам участвуют 10 человек. В финал выходят 3 человека. Определить число различных исходов полуфинала шахматного турнира.

г) Цифровой замок состоит из трех дисков, каждый из которых содержит10 цифр, и четырех дисков, каждый из которых содержит 8 букв. Чему равно общее количество возможных комбинаций цифрового замка?

На дом

а) Группа состоит из 25 человек. Необходимо выбрать старосту, заместителя старосты и профорга. Сколькими способами может быть сделан этот выбор, если каждый член группы может занимать лишь один пост?

б) В магазине имеется 10 ящиков для размещения сумок покупателей. В магазин пришло 10 покупателей. Сколькими способами они могут разместить свои сумки?

в) Сколько существует способов распределения 4 билетов на дискотеку между 20 студентами группы, если каждому студент может получить не больше 1 билета? А сколько существует способов распределения, если 2 билета выделяются девушкам, а 2 – юношам (в группе 8 юношей и 12 девушек)?

г) На шахматной доске 64 клетки. Сколькими способами можно поставить на шахматную доску 8 ладей так, чтобы они не били друг друга?

 

4. Выписать все элементы отношений r =< X, R> и r^-1 и представить их в виде координатных диаграмм, если

а) X= {1, 3, 5}, R = {< x, y>: x £ y},

б) X={3, 6, 9, 15}, R ={< x, y>: y/x нечетно}

на дом .

Занятие 2

1. Повторение определений основных понятий темы.

2. Нарисовать графы отношений (см. п. 4 занятия 1).

а) X= {1, 3, 5}, R = {< x, y> : x £ y},

б) X={3, 6, 9, 15}, R ={< x, y>: y/x нечетно}

на дом .

3. Исследовать свойства отношений, приведенных в п. 2, (рефлексивность, симметричность, транзитивность, антисимметричность, иррефлексив­ность, асимметричность, сравнимость). Определить, являются ли эти отношения а) отношением эквивалентности; б) отношением строгого порядка; в) отношением нестрогого порядка; г) отношением линейного порядка.

4. Пусть X = Y = R (множество действительных чисел), а отображение j: X ® Y задается указанным ниже законом. Нарисовать график отображения и охарактеризовать отображение (всюду определенность, функциональность, отображение “на”, взаимная однозначность).

а) y = | x |, б) | y | = | x |

на дом а) x = y² ; б) y = tg x.

Занятие 3

1. Повторение определений основных понятий темы.

2.Для графа, представленного следующей матрицей инциденций, определить матрицу смежности и нарисовать диаграмму графа.

на дом

3. Для орграфа, представленного следующей матрицей смежности, определить матрицу инциденций и нарисовать диаграмму орграфа:

на дом

4. Нарисовать диаграмму орграфа G=< V, X> и определить, будет ли он связным, сильно связным или несвязным.

V={v₁, v₂, v_3, , v₄, v₅},

X= {< v₁, v₂>, < v₂, v₁>, < v₂, v₂>, < v₂, v₃>, < v₂, v₄>, < v₄, v₃>, < v₄, v₂>, < v₄, v₁> }

На дом

V={v₁, v₂, v_3, , v₄, v₅},

X= {< v₁, v₂>, < v₂, v₁>, < v₂, v₃>, < v₃, v₁>, < v₃, v₃>, < v₄, v₁>, < v₅, v₅> }

6. Пусть Т =< V, X> ‑ ориентированное дерево. Разрезом С дерева Т называется подмножество вершин Т таких, что

а) не существует двух вершин С на маршруте в Т;

б) ни одна вершина не может быть добавлена к С без нарушения пункта а).

Определить все разрезы следующего ориентированного дерева:

V={v₁, v₂, v_3, , v₄, v₅ , v₆}, X={< v₁, v₂>, < v₁, v₃>, < v₁, v₄>, < v₃, v₅>, < v₃, v₆> }

На дом

V={v₁, v₂, v_3, , v₄, v₅ , v₆}, X={< v₁, v₂>, < v₁, v₆>, < v₂, v₃>, < v₂, v₄>, < v₂, v₅> }

5. Если T ‑ ориентированное дерево, то уровень вершины определяют как максимальную длину маршрута от этой вершины до листа. Глубина вершины ‑ это длина пути от корня до этой вершины. Глубиной дерева T называют длину самого длинного маршрута в T. Высотой вершины называют глубину дерева T за вычетом глубины вершины. Высотой дерева T является высота корня.

Пусть T =< V, X>, V={v₁, v₂, ..., v₉},

X={< v₁, v₂>, < v₁, v₃>, < v₁, v₄>, < v₃, v₅>, < v₃, v₆>, < v₃, v₇>, < v₅, v₈>, < v₅, v₉> }

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

На дом

Нарисовать Т со значениями уровней и со значениями высот в качестве меток вершин. Определить высоту дерева Т.

⇐ Предыдущая1234Следующая ⇒

Поделиться: