[СГ ВМ] Типовой расчёт

Типовой расчет

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

1. , 2. ,

3. , 4. ,

5. , 6. ,

7. , 8. ,

9. , 10. ,

11. , 12. ,

13. , 14. ,

15. , 16. ,

17. , 18. ,

19. , 20. ,

21. , 22. ,

23. , 24. ,

25. , 26. ,

27. , 28. ,

29. , 30. .

2. Проверить, является ли отношение на множестве натуральных чисел а) функциональным, б) рефлексивным, в) антирефлексивным, г) симметричным, д) антисимметричным, е) транзитивным, ж) связанным.

1.  нечетное. 2. НОД.

3. . 4. .

5. . 6. .

7. . 8.  нечетное.

9. НОК. 10.  четное.

11. НОД. 12. НОК.

13. . 14. .

15. . 16.  четное.

17.  нечетное. 18. НОД

19. . 20. .

21. . 22. .

23. . 24.  нечетное.

25. НОК. 26.  четное.

27. НОД. 28. НОК.

29. . 30. .

3.

1. Доказать, что в произвольном графе порядка существует две вершины одинаковой степени.

2. Доказать, что связанный граф с вершинами имеет не меньше ребер.

3. Изоморфны ли графы:

4. Изоморфны ли графы:

5. Доказать, что дерево имеет один центр тогда и только тогда, когда диаметр – четное число.

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

7. Может ли в государстве, в котором из каждого города выходит ровно три дороги, быть ровно 1000 дорог?

8. Найти число остовных деревьев для графа, заданного матрицей смежности:

?

9. Из какого минимального числа кусков проволоки можно спаять каркас икосаэдра (толщина ребер должна быть одинаковой)?

10. Можно ли изготовить плату, состоящую из 12 деталей, соединенных 32 проводниками, чтобы все проводники располагались на одной стороне платы?

11. В теннисном турнире каждый игрок команды А встречается с каждым игроком команды В, Число игроков команды одинаково и не больше 9. Игроки команды А выиграли в 4 раза больше встреч чем игроки команды В, Сколько человек в каждой из команд?

12. Двадцать пять студентов одной группы, уезжая на каникулы, договорились послать SMS пяти студентам своей группы. Может ли оказаться так, что каждый получит SMS именно от тех, кому пошлет сам?

13. Существует ли граф с заданной степенной последовательностью 7 7 6 6 5 5 5 5?

14. Из какого минимального числа кусков проволоки можно спаять каркас додекаэдра (толщина ребер должна быть одинаковой)?

15. На клетчатом листе зарисовано 25 клеток. Может ли каждая иметь нечетное число соседей (соседними называем клетки, имеющие общую сторону)?

16. Есть 40 человек, некоторые из них знакомы. Доказать, что число человек, имеющих нечетное число знакомых, четно.

17. Феликс пошел с отцом в тир. Уговор был такой: Феликс делает 5 выстрелов и за каждое попадание получает право еще на 2 выстрела. Феликс выстрелил 25 раз. Сколько было попаданий?

18. Мэрия решила построить в каждом квартале города, имеющего 155 перекрестков и 260 отрезков улиц между перекрестками, приемный пункт вторсырья. Сколько запланировано приемных пунктов?

19. Доказать, что не существует выпуклого многогранника, у которого все грани шестиугольники.

20. Семь шестерен нужно разместить на минимальном количестве валов, но некоторые шестерни не могут находиться на одном валу. Такие пары шестерен указаны в таблице крестиками. Найти минимальное число валов, на которые можно поместить шестерни.

21. М ожет ли существовать шахматный турнир, в какой-то момент которого есть игроки, сыгравшие 7,5,3,2 партии, и нет игроков, сыгравших другое число партий?

22. Доказать, что в каждый момент соревнования, проводимого по круговой системе, найдутся хотя бы 2 игрока, проведшие одинаковое число встреч.

4. Граф G задан матрицей смежности.

1. Построить рисунок графа G.

2. Записать степенную последовательность графа G. Является ли граф G регулярным?

3. Является ли граф G связным? Чему равна его вершинная и реберная связность?

4. Осуществить поиск в ширину, начав с вершины 3.

5. Найти удаленности всех вершин.

6. Найти радиус и диаметр графа G; указать центры и периферийные центры.

7. Осуществить поиск в глубину, начав с вершины 2. Записать соответствующий обход и построить дерево путей.

8. Найти циклический ранг и ранг разрезов графа G.

9. Построить остов T графа G с максимально возможным числом концевых вершин.

10. Изобразить остов T как корневое дерево, выбрав в качестве корня центр T. Записать код полученного корневого дерева.

11. Построить фундаментальную систему циклов графа G, ассоциированную с остовом T. Какова мощность пространства циклов графа G?

12. Построить фундаментальную систему разрезов графа G, ассоциированную с остовом T.

13. Является ли граф G двудольным? Если является, то укажите доли.

14. Является ли граф G эйлеровым? Если является, то укажите эйлеров цикл. Если нет, то определите, содержит ли G эйлерову цепь (укажите ее).

15. Является ли граф G гамильтоновым? Если является, то укажите гамильтонов цикл. Если нет, то определите, содержит ли G гамильтонову цепь (укажите ее).

16. Является ли граф G планарным? Если является, то постройте изоморфный плоский граф. Сколько граней он содержит?

17. Найдите хроматическое и реберно-хроматическое число графа G. Приведите соответствующие раскраски.

18. Найдите наибольшее паросочетание графа G. Является ли оно совершенным?

1) 2)

3) 4)

5) 6)

7) 8)

9) 10)

11) 12)

13) 14)

15) 16)

17) 18)

19) 20)

21) 22)

23) 24)

25) 26)

27) 28)

29) 30)

5. Методом ветвей и границ решить задачу коммивояжера (алгоритм Литтла)с матрицей AN, где N - номер варианта:

	∞	27	26	23	25			∞	42	49	33	45
	29	∞	31	32	28			39	∞	38	38	41
A1=	22	34	∞	22	31	,	A2=	46	54	∞	42	38	,
	29	20	26	∞	23			58	53	45	∞	55
	28	43	32	26	∞			45	54	61	60	∞

	∞	34	33	25	28			∞	29	29	33	40
	28	∞	25	27	22			32	∞	30	40	37
A3=	37	28	∞	30	31	,	A4=	44	28	∞	32	26	,
	30	29	28	∞	34			47	38	44	∞	47
	39	38	41	40	∞			44	37	33	32	∞

	∞	52	46	52	43			∞	19	22	18	21
	48	∞	44	53	43			22	∞	22	22	21
A5=	53	59	∞	54	48	,	A6=	24	19	∞	24	27	,
	52	44	55	∞	42			23	27	23	∞	22
	54	57	57	51	∞			23	30	25	29	∞

	∞	57	38	38	50			∞	43	49	32	31
	55	∞	45	52	32			31	∞	41	52	42
A7=	35	43	∞	48	57	,	A8=	42	50	∞	28	51	,
	37	47	56	∞	37			32	39	30	∞	39
	46	35	61	61	∞			36	54	42	53	∞

	∞	32	32	36	38			∞	30	24	27	21
	45	∞	29	38	39			28	∞	26	20	29
A9=	34	31	∞	35	36	,	A10=	23	32	∞	25	38	,
	32	34	42	∞	28			24	22	24	∞	34
	37	48	41	34	∞			31	28	35	36	∞

	∞	14	23	24	16			∞	48	44	38	46
	22	∞	12	19	22			46	∞	51	43	30
A11=	16	24	∞	17	21	,	A12=	40	39	∞	45	34	,
	23	15	29	∞	15			56	50	53	∞	49
	21	23	23	19	∞			51	41	50	54	∞