ІНДИВІДУАЛЬНІ ЗАВДАННЯ

Варіант №6 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ

1. Неорієнтовний граф G=(V,E) заданий аналітичним способом. Необхідно:

-задати граф геометричним способом;

-визначити степінь вершин графа;

-виділити три пiдграфи;

-виділити маршрут, довжиною 5;

-виділити маршрут, що є ланцюгом;

-виділити цикл.

V = {v1,v2,v3,v4,v5}, E= {{v1,v3}, {v1,v4}, {v1,v5}, {v2,v2}, {v2,v3}, {v2,v4}, {v3, v3}, {v3,v5}, {v4,v4}, {v5,v5}}.

2. Задано орієнтований граф матрицею суміжності R. Необхідно:

-задати граф геометричним способом;

-задати граф аналітичним способом;

-задати граф матрицею iнцедентностi;

-визначити пiвстепінь входу і виходу кожної вершини графа;

-визначити число всіх орієнтовних маршрутів довжини 1, 2, 3.

Матриця суміжності	(	)
3. Знайти найкоротший маршрут від		до для графа, що заданий

на рисунку 72.

Рис. 72	Рис. 73
4. Побудувати каркасне дерево найменшої	ваги для графа, що

зображений на рисунку 73.

ЗАВДАННЯ З КОМБІНАТОРИКИ 5. Для отримання заохочувальних балів студент вирішив написати

11

реферат. Скількома способами він може вибрати тему реферата, якщо викладач йому запропонував 21 тему з теорії множин, 15 тем з комбінаторики та 30 з теорії графів?

6.У поштовому відділенні продаються листівки 10 сортів. Скількома способами можна купити 12 листівок?

7.У класі 20 учнів. На іспитах з історії, математики та української мови 10 учнів не отримали жодної оцінки «12», 6 учнів отримали «12» з історії, 5 – з математики і 4 – з української мови; 2 – з історії і математики, 2 – з історії і української мови, 1 – з математики і української мови. Скільки учнів класу отримали оцінку «12» з усіх предметів, що складали?

8.На пісенному фестивалі виступило 20 фольклорних колективів з України, Білорусі, Росії й Словаччини. Відомо, що колективів з України було не менше 6, Білорусі – не менше 3, Росії – не більше 7, а Словаччини

–не більше 4. Скількома способами могли розподілитися колективи за країнами?

9.Знайти розв’язання рекурентного рівняння:

.

12

Варіант №7 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ

1. Неорієнтовний граф G=(V,E) заданий аналітичним способом. Необхідно:

-задати граф геометричним способом;

-визначити степінь вершин графа;

-виділити три пiдграфи;

-виділити маршрут, довжиною 5;

-виділити маршрут, що є ланцюгом;

-виділити цикл.

V = {v1,v2,v3,v4}, E= {{v1,v1}, {v1,v3}, {v1,v2}, {v2,v2}, {v2,v4}, {v3,v2}, {v3,v3}, {v3, v4}}.

2. Задано орієнтований граф матрицею суміжності R. Необхідно:

-задати граф геометричним способом;

-задати граф аналітичним способом;

-задати граф матрицею iнцедентностi;

-визначити пiвстепінь входу і виходу кожної вершини графа;

-визначити число всіх орієнтовних маршрутів довжини 1, 2, 3.

Матриця суміжності

(

)

3. Знайти найкоротший маршрут від X2 до X6 для графа, що заданий матрицею суміжності М.

М	X1	X2	X3	X4	X5	X6
X1		21	40	28	60	52
X2	21		11	39	22	56
X3	40	11		23	14	19
X4	28	39	23		20	54
X5	60	22	14	20		52
X6	52	56	19	54	52		Рис. 74

4. Побудувати каркасне дерево найменшої ваги для графа, що зображений на рисунку 74.

ЗАВДАННЯ З КОМБІНАТОРИКИ 5. На дошці написано 6 іменників, 5 дієслів та 3 прикметників. Для

13

речення потрібно вибрати по одному слову кожної частини мови. Скількома способами це можна зробити?

6.Скількома способами можна розмістити 10 фотографій на Дошці пошани?

7.У групі 20 студентів, серед них 11 полюбляють читати детективи, 8 – любовні романи, 5 – фантастику, 7 – детективи й любовні романи, 3 – детективи й фантастику, 4 любовні романи й фантастику. Скільки студентів читають романи всіх вказаних жанрів, якщо 7 студентів взагалі не читають художньої літератури?

8.Погодного суботнього ранку рибалка Семен спіймав 25 рибин: карасів, окунів і щук. Відомо, що в його улові було не менше 10 карасів, не менше 8 окунів і не більше 5 щук. Скількома способами міг розподілитися його улов за видами риб?

9.Знайти розв’язання рекурентного рівняння:

.

14

Варіант №8 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ

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. Знайти найкоротший маршрут від 1 до всіх інших вершин графа, що заданий на рисунку 75.

Рис.	75	Рис. 76
4. Побудувати	каркасне дерево найменшої	ваги для графа, що

зображений на рисунку 76.

ЗАВДАННЯ З КОМБІНАТОРИКИ

15

1.Студент вирішив випити стакан напою. Скількома способами він може здійснити це, якщо у кафетерії є 8 видів мінеральних вод, 13 видів лимонадів та 10 видів соків?

2.Скількома способами можна розвісити в один ряд 5 різних картин, якщо є 8 місць для їх кріплення?

3.На вечірку зібралося 10 прихильників футболу, 7 – боксу, 4 – хокею, 5 прихильників футболу й боксу, 4 – футболу й хокею, 3 – боксу й хокею, а троє полюбляють всі ці види спорту. Скільки людей було на вечірці, якщо п’ятеро взагалі не цікавиться спортом?

4.На випускний бал 26 випускниць прийшли в платтях різних кольорів: білих, червоних, жовтих і синіх. Відомо, що білі плаття одягнули не менше 6 випускниць, червоні – не менше 3, жовті – не менше 2 і не більше 7, сині – не більше 4. Скількома способами могли розподілитися плаття дівчат за кольорами?

5. Знайти розв’язання рекурентного рівняння:

.

16

Варіант №9 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ

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		4	39	22	10	47
X2	4		56	18	4	35
X3	39	56		17	57	18
X4	22	18	17		15	37
X5	10	4	57	15		32
X6	47	35	18	37	32		Рис. 77

4. Побудувати каркасне дерево найменшої ваги для графа, що зображений на рисунку 77.

ЗАВДАННЯ З КОМБІНАТОРИКИ 5. У першості України з футболу беруть участь 16 команд.

17

Скількома способами можуть бути розподілені золота, срібна і бронзова медалі?

6.Скільки варіантів різних екзаменаційних комісій, що складаються

з3 членів, можна скласти з 10 викладачів?

7.Серед 20 студентів групи 11 полюбляє слухати поп-співаків, 8 – рок-співаків, 5 – у стилі кантрі, 7 – попта рок-співаків, 3 – поп-співаків та у стилі кантрі, 4 – рок-співаків та у стилі кантрі. Скільки студентів слухають пісні вказаних напрямків, якщо 7 студентів полюбляють тільки реп-музику.

8.У ліцей «Мудра сова» було зараховано 87 вступників у три класи: фізико-математичного, природничого і гуманітарного профілів. Скількома способами могла розподілитись кількість учнів у названих класах, якщо відомо, що у фізико-математичний клас зарахували не менше 28 учнів і не більше 33, природничий – не менше 24 і не більше 27, гуманітарний не менше 30 і не більше 35 учнів?

9.Знайти розв’язання рекурентного рівняння:

.

18

Варіант №10 ІНДИВІДУАЛЬНІ ЗАВДАННЯ З ТЕОРІЇ ГРАФІВ

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. Знайти найкоротший маршрут від 1 до всіх інших вершин графа, що заданий на рисунку 78.

Рис. 78	Рис. 79
4. Побудувати каркасне дерево	найменшої ваги для графа, що

зображений на рисунку 79.

ЗАВДАННЯ З КОМБІНАТОРИКИ 5. У кіоску «Укрпошта» було 10 різних російськомовних, 4 -

19

україномовних та 3 - англомовних журнали. Скількома способами можна купити один журнал?

6.Скільки різних восьмирозрядних чисел можна скласти у двійковій системі числення?

7.Із 17 студентів групи 12 добираються на заняття автобусом, 9 – тролейбусом, 7 – трамваєм, 8 – автобусом і тролейбусом, 5 – тролейбусом

ітрамваєм, 4 – автобусом, тролейбусом та трамваєм. Скільки студентів їдуть на заняття автобусом та трамваєм, якщо 3 студенти на заняття добираються тільки пішки?

8.Спонсори дитячого садка придбали для дітей молодшої групи 30 нових іграшок, з них не менше 6 машинок, не менше 8 ляльок, не менше 4 конструкторів, і не більше 4 дитячих столових наборів. Скількома способами могли розподілитися іграшки за їх видами?

9.Знайти розв’язання рекурентного рівняння:

.

20