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

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

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		0	56	48	39	3	40
	X2		56	0	50	4	10	49
	X3		48	50	0	42	19	16
	X4		39	4	42	0	23	33
	X5		3	10	19	23	0	26
	X6		40	49	16	33	26	0	Рис. 80

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

ЗАВДАННЯ З КОМБІНАТОРИКИ 5. У магазині «Світ чаю» є 45 різних чашок і 20 різних блюдечок.

21

Скількома способами можна купити чашку з блюдечком?

6.Скільки різних слів, навіть безглуздих, можна скласти з усіх букв слова «перешийок»?

7.Серед 21 дівчат, яких опитали, 11 люблять троянди, 6 – ромашки, 6 – троянди і тюльпани, 5 – троянди і ромашки, 3 – тюльпани й ромашки, а двом подобаються всі вказані квіти. Скільком дівчатам подобаються тюльпани, якщо 5 дівчат через алергію не терплять жодні квіти?

8.У парку одночасно 50 дітей каталися на атракціонах, з них не менше 20 на «Веселих гірках», не більше 14 – на каруселях, не менше 15 – на «Автодромі» і не більше 12 на батуті. Скількома способами можна розподілити кількість дітей на різних атракціонах?

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

.

22

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

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

Рис. 81 Рис. 82

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

23

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

5.У кіоску колекціонер побачив 12 різних марок та 25 різних значків. Скількома способами він може купити одну марку або значок?

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

7.Серед 17 учнів, які поїхали на озеро купатися, 11 взяли із собою яблука, 6 – персики, 5 – груші, 4 – яблука й персики, 3 – яблука й груші, 2

–персики й груші, а решта взяли бутерброди. Скільки учнів взяло бутербродів, якщо яблука, персики й груші взяв один учень?

8.Розумний Андрійко лічив машини, що проїжджали повз його подвір’я. Протягом часу спостережень він нарахував 24 машини, з них не менше 8 марки Mercedes, 5 чи 6 машин марки BMW, не більше 9 марки Opel. Скількома способами могли розподілитися машини за їх марками?

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

.

24

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

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

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

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

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

V = {v1,v2,v3,v4}, E= {{v1,v1}, {v1,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			58		28	18	2	50
X2		58			18	47	14	49
X3		28	18			24	35	51
X4		18	47		24		45	15
X5		2	14		35	45		6
										Рис. 83
X6		50	49		51	15	6
4.	Побудувати				каркасне		дерево найменшої			ваги для графа, що
								25

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

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

5.Скільки чотиризначних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5, якщо жодна цифра не повторюється?

6.Скількома способами можна розмістити 9 студентів для роботи на 9 комп’ютерах?

7.Серед 26 студентів, які сидять у читальному залі, 14 вивчають математику, 11 – інформатику, 5 – фізику, 4 – математику та фізику, 3 – інформатику та фізику, 2 – математику, інформатику та фізику. Скільки студентів вивчають математику та інформатику, якщо 6 із присутніх не вивчають жоден із вказаних предметів?

8.Фермер Федір засіяв 50 га зернових. Причому засіяна площа кожного з видів виражається цілим числом га. Відомо, що пшениці було засіяно не менше ніж 20 га, ячменю – не менше 10 га, жита – не більше 5 га, гречки – від 3-х до 7-и га, кукурудзи – не більше 7 га. Скількома способами могли розподілитися засіяні площі за видами зернових культур?

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

26

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

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}, {v4,v3}}.

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

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

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

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

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

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

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

( )

3. Знайти найкоротший маршрут від 2 до всіх інших вершин графа, що заданий на рисунку 84.

Рис. 84

Рис. 85

27

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

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

5.У магазині квітів було 7 різних червоних, 10 – білих та 5 – жовтих троянд. Скількома способами юнак може купити одну троянду?

6.Студенти у семестрi вивчають 14 предметів. Скількома способами можна скласти розклад занять на один день, якщо повинно бути 4 пари з різних предметів?

7.У спортивному таборі 100 людей, які займаються плаванням, легкою атлетикою і лижами. Із них 10 займаються і плаванням, і легкою атлетикою і лижами, 18 – плаванням і легкою атлетикою, 15 – плаванням і лижами, 21 – легкою атлетикою і лижами. Число спортсменів, які займаються плаванням рівне числу спортсменів, що займаються легкою атлетикою, і рівне числу спортсменів, які займаються лижами. Знайдіть це число.

8.У шкільній майстерні хлопчики трьох класів: 8-А, 8-Б і 8-В виготовили 20 шпаківень. Відомо, що учні 8-А класу виготовили не менше 8-и, 8-Б – від 4-х до 8-и, 8-В – не більше 7-и шпаківень. Скількома способами може розподілитися кількість шпаківень, виготовлених учнями названих класів?

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

.

28

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

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. Знайти найкоротший маршрут від X2 до X6 для графа, що заданий матрицею суміжності М.

М	X1	X2	X3	X4	X5	X6
X1		19	25	11	2	35
X2	19		26	58	21	43
X3	25	26		39	22	3
X4	11	58	39		38	45
X5	2	21	22	38		2
X6	35	43	3	45	2		Рис. 86

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

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

29

5.Скільки є різних двозначних чисел, у десятковому записі яких не зустрічається жодна з цифр 1, 3, 7?

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

7.Групі студентів «Інформатика» запропонували три спецкурси: з мультимедіа, штучному інтелекту та імітаційному моделюванню. 22 студенти записалися на спецкурс з мультимедіа, 18 – на спецкурс із штучного інтелекту, 10 – на спецкурс з імітаційного моделювання, 8 – на спецкурси з мультимедіа і штучного інтелекту, 15 – на спецкурси з мультимедіа і імітаційного моделювання, 7 – на спецкурси зі штучного інтелекту і імітаційного моделювання, 5 студентів записалися на всі три спецкурси. Скільки студентів у групі?

8.Літнього дня протягом однієї години у кафе «Морозиво» було продано 20 порцій морозива «Пломбір», «Вершкове», «Фруктове». Відомо, що пломбіру продали не менше 6-и порцій, вершкового – не більше 11-и, фруктового – не більше 8-и. Скількома способами може розподілитися кількість проданого кожного із сортів морозива?

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

.

30