Презентация, доклад на тему Домашнее задание по теме Введение в теорию графов

учитель»
П.-С. Лаплас (1749 - 1827)

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

Решение:
Степени вершин:
deg(ПБ) - 2
deg(ЛБ) - 4
deg(1) - 4
deg(2) - 3

deg(3) - 2
deg(4) - 3
deg(5) - 4
deg(6) - 2

В графе 2 нечетных вершины
⇒ Пройти по всем островам и закончить прогулку на исходном -
НЕЛЬЗЯ
Нужно построить мостик 2 - 4

и D (если оно есть)
2) Предполагая, что веса ребер обозначают расстояния между вершинами, определите длину пути ABDCEA
3) Укажите, какой из трех путей — ABDC, ADEC или AEBC — самый короткий, самый длинный

Решение:
1) BD = 3
2) ABDCEA = 2 + 3 + 9 + 8 + 6 = 28
3) ABDC = 2 + 3 + 9 = 14
ADEC = 7 + 1 + 8 = 16
AEBC = 6 + 4 + 1 = 11

Самый короткий путь

Самый длинный путь

F построены дороги, протяженность которых приведена в таблице. Отсутствие числа в ячейке таблицы означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

A)

Ответ: 14

A

дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Ответ: 23

А

1

А, Б, Г

А

Б, В

В, Г

В, Д, Е

Е

Д

И, Ж, Е, З

1

3

4

4

11

4

4

23

дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Ответ: 12

А, В

1

А, Г

А

А, Г

Б, Ж

В

Г, Ж

Д

И, Ж, Е, З

3

12

2

2

2

5

3

2

A, B, C, D, E, F, G, H, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город K?

Ответ: 15

А

1

А

А

А

A, C, D

В, C

C, F

F, D, E

E

3

15

2

5

G, H, F, I, J

1

1

1

4

1

номера:
1. прибавь 1
2. умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 55?

Ответ: 32

1

8

16

20

24

4

5

6

32

8

7

28

9

36

44

11

10

40

12

48

13

14

52

2

3

4

12

номера:
1. прибавь 1
2. умножь на 2
3. умножь на 3
Сколько есть программ, которые число 1 преобразуют в число 18?

Ответ: 96

2

1

3

2

4

6

3

6

9

18

10

18

12

6

7

4

12

8

16

9

5

15

10

8

14

номера:
1. прибавь 1
2. умножь на 2
3. возведи в квадрат
Сколько есть программ, которые число 2 преобразуют в число 38?

Ответ: 266

2

4

4

6

9

4

6

25

10

20

16

5

8

32

17

34

9

18

11

22

8

7

12

3

36

36

20

38

24

13

26

16

14

28

12

15

14

10

19

18

номера:
1. прибавь 1
2. увеличь каждый разряд числа на 1
Например, число 23 с помощью команды 2 превратится в 34, а 29 в 39.
Сколько есть программ, которые число 25 преобразуют в число 51?

Ответ: 33

25

48

39

47

49

49

40

51

41

37

36

37

38

38

39

26

27

28

39

29

41

30

42

31

43

32

44

33

45

34

34

46

35

36