Презентация к уроку Решение задач с помощью теории Графов

Решение задач с помощью теории графов

Анализирование информации, представленной в виде схем
1=
1
1
1=
1
1
1
B=1+1=2
2=
2
2
1=
1
F=2+1+1=4
1
4
=4
4
D=2+4=6
=6
6
G=6+4+1=7
Ответ: 7
Задача 1
На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город G?

Решение:

Задача 2
1=
1
1
1
1
1=
1=
1
1
1
1
B=1+1=2
=2
2
2
Г=2+1+1=4
=4
4
4
Е=2+1=3
=3
3
Ж=4+1=5
=5
5
К=3+4+5=12
На рисунке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж и К. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном направлении,
ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город К?

Ответ: 12
Решение: