Задание для зачёта по ДМ

3 курс ПО_ЭО_ОЗО вариант 1 Задание для зачёта по ДМ Теория: 1. Основные правила комбинаторики: правило суммы и правило произведения. 2. Основные понятия теории графов: граф, смежность, инцидентность, изоморфизм. Практика: 1. Из колоды, состоящей из 36 карт, произвольно выбрали 6 карт. В скольких случаях среди них может оказаться ровно три дамы? 2. Определить, в каком из графов существует эйлеровый цикл или эйлерова цепь, перечислить порядок прохождения рёбер.	3 курс ПО_ЭО_ОЗО вариант 2 Задание для зачёта по ДМ Теория: 1. Основные комбинаторные конфигурации (кортеж, размещение, перестановка, сочетание): определения, формулы. 2. Формула Эйлера для степеней вершин, лемма о рукопожатиях. Практика: 1. Сколькими способами можно разбить 16 человек на три команды так, чтобы в первой команде было 6 человек, а во второй и третьей – по 5 человек? 2. Доказать, что графы G1 и G2 изоморфны:
3 курс ПО_ЭО_ОЗО вариант 3 Задание для зачёта по ДМ Теория: 1. Перестановка с повторением: определение, формула, примеры. 2. Способы задания неориентированного графа: перечисление, список смежности, список рёбер. Практика: 1. Сколькими способами можно раскрасить квадрат из 9 равных частей в 4 цвета так, чтобы в первый цвет были окрашены 3 части, во второй - 2, в третий - 3, в четвёртый - одна? 2. Семеро школьников на каникулах договорились, что каждый пошлёт друзьям три открытки. Может ли оказаться так, что каждый получит открытки именно от тех, кому напишет сам?	3 курс ПО_ЭО_ОЗО вариант 4 Задание для зачёта по ДМ Теория: 1. Сочетание с повторением: определение, формула, примеры. 2. Матрица смежности для неориентированного и ориентированного графа: определения, свойства, недостатки. Практика: 1. Сколько существует натуральных чисел, меньших 100, которые не делятся ни на 2, ни на 3, ни на 5? 2. Определить, в каком из графов существует эйлеровый цикл или эйлерова цепь, перечислить порядок прохождения рёбер.
3 курс ПО_ЭО_ОЗО вариант 5 Задание для зачёта по ДМ Теория: 1. Свойства сочетаний. Треугольник Паскаля. 2. Матрица инцидентности для ориентированного и ориентированного графа: определения, свойства. Практика: 1. Сколько четырёхзначных чисел можно составить из цифр 0,1,2,3,4,5, если: а) цифры могут повторяться; б) все цифры в записи числа разные; в) цифры могут повторяться, но число должно быть кратно 5. 2. В большом парке строится 11 аттракционов. Возможна ли такая планировка дорожек, при которой каждый аттракцион будет соединён дорожками ровно с пятью другими аттракционами?	3 курс ПО_ЭО_ОЗО вариант 6 Задание для зачёта по ДМ Теория: 1. Полиномиальная формула: формула, пример разложения. 2. Эйлерова цепь, критерий существования эйлеровой цепи. Примеры. Практика: 1. Для проведения диктанта из 5 преподавателей кафедры русского языка создана комиссия из двух человек. Сколько можно составить различных комиссий? 2. Нарисовать граф G, заданный с помощью матрицы смежности:   A(G) =
3 курс ПО_ЭО_ОЗО вариант 7 Задание для зачёта по ДМ Теория: 1. Бином Ньютона: формула, пример разложения. 2. Планарные графы. Критерий планарности. Решение задачи о трех домах и трех колодцах. Практика: 1. Сколько чисел, больших 100 и меньших 10000, записываются только нечётными цифрами? 2. Определить, в каком из графов существует эйлеровый цикл (эйлерова цепь), перечислить порядок прохождения рёбер.	3 курс ПО_ЭО_ОЗО вариант 8 Задание для зачёта по ДМ Теория: 1. Разбиение множества: определение, формула, примеры. 2. Гамильтоновый цикл. Достаточные условия существования гамильтонова цикла (условия Дирака и Оре). Задача коммивояжера. Практика: 1. Определить коэффициент k для выражения k* x13 x24 x32 в разложении (x1+ x2+ x3)9 2. Нарисовать граф G, заданный с помощью матрицы инцидентности B (G) =
3 курс ПО_ЭО_ОЗО вариант 9 Задание для зачёта по ДМ Теория: 1. Принцип включения-исключения: формула, примеры. 2. Правильная раскраска и хроматическое число графа, примеры. Задача о политической карте. Теорема о пяти красках. Проблема четырёх красок. Практика: 1. Определить коэффициент k для выражения k* x14 x2 x32 в разложении полиномиальной формулы (x1+ x2+ x3)7 2. Нарисовать граф G, заданный с помощью списка смежности: G =	3 курс ПО_ЭО_ОЗО вариант 10 Задание для зачёта по ДМ Теория: 1. Кортеж, размещение, перестановка, сочетание: определения, формулы. 3. Формула Эйлера для степеней вершин, лемма о рукопожатиях. Практика: 1. Сколько различных пятизначных чисел можно записать из цифр 0,2,4,5,7, не повторяя одну и ту же цифру в записи числа? 2. Нарисовать граф G, заданный с помощью матрицы смежности:   A(G) =
3 курс ПО_ЭО_ОЗО вариант 11 Задание для зачёта по ДМ Теория: 1. Принцип включения-исключения. 2. Плоские графы. Грань плоского графа. Формула Эйлера для плоского графа. Практика: 1. Для освещения зала может быть включена каждая из имеющихся 10 ламп. Сколько существует различных способов освещения зала? 2. Определить, в каком из графов существует эйлеровый цикл (эйлерова цепь), перечислить порядок прохождения рёбер.	3 курс ПО_ЭО_ОЗО вариант 12 Задание для зачёта по ДМ Теория: 1. Основные правила комбинаторики: правило суммы и правило произведения. 2. Способы задания ориентированного графа: перечисление, список смежности, список дуг. Практика: 1. Дано множество А={1,2,3,4,5}. Перечислить все сочетания из трёх элементов? 2. На вечере присутствуют девять человек. Может ли оказаться так, что каждый из них знаком только с тремя участниками вечера?
3 курс ПО_ЭО_ОЗО вариант 13 Задание для зачёта по ДМ Теория: 1. Свойства сочетаний. Треугольник Паскаля. 2. Матрица смежности для неориентированного и ориентированного графа: определение, свойства. Практика: 1. В классе изучают 12 учебных предметов. Какое количество разных расписаний на вторник можно составить, если известно, что во вторник должно быть не меньше 4 и не больше 6 уроков, причём разных? 2. Проверить, являются ли изоморфными графы G1 и G2	3 курс ПО_ЭО_ОЗО вариант 14 Задание для зачёта по ДМ Теория: 1. Перестановка с повторением: определение, формула, примеры. 2. Матрица инцидентности для неориентированного и ориентированного графа: определения, свойства. Практика: 1. Определить коэффициент k при x5 и x7 в разложении выражения (x3 + x – 2)7 2. Определить, в каком из графов существует эйлеровый цикл (эйлерова цепь), перечислить порядок прохождения рёбер.
3 курс ПО_ЭО_ОЗО вариант 15 Задание для зачёта по ДМ Теория: 1. Полиномиальная формула: формула, пример разложения. 2. Понятие пути и цикла в графе. Эйлеровый цикл, критерий существования эйлерового цикла. Решение задачи о семи мостах. Практика: 1. Сколько существует натуральных чисел, меньших 100, которые не делятся ни на 3, ни на 7? 2. Задать граф G с помощью матрицы смежности, матрицы инцидентности, списком смежности и списком дуг.	3 курс ПО_ЭО_ОЗО вариант 16 Задание для зачёта по ДМ Теория: 1. Сочетание с повторением: определение, формула, примеры. 2. Эйлерова цепь, критерий существования эйлеровой цепи. Пример. Практика: 1. Записать разложение выражения, используя формулу бинома и треугольник Паскаля: (2x + y)5 2. Задать граф G с помощью матрицы смежности, матрицы инцидентности, списком смежности и списком рёбер.
3 курс ПО_ЭО_ОЗО вариант 17 Задание для зачёта по ДМ Теория: 1. Бином Ньютона: формула, пример разложения. 2. Гамильтоновый цикл, достаточные условия существования гамильтонова цикла (условия Дирака и Оре). Задача коммивояжера. Практика: 1. Имеется 10 одинаковых кружков: 3 белых, 3 чёрных, 4 красных. Сколько различных узоров можно составить, располагая кружки в один ряд? 2. Проверить, являются ли изоморфными графы G1 и G2	3 курс ПО_ЭО_ОЗО вариант 18 Задание для зачёта по ДМ Теория: 1. Разбиение множества: определение, формула 2. Правильная раскраска и хроматическое число графа, примеры. Задача о политической карте. Теорема о пяти красках. Проблема четырёх красок. Практика: 1. Из группы, состоящей из 10 мужчин и 10 женщин, выбирают 10 человек. В скольких случаях мужчин окажется больше, чем женщин? 2. Определить, в каком из графов существует эйлеровый цикл (эйлерова цепь), перечислить порядок прохождения рёбер.