Дискретная математика - методичка

9.24.В скількох випадках при виборі з колоди в 52 карти десяти карт серед них опиняться усі 4 туза?

9.25.В одній купці – 12 карт, а в іншій – 10. Скількома способами можна три карти з однієї купки поміняти на 3 карти з іншої.

9.26.Скількома способами можна розкласти 20 однакових куль по чотирьом різним урнам?

9.27.Знайти кількість цілих додатних чисел не більш 100, які діляться

на 2; 3 та 5.

9.28.Маємо 38 предметів: з них 13 із сталі, 10 чорних, 14 сферичних; сталевих і чорних – 4; чорних і сферичних – 3; не мають жодної з вказаних властивостей 12 предметів. Скільки сферичних предметів, які до того ж є сталевими та чорними?

9.29.Скільки існує п’ятизначних чисел, в яких кожна наступна цифра більш за попередню?

9.30. Скільки непарних п’ятизначних чисел можна отримати з цифр

0;1;2;3;4;5;6;7;8;9;10, якщо цифри в цих числах різні?

Задача 10.

10.1. Який з циклів даного графа є ейлеревим? v1 v3

v2 v4

v6 v5

10.2. Побудувати матриці суміжності та інцидентності графа

v1		e1	v2
e3	e2		e4

	v3	v4
		e5

31

10.3. Побудувати матриці суміжності та інцидентності графа

1) 2) 3)

10.4. Завдана матриця суміжності. повідає?

1)	2)	v1

v1

v2

v3

v4

v3

Якому з наведених графів вона від-

3) v1	v2
v2

v4

v3

v4

	v1	v2	v3	v4
v1	0	1	1	0
v2	0	1	0	0
v3	1	1	0	1
v4	0	0	0	0

10.5. Побудувати матрицю суміжності та матрицю інцидентності гра-

фа.

e1	v2
v1	e2
	e3	v3
v4	e5	e6
	e4	v5

10.6. Який із зображених графів є повний?

1)

2)

3)

4)

10.7. Якому орієнтованому графу відповідає матриця суміжності

	v1	v2	v3	v4
v1	0	1	1	0
v2	1	0	1	0
v3	1	0	0	1
v4	1	0	1	1

32

1)	v2	v3	2)

v1 v4

10.8. Який із зображених графів повний?

V2		V1	V2
	V1	V2

V1

V3

V5

V5	V4	V4	V3	V5
10.9. Яка матриця інцидентності відповідає графу
V1	е1	V2

V3

V4

е4			е3			е2
V4						V3
			V5
1)				е1		е2		е3		е4			2)		е1		е2		е3		е4
		V1		1		0		0		1				V1	1		0		0		1
		V2		1		0		1		0				V2	1		1		1		0
		V3		0		0		0		0				V3	0		1		0		0
		V4		0		0		0		1				V4	0		0		1		1
		V5		0		0		0		0				V5	0		0		0		0
10.10. Побудувати орграф,													матриця суміжності якого є
				V1		V2		V3		V4
		V1		1		0		0		0			,
А(G)=		V2		0		0		1		0
		V3		1		0		0		0
		V4		0		0		1		0
а матриця				інцидентності є:
				e1		e2		e3		e4
		V1		-1	0			1	0
B(G)= V2				1	-1			0	0
		V3		0	1			-1	1
		V4		0	0			0	-1

33

10.11. Чи є даний граф зв'язним, сильно зв'язним?

V3

V1

V2

V4

10.12. Побудувати граф, матриця суміжності якого є

			V1	V2	V3	V4	V5
		V1	0	1	0	1	0	,
А(G)=		V2	1	0	1	1	0
		V3	0	1	0	1	0
		V4	1	1	1	0	1
		V5	0	0	0	1	0
матриця інцидентності B(G) є:
			e1	e2	e3	e4	e4	e6
		V1	1	0	0	0	1	0
B(G)=		V2	1	1	0	1	0	0
		V3	0	1	1	0	0	0
		V4	0	0	1	1	1	1
		V5	0	0	0	0	0	1

10.13. Побудувати матриці суміжності та інцидентності графа:

		V2	е2
	е1		V3
			е4
V1			е3
		е5 V4

10.14. Який з зображених графів є повний?

1)

2)

3)

34

10.15. Чи є граф G зв'язним, сильно зв'язним?

V2

V3

V1

V5

V4

10.16. Побудувати матриці суміжності та інцидентності графа:

V2

е1 е2

V1

е4

V3

е5 е3

V4

е6

V5

10.17. Вказати, які графи є ізоморфні?

1)

2)

3)

10.18. Завдана матриця інцидентності графа

		e1	e2	e3	e4	e5
	V1	1	1	0	1	0
B(G)= V2		1	0	0	0	1
	V3	0	1	1	0	0
	V4	0	0	1	1	1

Якому з наведених графів вона відповідає?

	1)				2)
V1	е2	V3		V1	е1
е1	е5
			е3	е2	е5
V2			V4	V3
	е4

		3)
V2	V1	е2	V3

е1

	е3	е4	е3
	V4
		V4	V2
	е4		е5

35

10.19. Чи є даний граф зв'язним, сильно зв'язним?

V1	V2
	V3

V5 V4

10.20. Завдана матриця інцидентності графа

		e1	e2	e3	e4	e5
	V1	1	1	0	0	0
B(G)= V2		1	1	1	0	0
	V3	0	0	1	1	1
	V4	0	0	0	1	1

якому з наведених графів вона відповідає?

	е3				V4
					V2
	V2			е2
				V1	е5
1) V1 е1			2)
	е2	V3		е3	е4

е1

е4 е5

V3

	V4
3)
е1
V1	V2
е2	е3
	е4
V3	V4

е5

10.21. Вказати, якщо є ізоморфні графи?

		V1		V1		V2		V1
V7			V2					V6
1)				2)		3)
							V4
								V3
			V3
V6				V5		V3
	V5	V4		V6	V4	V7	V2	V5
								V7

36

10.22. Чи є граф G зв'язним, сильно зв'язним?

V1V2

V4 V3

10.23. Вказати, які графи є ізоморфні.

2)	3)
1)

10.24. Якому орграфу відповідає матриця суміжності:

	V1	V2	V3	V4
V1	0	1	1	1
V2	1	0	1	0
V3	1	0	0	1
V4	1	0	0	0
V2	1)				2)	3) V2	V3
			V3	V2
						V3
V1			V4	V1		V4
						V1	V4

10.25. Побудувати матриці суміжності та інцидентності графа:

		V2
	е1		е4
V1		е2	V3
	е5		е3
V5	е6	V4

10.26. Який з наведених шляхів відповідає гамільтоновому циклу для завданого графа?

	е2		е6		1) е4, е5, е6
е1	е3		е7	е9	2)	е2, е6, е6 , е9, е7, е3, е1
					3)	е1, е2, е6 , е9, е8, е4
		е5
					4)	не існує гамільтонового циклу
	е4		е8

37

10.27. Побудувати матрицю суміжності А(G) та матрицю інцидентності В(G) графа.

V1	е1		V2	е5
е2	е3	е6	е4	V3
				е7
V4	е8		V5

10.28. Чи є даний граф зв'язним, сильно зв'язним?

	V4
V5	V3

V2 V1

10.29. Побудувати матриці суміжності та інцидентності графа

		е1	V2
V1			V3
			е4
		е3
			е2
	V4
		е5	V5

е6

10.30. Які з наведених дерев є ізоморфними?

1)

2)

3)

38

Задача 11. В задачі задано зважений граф G(V,E), де

V={v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11},

E={e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12,e13,e14,e15,e16,e17,e18,e19,e20}

					v2							e6						v5						е13							v9
				e1		е4						e7			е10								е14			е16						е19
	v1				e2				v3					v6							е11					v8									v11
				e3			е5										е12						е15					е17				е20
											е8
														е9										е18
					v4															v7									v10
			Вага ребра еі дорівнює mi і задана таблицею ( i =																									1,20		). Побудувати мі-
німальне остове дерево по алгоритму Краскала.
			11.1.
еі		e1		e2	е3		е4	e5		e6		e7	e8		e9		e10			e11			e12	e13		e14		e15		e16		e17		e18	e19	e20
mi		1		2	3		3	2		1		4	2		3		2			1			4	1		1		2	3			2		2	4	3
			11.2.
еі		e1		e2	е3		е4	e5		e6		e7	e8		e9		e10			e11			e12	e13		e14		e15		e16		e17		e18	e19	e20
mi		3		4	5		2	1		1		2	2		4		3			4			3	2		1		2	3			1		4	3	4
			11.3.
еі		e1		e2	е3		е4	e5		e6		e7	e8		e9		e10			e11			e12	e13		e14		e15		e16		e17		e18	e19	e20
mi		2		3	1		4	1		1		2	3		3		4			1			3	2		3		3	1			1		2	2	5
			11.4.
еі		e1		e2	е3		е4	e5		e6		e7	e8		e9		e10			e11			e12	e13		e14		e15		e16		e17		e18	e19	e20
mi		2		1	3		4	1		2		4	3		1		2			2			3	3		4		3	2			2		1	1	4
			11.5.
еі		e1		e2	е3		е4	e5		e6		e7	e8		e9		e10			e11			e12	e13		e14		e15		e16		e17		e18	e19	e20
mi		1		2	3		3	2		1		4	3		2		1			1			2	4		3		2	4			3		3	2	2
			11.6.
еі		e1		e2	е3		е4	e5		e6		e7	e8		e9		e10			e11			e12	e13		e14		e15		e16		e17		e18	e19	e20
mi		3		2	2		3	2		1		4	4		3		2			4			3	3		4		5	1			2		1	3	3
			11.7.
еі		e1		e2	е3		е4	e5		e6		e7	e8		e9		e10			e11			e12	e13		e14		e15		e16		e17		e18	e19	e20
mi		1		1	3		3	2		2		4	4		1		2			3			4	3		2		3	4			2		1	2	4

39

11.8.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	2	1	1	2	3	1	2	3	4	2	3	1	1	3	2	1	2	3	3	1

11.9.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	3	2	2	1	4	3	2	2	1	4	3	2	2	1	4	3	2	2	4	3

11.10.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	1	1	2	4	3	2	1	1	2	4	3	3	2	4	2	1	3	1	1	2

11.11.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	3	3	4	3	2	1	1	2	2	3	3	1	2	3	4	1	2	4	2	5

11.12.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	2	2	3	4	1	2	4	1	3	2	3	3	4	4	1	2	4	1	3	5

11.13.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	2	4	4	3	2	1	1	2	4	3	3	2	1	1	3	3	2	2	1	5

11.14.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	1	2	3	4	3	2	1	2	3	4	3	2	1	2	3	4	3	2	3	4

11.15.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	1	1	3	4	2	2	4	3	1	1	2	3	3	2	1	2	1	2	2	5

11.16.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	2	2	4	2	1	4	3	2	2	3	4	4	3	2	2	1	3	3	1	3

11.17.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	1	3	5	2	4	1	3	5	2	4	1	3	5	2	4	1	3	5	1	3

11.18.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	1	2	1	3	1	4	1	1	1	2	1	3	1	4	1	1	2	1	3	1

11.19.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	4	3	4	1	2	1	3	1	4	2	3	2	4	1	2	3	1	1	4	5

11.20.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	1	3	2	4	1	3	2	1	3	4	5	1	4	2	2	3	3	2	1	2

40