Графы. Пути в графах

1. Графы. Пути в графах

2. Что такое граф?

Граф это множество точек или вершин и множество
линий или ребер, соединяющих между собой все или
часть этих точек. Граф является информационной
моделью некоторого объекта или системы объектов.

3.

ГРАФЫ
ориентированные
дуги
неориентированные
рёбра

4. В таблице представлено расстояние между населенными пунктами в километрах. Определить кратчайшее расстояние между пунктами A и E.

A
A
B
C
D
E
2
10
8
16
9
1
B
2
C
10
9
D
8
1
E
16
3
3
4
4
11
11

5. Проверим правильность построения

A
A
B
C
D
E
2
10
8
16
9
1
B
2
C
10
9
D
8
1
E
16
3
3
4
4
2
A
8
10
16
1
D
3
C
11
11
B
9
4
E
11

6.

2
A
1.ABCDE – 25 км
2.ABCE – 15 км
3.ABDCE – 10 км
4.ACBDE – 31 км
5.ACDE – 24 км
6.ACE – 14 км
7.ADCE – 15 км
8.ADE – 19 км
9.AE – 16 км
8
B
9
10
D
3
C
16
1
4
E
11

7.

На рисунке — схема дорог, связывающих города А, Б, В, Г,
Д, Е, Ж и К. По каждой дороге можно двигаться только в
одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

8.

На рисунке — схема дорог, связывающих города А,
Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном
стрелкой. Сколько существует различных путей из
города А в город К?

9.

На рисунке — схема дорог, связывающих города А, Б,
В, Г, Д, Е, К. По каждой дороге можно двигаться только
в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

10.

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

11.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д,
Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в
одном направлении, указанном стрелкой. Сколько существует
различных путей из города А в город Л?

12.

Между населёнными пунктами А, В, С, D, Е построены
дороги, протяжённость которых (в километрах) приведена в
таблице.
Определите длину кратчайшего пути между пунктами А и E.
Передвигаться можно только по дорогам, протяжённость
которых указана в таблице.
A
A
B
B
C
D
E
2
2
7
1
1
C
2
3
D
2
4
E
7
3
4

13.

Между населёнными пунктами А, В, С, D, Е построены дороги,
протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и F.
Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

14.

В таблице приведена стоимость перевозок между
пятью железнодорожными станциями, обозначенными буквами A, B, C,
D и E. Укажите схему, соответствующую таблице.