Дискретная_математика-Сборник_задач

те область определения и область значений.

а) x < y; б) х делится на у; в) х в 2 раза больше у; г) х на 2 больше у;

д) х у; е) х – делитель у; ж) х + у = 6.

1.32.Дайте графическое и матричное представление отношения (X, R), где

Х = {a, b, c, d, e, f}, R = {(a, a), (a, c), (a, f), (b, a), (b, e), (d, a), (d, d), (d, f), (f, b), (f, c), (f, e), (e, f)}.

1.33.Представьте в матричной форме следующие отношения, заданные графиче-

ски, запишите график этих отношений.

R

S

T

а

b

а

b

а

b

e

e

e

c

d

c

d

c

d

1.34.Для отношений R, S и T, представленных в упражнении 1.33, найти:

R

1

, R

2

, R R

1

, R

1

R, S

1

T

1

, S T, S

1

ˆ ˆ ˆ

T, R, S,T .

1.35.Отношения R и S заданы на множестве людей: R = {(x, y)| x – брат у},

S = {(x, y)| x – жена у}. Что означают отношения R S и S R ? 1.36.Какими свойствами обладают отношения (X, R) и (X, R 1), если:

а) X – множество геометрических фигур; R = {(x, y)| фигура х подобна у};

б) X – множество прямых на плоскости; R = {(x, y)| x||y};

в) X – то же, что и в б); R = {(x, y)| прямая х перпендикулярна у};

г) X – множество окружностей на плоскости; R = {(x, y)| окружность х концентрична окружности у};

д) X – то же, что и в г); R = {(x, y)| окружность х касается окружности у};

е) X = N; R = {(m, n)| m без остатка делится на n);

ж) X = Е; R = {(x, y)| x y};

з) X – то же, что и в ж); R = {(x, y)| x < y};

и) X = Z; R = {(x, y)| x – y делится без остатка на р, где р N}.

-11-

1.37.Какими свойствами обладают отношения (X, R) и (X, R 1), если

а) X = N\{1} – множество натуральных чисел, больших 1, а R = {(x, y)| x и y

имеют общий делитель, отличный от единицы};

б) X – множество точек плоскости, а R = {(x, y)| точки x и y принадлежат одной и той же окружности с центром в начале координат};

в) X – множество точек плоскости, а R = {(x, y)| точки x и y расположены симметрично относительно оси абсцисс}

г) X = N, а R = {(x, y)| x и y имеют один и тот же остаток от деления на 3}

д) X – множество сотрудников предприятия, а R = {(x, y)| x является начальником y}

е) X – множество букв русского алфавита, а R = {(x, y)| буква x предшествует в алфавите букве y}?

1.38.Какими свойствами обладает отношение (M, R), где M – множество подмно-

жеств некоторого множества S, а R = {(X, Y)| X M, Y M, X Y}? То же, если

R = {(X, Y)| X M, Y M, X Y}?

1.39.Какими свойствами обладают отношения (X, R) и (X, R 1), где Х – множество людей, если:

а) R = {(x, y)| х моложе у};

б) R = {(x, y)| х ребенок у};

в) R = {(x, y)| х состоит в браке с у};

г) R = {(x, y)| х живет в одном городе с у};

д) R = {(x, y)| х брат у};

е) R = {(x, y)| х похож на у}.

1.40.Найдите среди отношений, приведенных в упражнениях 1.34 – 1.37, отноше-

ния эквивалентности, частичного порядка, строгого частичного порядка.

-12-

2. ТЕОРИЯ ГРАФОВ

Для решения задач из этого раздела необходимо проработать материал, изло-

женный в [1] на стр. 35 – 53.

Пример 2.1. Выяснить, связен ли неограф G(X), заданный следующей матри-

цей смежности:

1	2	3	4	5	6	7	8	9	10
0	0 0 0			0	0	1	1	0	0	1
	1 1 0			0	0	0	0	0	0	2
		1 1		0	0	0	0	0		3
									0
			1	0	0	0	0	0	0	4
				0	1	0	0	0	1	5
M (G)
					1	0	0	0	1	6
						0	1	1	0	7
							0	1	0	8
								0	0	9
									0	10

Так как граф неориентированный, то изображена только верхняя часть матрицы смежности (нижняя часть симметрична относительно главной диагонали). Верши-

ны графа для краткости обозначены их номерами.

Если граф не связен, то найти все его связные компоненты.

Решение. Чтобы выяснить, является ли этот граф связным, воспользуемся мо-

дификацией алгоритма Мальгранжа ([1], стр. 42-43), предназначенного для выде-

ления всех максимальных сильно связных подграфов в орграфе. Так как в неогра-

фе множество достижимости вершины совпадает с множеством ее обратной дос-

тижимости, то, в отличие от алгоритма Мальгранжа, нам здесь достаточно найти лишь множество достижимости любой вершины. Если это множество включает все вершины графа, то он связен. Иначе – нужно взять любую вершину, не входящую в найденное множество достижимости, и найти множество достижимости для нее и т.д., пока не будут выделены все связные компоненты.

-13-

Найдем ˆ x1 – множество достижимости вершины x1. Для этого справа от мат-

рицы смежности изобразим столбец, в котором будем указывать расстояние от этой вершины до всех вершин графа, в которые можно попасть из x1 по какой-либо цепи. Около строк, соответствующих вершинам, не достижимым из x1, поставим крестик.

1	2	3	4	5	6	7	8	9	10
0	0 0 0			0	0	1	1	0	0	1
											0
	1 1 0			0	0	0	0	0	0	2
		1 1		0	0	0	0	0		3
									0
			1	0	0	0	0	0	0	4
				0	1	0	0	0	1	5		ˆ
M (G)					1	0	0	0		6		x1
									1
						0	1	1	0	7	1
							0	1	0	8	1
								0	0	9	2
									0	10

Так как ˆ x1 включает в себя не все вершины графа, то он не связен. Связная компонента, включающая в себя вершину x1, представляет собой подграф, опреде-

ляемый множеством вершин C(x1) = { x1, x7, x8, x9}.

Для нахождения остальных связных компонент исключим их матрицы M(G)

строки и столбцы, соответствующие вершинам из множества C(x1). Получим мат-

рицу смежности M(G1) подграфа, содержащего остальные связные компоненты графа G.

2	3	4	5	6	10
1	1	0	0	0	0	2
							0
	1	1	0	0	0	3	1
		1	0	0	0	4	2	ˆ
M (G1 )								x2
			0	1	1	5
				1	1	6
					0 10
			-14-

Найдем ˆ x2 – множество достижимости вершины x2 аналогично тому, как мы это делали с ˆ x1 . Нетрудно видеть, что связная компонента, включающая в себя вершину x2, представляет собой подграф, определяемый множеством вершин

C(x2) = {x2, x3, x4}. Исключим из матрицы M(G1) строки и столбцы, соответствую-

щие вершинам из C(x2). Получим матрицу смежности M(G2) подграфа, содержаще-

го остальные связные компоненты графа G:

5	6	10
0	1	1	5
				0
	1		6	1	ˆ
M (G2 )		1			x5
			10	1
		0

Так как из вершины x5 можно попасть во все оставшиеся вершины, то матри-

ца M(G2) определяет последнюю оставшуюся связную компоненту графа G.

Итак, граф G содержит три связных компоненты. Дайте их графическое пред-

ставление самостоятельно.

ЗАДАЧИ

2.1. Дайте аналитическое и матричное представление следующих графов:

а)

б)

x2

x3

в)

b

c

г)

b

c

х2

d

d

х1

х3

x1

х4

a

e

a

e

G1

G2

G3

G4

д) b

c

е)

ж)

х4

з)

х4

х2

d

х5

х3

х5

х3

х4

х1

х3

х

х

a

e

х2

1

x2

х1

G8

2

G5

G6

G7

2.2.Дайте графическое и матричное представление следующих графов:

а) G1 = (X1, Г1), где Х1 = {х1, х2, х3, х4, х5}, Х1/Г1 = {Г1х1 = {х3, х4, х5}; Г1х2 = ; Г1х3 = {х3}; Г1х4 = {х1, х5}; Г1х5 = {х2}};

б) G2 = (X2, Г2), где X2 = {x1, x3, x6}; X2/Г2 = {Г2x1 = {x6}; Г2x3 = X2;

Г2x6 = {x1, x3}};

-15-

в) G3 = (X3, Г3), где X3 = X2 (см. пункт б); X3/ Г3 = {Г3x1 = {x1, x3}; Г3x3 = ;

Г3x6 = {x3}};

г) G4 = (X4, Г4), где X4 = {x1, x2, x3, x4}, X4/Г4 = {Г4x1 = {x2, x3}; Г4x2 = {x1, x3}; Г4x3 = {x1, x2}; Г4x4 = };

д) G5 = (X5, Г5), где X5 = X4 (см. пункт г); X5/Г5 = {Г5x1 = {x3, x4}; Г5x2 = ;

Г5x3 = {x1, x4}; Г5x4 = {x1, x3}}.

2.3. Дайте аналитическое и графическое представление следующих графов, задан-

ных матрицами смежности:
а)							б)						в)
	0	0	1	1	0			0 1	0	0	1			0 1 1 1	0
	1	0	1	0	1			0 0	0	1	1			1 1 1 0	0
M (G ) 0		0	0	0	0	;	M (G ) 0 1		0	1	1	;	M (G ) 1 1 0 1		1
1							2						3
	1	0	1	1	0			0 1	0	0	0			0 0 0 1	0
	0	0	0	0	1			0 0	0	1	0			1 0 1 1	0

2.4.Какие из графов, представленных в упражнениях 2.1 – 2.3, являются ориентированными, неориентированными, смешанными?

2.5.Используя графы G6, G7 и G8 из упражнения 2.1, привести примеры элементарных, простых и составных путей, цепей, контуров и циклов. Указать их длины.

2.6.Выполните следующие операции над графами из упражнения 2.1:

а) G1 G2;G1 G2; б) G3 G4;G3 G4; в) G2 G6;G6 G2; г) G3 G4;G4 G3; д) G4 G5;G5 G4; е) G7 G8;G8 G7.

2.7. Выполните следующие операции над графами из упражнения 2.2:

а) 3	Gi ; 3		Gi ; б) 4		Gi ; 4		Gi ; в) G2 G3; G3 G2; г) G4 G5; G5 G4.
i 1		i 1		i 1		i 1

Дайте графическое представление полученных результатов.

2.8. Выполните следующие операции над графами из упражнения 2.3, полагая, что графы, над которыми выполняется операция, заданы на одном и том же множестве вершин:

а) G1 G2; G1 G2; б) 3	Gi ; 3	Gi ; в) G1 G2; G2 G1.
i	1 i	1

2.9.Найти транзитивное замыкание графов из упражнения 2.1.

2.10.Найти транзитивное замыкание графов, построенных в упражнениях 2.8, 2.9.

2.11.Приведите примеры частичных графов, используя в качестве исходных графы G6, G7 и G8 из упражнения 2.1.

-16-

2.12. Постройте подграфы графа G8 из упражнения 2.1, определяемые соответственно множествами {x1, x2, x5} и {x1, x2, x4, x5}. Приведите примеры частичных подграфов графа G8, определяемых теми же множествами.

2.13. связен ли следующие неографы, заданные своими матрицами смежности? Ес-

ли нет, то сколько в них связных компонент?
а)														б)
1		2	3	4	5	6	7	8	9	10 11 12				1	2	3	4	5	6	7	8	9	10	11 12
	0	1	0	1	1	0	1	1	1	0	1	1		1	0	0	0	0	0	0	0	1	1	1	0
		0 0 1 0				1	0	0	0	1	0	1			0 0 0 1				0	0	1	0	0	0	1
			0 0 1			1	1	1	0	1	0	0				0 1 0			1	1	0	0	0	0	0
				0 0		0	1	0	1	0	0	1					1 0		1	1	0	0	0	0	0
					0	1	1	0	0	1	1	1						0	0	0	1	0	0	0	1
						0	1	0	0	0	0	1							0	1	0	0	0	0	0
							0	1	1	0	0	0								1	0	0	0	0	0
								0	0	1	1	1									0	0	0	0	1
									0	1	1	0										0	1	1	0
										0	0	1											0	1	0
											0	1												0	0
												0													1

в)													г)
1	2	3	4	5	6	7	8	9	10 11 12				1		2	3	4	5	6	7	8	9	10	11 12
1	0	0	0	0	0	0	0	1	1	1	0			0	0	0	0	0	0	0	0	1	1	1	0
	0 1 0 1				0	0	1	0	0	0	1				0 1 0 1				0	0	1	0	0	0	0
		0 0 0			1	1	0	0	0	0	0					0 0 0			1	1	0	0	0	0	0
			1 0		1	1	0	0	0	0	0						0 0		1	1	0	0	0	0	0
				0	0	0	1	0	0	0	1							0	0	0	1	0	0	0	1
					0	1	0	0	0	0	0								0	1	0	0	0	0	0
						1	0	0	0	0	0									0	0	0	0	0	0
							0	0	0	0	0										0	0	0	0	1
								0	1	0	0											0	0	0	0
									0	1	0												0	1	0
										1	0													0	0
											1														0

-17-

2.14. Являются ли следующие графы связными? сильно связными? Если нет, то

разложите их на максимальные сильно связные подграфы.
а)												б)
1	2	3	4	5	6	7	8	9	10 11 12			1	2	3	4	5	6	7	8	9	10	11 12
0	1	1	0	0	0	0	1	1	1	0	0	0 0 0 0 0 0 1 0								0	0	0	0
1	1	0	0	1	0	0	0	0	0	1	0	1 1 0 0 0 0 0 1								0	0	1	0
1	1	0	0	1	1	1	1	0	1	0	0	0	0	1	1	0	0	0	0	1	1	0	0
0	0	0	0	0	0	1	0	0	0	0	1	0 0 0 1 1 0 0 0								0	0	0	0
0	0	1	0	0	0	1	0	0	0	0	0	0 0 0 1 0 0 0 0								0	0	0	1
0	1	1	1	0	0	0	0	1	1	0	0	0 0 0 0 0 1 0 1								0	0	0	0
1	0	0	0	0	0	1	0	0	0	1	1	0 0 0 0 0 0 0 0								0	0	1	0
1	0	0	0	0	0	0	1	0	1	0	1	0 0 0 0 0 0 0 0								0	0	0	1
0	1	0	0	0	0	0	0	1	1	1	0	0 0 1 0 0 0 0 0								0	0	0	0
1	0	0	1	0	1	1	1	0	0	0	0	0 0 1 0 0 0 0 0								0	0	0	0
0	0	0	0	0	0	0	0	0	0	1	0	1 0 0 1 1 0 0 0								1	0	0	0
1	1	0	0	0	0	1	0	1	0	1	1	0 0 1 1 0 0 0 0								1	0	1	0

в)												г)
1	2	3	4	5	6	7	8	9	10 11 12			1	2	3	4	5	6	7	8	9	10	11 12
0	1	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
1	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
0	1	0	1	1	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	1	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	0
1	0	0	0	0	0	1	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	1
0	0	0	0	1	0	0	1	0	1	0	0	0	0	1	1	0	0	1	0	0	0	0	0
0	0	0	0	0	0	1	0	0	1	0	0	0	1	0	0	0	0	0	0	0	0	1	0
0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	1
0	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	1	0	1	1	0	1	0	0	0	0	0	0	0	1	0
0	0	0	0	0	0	0	1	0	0	1	0	1	0	0	1	0	0	0	0	1	0	0	0
1	1	1	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	1	0	1	1	0

-18-

2.15. В следующих графах найти минимальный каркас:

	а) 1	2	3	4	5	6		б) 1	2	3	4	5	6
									8	8	3	11	10
		4	10	18	5	10
										4	7	12
			12	9	2	6
												9	7
				4	18	16						13	9
					14	6
													9
						6

в) 1

2	3	4
6		11

15 18

8

г) 1	2
	18

	5	6	7	8	9	10	11	12
	5
	8		11
				18	6
		10	7				17
		15	9
							3
				9	4	13	12
					14			5
						19
								5
								7
	3	4	5	6	7	8	9	10		11
							15	4		10
	8		12			11
		6		2	9
			18	13	4
				1		3
					8
						14
							5
								4		6
										3
						-19-

7

9

4

6

8

5

2.16.В графах из упражнения 2.15 найти кратчайшие цепи, соединяющие вершину х1 со всеми остальными вершинами.

2.17.В следующих графах найти длины кратчайших путей из вершины х1 во все остальные вершины. Построить кратчайший путь из вершины х1 в вершину с наибольшим номером:

а) 1 2 3 4 5 6 7 8 9 10							б) 1 2 3 4 5 6 7							8 9
1	10		6	3			7 8 9
10 10							6 4
					3				3		6
								7
1		4 4		1				5		5			16
2		2					3						8	14
3							2						4	8 10
											4		12 8
5 8							2
														1
2				6 8									2
3					5		10

2.18. В следующих графах найти длиннейший путь: а) из х0 в х11

		0	1	2	3	4	5	6	7	8	9	10	11
	3 4 11
						9 7
	7
		9				2 4
	2						3 3
									5
									8
	5
	8 5
		11
	4											5
													3
													2

-20-