36

Ответ. 97072 + 7843 = 104915, или 97073 + 7842 = 104915.

5.ГРАФЫ

№5.1. Доказать, что, если число ребер графа с n вершинами больше Сn2 , то он связный..

№5.2. Доказать, что не существует графа, степени всех вершин которого попарно различны..

№5.3. Найти все попарно неизоморфные графы с четырьмя вершинами и тремя ребрами.

№5.4. Установить какие из графов рис. 35 изоморфны.

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

G1

G2

●

●

●

●

●

●

● ● ● ● ●

● ●

● ●

●

●

●

●

●

G3

G4

Рис. 35. Разновидности графов

№ 5.5. Дополнением графа G называется граф G , который содержит те же вершины, что и граф G, и имеющий те и только те ребра, которые необходимо добавить графу G, чтобы он стал полным.

Приведите пример графа с 4-мя вершинами, изоморфного своему дополнению (самодополнительного). Доказать, что число вершин самодополнительного графа равно 4к или 4к + 1.

№ 5.6. По заданной матрице смежности (проверить!) построить граф или орграф. Составьте матрицу инцидентности.

37

	0111111			0110110
	1001110			10001101
	1010000				0110011
1)			2)
	1100101			0110101
	1110100			110100 0
	1100000			1010100
					0111000
	1001001

	00 11 0 1 1				0 11 0 11 0
					1 0 11 0 11
	01 1 0 0 0 0				1 0 0 1 0 11
3)		11 0 0 1 11		4)
	0 1 0 0 0 11				0 11 0 0 1 0
		0 0 1 1 0 11
					1 0 0 0 0 0 1
	1 1 1 0 0 10				1 1 11 0 0 0
	1 0 0 1 0 1 0				0 1 1 0 1 0 0

№5.7. В каждой строке матрицы смежности одинаковое нечетное число ненулевых элементов. Доказать, что число вершин графа четно.

№5.8. Найти кратчайший путь Хо-Х9 для взвешенного графа.

а)
	Х0	Х1		Х2		Х3		Х4		Х5		Х6		Х7		Х8			Х9
Х0		4	7		5
Х1	4		5				9		3
Х2	7	5							12		8
Х3	5										10
Х4		9							6				11
Х5		3	12				6
Х6			8		10										9		15
Х7							11										7
Х8											9						6
Х9											15		7		6
б)
						Х0		Х1		Х2		Х3		Х4		Х5			Х6			Х7		Х8		Х9
				Х0				41		71		51
				Х1		41				51				91		31
				Х2		71		51								121			81
				Х3		51													101
				Х4				91								61						111
				Х5				31		121				61												151
				Х6						81		101												91		75
				Х7										111												71
				Х8															91							61
				Х9												151			75			71		61
в)
						Х0		Х1		Х2		Х3		Х4		Х5			Х6			Х7		Х8		Х9
				Х0				24		27		25
				Х1		24				25				29		23
				Х2		27		25								122		28
				Х3		25										33		101
				Х4				29								26					112
				Х5				23		122		33		26												45
				Х6						28		101												29		152
				Х7										112												27
				Х8														29								26
				Х9												45		152			27			26

г)

											38
					Х0	Х1	Х2		Х3		Х4	Х5	Х6	Х7	Х8 9
			Х0			34	73		35
			Х1		34		35				39	33
			Х2		73	35						12	38
			Х3		35						20		10
			Х4			39			20			36		11
			Х5			33	12				36
			Х6				38		10						39	15
			Х7								11					37
			Х8										39			36
			Х9										15	37	36
д)					Х0	Х1	Х2		Х3		Х4	Х5	Х6	Х7	Х8	Х9
			Х0			44	74		54
			Х1		44		54				91	34
			Х2		7	5			22			42	84
			Х3		54		22						40
			Х4			94						64		41
			Х5			34	42				64
			Х6				84		40						94	45
			Х7								41					74
			Х8										94			64
			Х9										45	74	64
е)		25							Х0
	Х0 •		•			ж)			•
20	5		10				3		6	10	10
•		•					•		•		•	•
	5	10			15			2		5		1
			•
25		15	7 9		•		9	6 3 8 4 5 11
	•	•					•		•		•	•
	10	20	10	18				5		7	5	9
	•		•							•
		10	Х9							Х9

Рис. 36. Графы для задачи 5.8 № 5.9. Найти остовное дерево наименьшего веса для графа, заданного матрицей

	Х0	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Х8	Х9
Х0		1								7
Х1			5				8			5
Х2				4	3		7
Х3					8					4
Х4						3
Х5							6	5
Х6									9
Х7							12		11
Х8										5
Х9	7

№5.10. Выполнить поиск в глубину из различных стартовых вершин для графов предыдущей задачи..

№5.11. Для данного графа (рис. 37) выполнить поиск в ширину из вершины v5, а затем из вершины v8.

39

V13

V2

V14

V4

V6

V

V3

V8

V9 V5

V7 V11

V10

Рис.37. Орграф к задаче 5.11

5.12. Составьте все возможные планы маршрута путешествия по историческим местам, если автотуристам надо проехать из пункта М в пункт Н, осмотрев все памятники архитектуры не более одного раза. Как называется такой маршрут (рис.38)?

••

М•	•	•Н
	•
•		•
		•

Гис. 38. Расположение памятников архитектуры

№5.13. Пусть ориентированный граф G(V, Х) с множеством вершин V= {1, 2,3,4,5,6, 7} задан списком дуг Х. 1. Постройте реализацию графа G.

2. Постройте матрицу инцидентности графа G.

3. Постройте матрицу смежности G.

4. Задайте соответствующий неориентированный граф матрицей смежности.

5. Укажите степени вершин полученных графов.

V12

а) Х= {(1, 2), (2, 3), (4, 3), (4, 5), (6, 5), (7, 6), (7, 1), (7, 2), (6, 4), (4, 4), (2, 7), (6, 4), (5, 2)}; б) Х={(1, 4), (2, 1), (4, 3), (4, 5), (2, 6), (7, 1), (7, 6), (3, 2), (5, 4), (3, 4), (6, 2), (5, 5)}; в) Х= {(1, 5), (2, 3), (4, 5), (4, 6), (5, 6), (5, 1), (6, 6), (3, 2), (5, 4), (6, 4), (7, 2), (6, 7), (7, 5)}; г) Х = {(1, 1), (2, 2), (2, 3), (3, 5), (4, 6), (5, 1), (5, 6), (5, 2), (6, 4), (7, 4), (7, 2), (7, 5)};

д) Х = ((1, 1), (1, 3), (2, 5), (2, 6), (3, 6), (3, 1), (3, 6), (3, 7), (4, 4), (4, 6), (5, 2), (6, 3), (6, 5)}; е) Х= {(1, 3), (2, 2), (2, 3), (2, 5), (3, 5), (3, 6), (2, 7), (4, 1), (4, 6), (4, 2), (6, 4), (6, 3), (7, 2), (7, 6)).

№ 5.14. Составьте сценарий и по нему постройте сетевой граф, иллюстрирующий порядок выполнения операций, для того чтобы а) выпустить газету;

б) провести шахматный турнир на первенство вуза; в) подготовить и провести в вузе КВН; г) посадить и вырастить картофель; д) организовать работу торговой точки; е) изготовить табурет.

№5.15. Решите задачи «о переправах», изобразите решение графом.

1.Три генерала — Строгий, Лихой и Грозный — со своими адъютантами переправлялись через реку с помощью двухместной лодки. Адъютант может либо перевозить своего генерала, либо переправляться с другим адъютантом. Однако ни один из генералов не разрешил своему адъютанту ни оставаться с другим генералом вдвоем на берегу, ни переправляться с ним через реку. Как они переправились через реку?

2.Трое мужчин и три женщины должны переправиться через реку. У них была одна лодка, которая вмещала только двух человек. Грести умели все мужчины и только одна женщина. Кроме того, женщины требовали,