ІНДИВІДУАЛЬНІ ЗАВДАННЯ
.pdf
Варіант №16 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ
1. Неорієнтовний граф G=(V,E) заданий аналітичним способом. Необхідно:
-задати граф геометричним способом;
-визначити степінь вершин графа;
-виділити три пiдграфи;
-виділити маршрут, довжиною 5;
-виділити маршрут, що є ланцюгом;
-виділити цикл.
V={v1,v2,v3,v4}, E={{v1,v1}, {v1,v2}, {v1,v3}, {v1,v4}, {v2,v2}, {v2,v3}, {v2,v4}, {v3, v3}}.
2. Задано орієнтований граф матрицею суміжності R. Необхідно:
-задати граф геометричним способом;
-задати граф аналітичним способом;
-задати граф матрицею iнцедентностi;
-визначити пiвстепінь входу і виходу кожної вершини графа;
-визначити число всіх орієнтовних маршрутів довжини 1, 2, 3.
Матриця суміжності |
( |
) |
3. Знайти найкоротший маршрут від 2 до всіх інших вершин графа, що заданий на рисунку.
Рис. 87 |
Рис. 88 |
4. Побудувати каркасне дерево найменшої ваги для графа, що
31
зображений на рисунку 88.
ЗАВДАННЯ З КОМБІНАТОРИКИ
5.Студенту потрібно написати курсову роботу з вищої математики. Скількома способами він може вибрати тему курсової, якщо на стенді висять 20 тем з дискретної математики, 15 тем з геометрії та 30 з математичного аналізу?
6.Скількома способами можна вибрати із повної колоди карт, яка містить 52 карти, по одній карті кожної масті?
7.На курсі вчиться 100 студентів. Із них 30 займається боротьбою самбо, 50 – карате, 40 – дзюдо, 15 – самбо та карате; 10 – самбо та дзюдо; 20 – карате та дзюдо. Скільки студентів не займається ніяким видом єдиноборств, якщо 7 студентів ходять на всі три секції?
8.На уроці математики учням 10-го класу запропонували на вибір розв’язати або тригонометричне рівняння, або тригонометричну нерівність, або систему тригонометричних рівнянь. Відомо, що рівняння вибрали не менше 16-и учнів, нерівність – не більше 8-и. систему – не більше 5-и. Скількома способами може розподілитися кількість вибраних виді завдань?
9.Знайти розв’язання рекурентного рівняння:
.
32
Варіант №17 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ
1. Неорієнтовний граф G=(V,E) заданий аналітичним способом. Необхідно:
-задати граф геометричним способом;
-визначити степінь вершин графа;
-виділити три пiдграфи;
-виділити маршрут, довжиною 5;
-виділити маршрут, що є ланцюгом;
-виділити цикл.
V ={v1,v2,v3,v4}, E={{v1,v2}, {v1,v3}, {v1,v4}, {v2,v2}, {v2,v4}, {v3,v2}, {v3,v3}, {v4, v3}}.
2. Задано орієнтований граф матрицею суміжності R. Необхідно:
-задати граф геометричним способом;
-задати граф аналітичним способом;
-задати граф матрицею iнцедентностi;
-визначити пiвстепінь входу і виходу кожної вершини графа;
-визначити число всіх орієнтовних маршрутів довжини 1, 2, 3.
Матриця суміжності |
( |
) |
3. Знайти найкоротший маршрут від X2 до X6 для графа, що заданий матрицею суміжності М.
М |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
|
|
|
|
|
|
|
|
X1 |
|
31 |
15 |
19 |
8 |
55 |
|
|
|
|
|
|
|
|
|
X2 |
31 |
|
22 |
31 |
7 |
35 |
|
|
|
|
|
|
|
|
|
X3 |
15 |
22 |
|
53 |
57 |
16 |
|
|
|
|
|
|
|
|
|
X4 |
19 |
31 |
53 |
|
39 |
9 |
|
|
|
|
|
|
|
|
|
X5 |
8 |
7 |
57 |
39 |
|
14 |
|
|
|
|
|
|
|
|
|
X6 |
55 |
35 |
16 |
9 |
14 |
|
Рис. 89 |
|
|
|
|
|
|
|
|
4. Побудувати каркасне дерево найменшої ваги для графа, що зображений на рисунку 89.
ЗАВДАННЯ З КОМБІНАТОРИКИ 5. У меню їдальні є 7 перших, 9 других і 10 третіх страв. Скількома
33
способами можна вибрати обід із трьох справ (перше, друге й третє)?
6.Скільки різних слів,навіть безглуздих, можна скласти з усіх букв слова «тарантас»?
7.На пікнік до лісу поїхало 16 учнів. Під час відпочинку 12 учнів грало на галявині у футбол, 9 – у шахи, 6 – грали у футбол та шахи, 4 – у футбол та бадмінтон, 3 – у шахи та бадмінтон, а 3 – у футбол, шахи та бадмінтон. Скільки учнів грало у бадмінтон, якщо один крім фотографування нічим іншим не займався?
8.20 студентів фізико-математичного факультету відвідують один із спецкурсів: або з математичного аналізу, або з алгебри, або з геометрії, або з інформатики. Скількома способами може розподілитися кількість студентів у різних групах. якщо відомо, що спецкурс з математичного аналізу відвідують не більше 6-и студентів, з алгебри – не більше 7-и, з геометрії – не менше 3-х, з інформатики – від 5-и до 9-и студентів.
9.Знайти розв’язання рекурентного рівняння:
.
34
Варіант №18 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ
1. Неорієнтовний граф G=(V,E) заданий аналітичним способом. Необхідно:
-задати граф геометричним способом;
-визначити степінь вершин графа;
-виділити три пiдграфи;
-виділити маршрут, довжиною 5;
-виділити маршрут, що є ланцюгом;
-виділити цикл.
V ={v1,v2,v3,v4}, E={{v1,v2}, {v2,v3}, {v2,v4}, {v3,v3}, {v4,v1}, {v4,v4}, {v3,v4}}.
2. Задано орієнтований граф матрицею суміжності R. Необхідно:
-задати граф геометричним способом;
-задати граф аналітичним способом;
-задати граф матрицею iнцедентностi;
-визначити пiвстепінь входу і виходу кожної вершини графа;
-визначити число всіх орієнтовних маршрутів довжини 1, 2, 3.
Матриця суміжності |
( |
) |
3. Знайти найкоротший маршрут від 2 до всіх інших вершин графа, що заданий на рисунку 90.
Рис. 90 |
Рис. 91 |
4. Побудувати каркасне дерево найменшої ваги для графа, що зображений на рисунку 91.
35
ЗАВДАННЯ З КОМБІНАТОРИКИ
5.У магазині є 15 різних дисків із піснями рок-виконавці, 45 різних дисків поп-виконавців та 10 – різних виконавців репу. Скільки існує способів купити один диск?
6.Скількома способами можна скласти букет із 7 квіток, якщо є 9 сортів квітів?
7.Серед 17 членів туристичної секції 13 приймали участь у поході по Карпатах, 6 – по горах Криму, 4 – на байдарках по Десні, 6 - по горах Карпат та Криму, 3 – по Карпатах та на байдарках по Десні, 2 – по горах Криму та на байдарках по Десні. Скільки членів туристичної секції приймали участь у всіх походах, якщо 3 початківців нікуди не ходили?
8.У магазині «Канцтовари» протягом дня було продано 90 зошитів на 12, 18, 24 і 36 аркушів. Відомо, що зошитів на 12 аркушів було продано не менше 20-и, на 18 – не менше 30-и, на 24 – від 10-и до 15-и, на 36 – не більше 12-и. Скількома способами може розподілитися кількість проданих зошитів кожного виду?
9.Знайти розв’язання рекурентного рівняння:
.
36
Варіант №19 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ
1. Неорієнтовний граф G=(V,E) заданий аналітичним способом. Необхідно:
-задати граф геометричним способом;
-визначити степінь вершин графа;
-виділити три пiдграфи;
-виділити маршрут, довжиною 5;
-виділити маршрут, що є ланцюгом;
-виділити цикл.
V ={v1,v2,v3,v4}, E= {{v1,v1}, {v1,v2}, {v2,v2}, {v2,v3}, {v2,v4}, {v3,v1}, {v3,v3}, {v3,v4}, {v4,v1}.
2. Задано орієнтований граф матрицею суміжності R. Необхідно:
-задати граф геометричним способом;
-задати граф аналітичним способом;
-задати граф матрицею iнцедентностi;
-визначити пiвстепінь входу і виходу кожної вершини графа;
-визначити число всіх орієнтовних маршрутів довжини 1, 2, 3.
Матриця суміжності |
( |
) |
3. Знайти найкоротший маршрут від X2 до X6 для графа, що заданий матрицею суміжності М.
|
М |
|
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
|
|
|
|
|
|
|
|
|
|
|
X1 |
|
|
41 |
27 |
54 |
46 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
X2 |
|
41 |
|
11 |
32 |
58 |
21 |
|
|
|
|
|
|
|
|
|
|
|
|
X3 |
|
27 |
11 |
|
33 |
22 |
33 |
|
|
|
|
|
|
|
|
|
|
|
|
X4 |
|
54 |
32 |
33 |
|
49 |
59 |
|
|
|
|
|
|
|
|
|
|
|
|
X5 |
|
46 |
58 |
22 |
49 |
|
47 |
|
|
|
|
|
|
|
|
|
|
Рис. 92 |
|
X6 |
|
5 |
21 |
33 |
5 |
4 |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
4. |
|
Побудувати каркасне дерево найменшої ваги для графа, що |
|||||||
зображений на рисунку 92. |
|
|
|
||||||
|
|
|
|
|
|
ЗАВДАННЯ З КОМБІНАТОРИКИ |
|||
5. |
У поштовому відділенні є 6 видів конвертів без марок, 5 видів |
||||||||
|
|
|
|
|
|
|
|
|
37 |
марок та 10 поздоровчих листівок. Скількома способами можна відправити листа з поздоровчою листівкою?
6.У кінотеатрі є десять крісел поставлених в ряд. Скількома способами може на них сісти дві особи?
7.На суботнику 14 студентів прибирали територію, 9 – садили дерева, 7 – ремонтували лавки, 7 – прибирали територію і садили дерева, 5 – прибирали територію й ремонтували лавки, 3 – садили дерева й ремонтували лавки, 2 – приймали участь у всих видах діяльності, а 1 – лише керував діями. Скільки студентів брали участь у суботнику?
8.Студентська профспілка організовує подорожі вихідного дня у міста України: Київ, Львів, Ужгород, Яремче. Відправитися у поїздку виявили бажання 105 студентів, з них не менше ніж 42 бажають відвідати Львів, не менше 10-и – Київ, не менше 30-и – Ужгород, не менше 15-и – Яремче. Скількома способами можна відправити студентів у подорож?
9.Знайти розв’язання рекурентного рівняння:
.
Варіант №20 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ
1. Неорієнтовний граф G=(V,E) заданий аналітичним способом. Необхідно:
-задати граф геометричним способом;
-визначити степінь вершин графа;
-виділити три пiдграфи;
-виділити маршрут, довжиною 5;
-виділити маршрут, що є ланцюгом;
-виділити цикл.
V ={v1,v2,v3,v4}, E= {{v1,v1}, {v1,v2}, {v2,v2}, {v2,v3}, {v2,v4}, {v3,v1}, {v3,v3}, {v3,v4}, {v4,v1}}.
2. Задано орієнтований граф матрицею суміжності R. Необхідно:
-задати граф геометричним способом;
-задати граф аналітичним способом;
-задати граф матрицею iнцедентностi;
-визначити пiвстепінь входу і виходу кожної вершини графа;
38
- визначити число всіх орієнтовних маршрутів довжини 1, 2, 3.
Матриця суміжності |
( |
) |
3. Знайти найкоротший маршрут від 3 до всіх інших вершин графа, що заданий на рисунку 93.
Рис. |
93 |
Рис. 94 |
4. Побудувати |
каркасне дерево |
найменшої ваги для графа, що |
зображений на рисунку 94.
ЗАВДАННЯ З КОМБІНАТОРИКИ
5.У магазині канцтоварів є 6 різних ручок із червоною пастою, 10 - із чорною пастою та 12 - із синьою пастою. Скількома способами можна купити одну ручку?
6.Скількома способами можна скласти розклад на один день, якщо потрібно включити 5 предметів?
7.Серед 35 учнів класу 20 відпочивало у таборі, 16 – на морі, 15 – у бабусі, 10 – у таборі та на морі, 8 – у таборі та бабусі, 9 – на морі та у бабусі, а 6 – у таборі, на морі та у бабусі. Скільки учнів ніде не відпочивало?
8.На клумбі розцвіли різнобарвні кущі троянд: червоні, білі, рожеві. Відомо, що кущів червоних троянд не менше 30-и, білих – не більше 15-и, рожевих – від 10-и до 25-и. Усього розцвіло 50 кущів троянд. Скількома способами може розподілитися кількість кущів троянд за кольорами?
9.Знайти розв’язання рекурентного рівняння:
.
39