Гамильтоновы и эйлеровы циклы min веса.

Найти гамильтонов цикл (путь) минимальной длины (з-ча коммивояжера)– методами ветвей и границ и штрафования вершин:

1.

	1	2	3	4	5	6	7	8	9	10
1	0	28	31	28	22	36	50	67	40	74
2	28	0	31	40	41	64	74	80	63	101
3	31	31	0	14	53	53	53	50	42	83
4	28	40	14	0	50	41	39	41	28	69
5	22	41	53	50	0	40	61	86	53	78
6	36	64	53	41	40	0	24	58	22	39
7	50	74	53	39	61	24	0	37	11	30
8	67	80	50	41	86	58	37	0	36	60
9	40	63	42	28	53	22	11	36	0	41
10	74	101	83	69	78	39	30	60	41	0

 

2.

а)                                                     б)

	1	2	3	4	5
1	∞	12	9	9	12
2	9	∞	8	19	15
3	6	8	∞	16	10
4	5	9	12	∞	16
5	15	7	13	23	∞

 

	1	2	3	4	5
1	∞	35	40	31	27
2	2	∞	17	30	25
3	19	15	∞	6	1
4	9	50	24	∞	6
5	22	8	7	10	∞

 

 

в)                                                    г)

	1	2	3	4	5	6	7
1	∞	3	93	13	33	9	57
2	4	∞	77	42	21	16	34
3	45	17	∞	36	16	28	25
4	39	90	80	∞	56	7	91
5	28	46	88	33	∞	25	57
6	3	88	18	46	92	∞	7
7	44	26	33	27	84	39	∞

 

	1	2	3	4	5	6
1	0	4	10	18	5	10
2	4	0	12	8	2	6
3	10	12	0	4	18	16
4	18	8	4	0	14	6
5	5	2	18	14	0	16
6	10	6	16	6	16	0

 

3. Доказать, что если (p²-3p+6)/2 ≤ q, то граф G(p, q) – гамильтонов.

 

4. Нарисовать граф р = 6

а) эйлеров, но не гамильтонов;

б) гамильтонов, но не эйлеров.

 

5. А и А₁ матр. смежности графов G и G₁ соответственно. Док.:

 G и G₁ изоморфны ↔ ∃Р (А₁=РАР⁺= РАР^-1). Описать матрицу Р.

 

6. Найти эйлеров цикл минимального веса (з-ча китайского почтальона) для графов:

 

 

 

 

Бинарные деревья. Числа Каталана. Код Хаффмана

1. Подсчитать число бинарных деревьев с n вершинами. Нарисовать все бинарные деревья с 5 вершинами.

2. Вычислить: C_i: 0≤i≤10

3. Дано12 чисел: Сколькими способами их можно перемножить, не меняя порядка.

4. В очереди – 20 человек – у автомата. Любой товар стоит 1р. В автомате изначально нет сдачи.

10 человек имеют 1р. 10 имеют 2р. Сколькими способами они могут выстроиться в очереди, чтобы каждый мог получить сдачу.

 

5. Код Хаффмана. Построить дерево Хаффмана, определить код Хаффмана, найти вес кода, декодировать слова:

1.

s	v
a	8	10010110001100
d	7	0011011001111001
e	12
k	1
z	4
s	6

 

 

2

s	v
c	7	10001001000011101
e	12
g	3
h	2
o	9
z	4
s	5
t	8
u	1

 

3

s	v	s	v
a	25	z	9
b	10	s	11
e	30	t	15
g	7	u	3
h	6	y	13
i	18
l	8
n	12
o	20

 

6. 4-х битный код. Вероятность появления “0” в заданном языке в 3 раза больше вероятности появления “1”.

Построить код Хаффмана. Найти среднее число битов в этом коде. Сравнить с минимальной средней длиной кода (т. Шеннона).

 

Остовные деревья

 

 

1) Теорема Кэли:

1. Определить последовательность для остовных деревьев:

А)

Б)

В)

 

2. По последовательности построить дерево:

А) (1,2,3,3,2,3)

Б) (1,2,2,2,5,4,5,6)

 

 

3. Нарисовать все остовные деревья k4.

4. Теорема Кирхгофа. Определить число остовных деревьев для графов из задания1 (Планарные графы).

5. Алгоритмы Крускала и Прима. Построить деревья min веса для графов из «задачи кит. почтальона».

 

Группы и их графы, подсчет классов изоморфных деревьев с n вершинами.

 

 1. Аксиомы группы :

 

Показать:

 – левый обратный элемент

 – левый обратный элемент  =>  – правый обратный элемент  , т.е.  => = е

 – единственный

т.е. левая ед. гр. – есть правая ед. гр.

 – единственно

5. Записать таблицу умножения для групп:

(Z₄;+) и (Z₅⁰;•)

 

6. Доказать:

(n-1) транспозиций: (1;2);(1;3)…(1;n)

n > 1 порождают S_n;

 – нормальная подгруппа. (j – индекс подгруппы);

S₃ имеет 6 внутренних автоморфизмов.

-группа, R – отношение: – эквивалентность.

=>  

 

7. Показать, что группа симметрий равностороннего треугольника (относительно композиции) изоморфна группе всех биекций

.

8. Показать, что в циклических группах порядков 5, 6 и 14 образующую можно выбирать 4, 2 и 6 способами соответственно.

Показать, что группы автоморфизмов этих групп циклические.

9. Показать, что группа Aut[Z,+] всех автоморфизмов аддитивной группы [Z,+] целых чисел имеет порядок 2.

10. Показать, что автоморфизмы группы [Z₈,+] образуют нециклическую группу порядка 4.

11. Описать все изоморфизмы между группами  и .

(Объяснение:  = {1,2,3,4}mod5 с умножением в качестве композиции)

12. Показать, что группа симметрий правильного тетраэдра изоморфна группе всех перестановок множества {1,2,3,4}.

13. Построить некоторый эпиморфизм аффинной группы всех линейных преобразований вида  вещественные) на группу .

14. Записать образующие D₄ : V, R – через подстановки.

15. Нарисовать графы гр.: D₃, D₄, D₂, D₁, D_∞.

16. Сколько существует остовных помеченных деревьев с 4, 5, 6 вершинами?

Сколько существует классов изоморфных деревьев?

Сколько элементов содержится в каждом классе?

17. Найти количество различных гамильтоновых циклов в помеченных K_n, K_nn, количество простых циклов.

18. Сколькими способами можно рассадить 10 человек за круглым столом.

 

Перечисления

1.Определить:

Количество раскрасок квадрата в 2 цвета при действии подгруппы (R)

Количество раскрасок для правильного 5, 6-угольников в 2 цвета.

Количество раскрасок в 2 цвета прямоугольника (не квадрат).

 

2. Сколькими способами можно раскрасить правильный 10-ти угольник в 10 цветов?

Сколько существует неэквивалентных раскрасок, при которых 4 вершины будут покрашены в цвет №1; 4 вершины в цвет №3 и 2 вершины в цвет №5?

 

3. Сколькими способами можно раскрасить в 20 цветов грани куба, вершины куба?

 

---

Дата добавления: 2021-07-19; просмотров: 110; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!