Similar presentations:
Графы. Пути в графах
1. Графы. Пути в графах
2. Что такое граф?
Граф это множество точек или вершин и множестволиний или ребер, соединяющих между собой все или
часть этих точек. Граф является информационной
моделью некоторого объекта или системы объектов.
3.
ГРАФЫориентированные
дуги
неориентированные
рёбра
4. В таблице представлено расстояние между населенными пунктами в километрах. Определить кратчайшее расстояние между пунктами A и E.
AA
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. Проверим правильность построения
AA
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.
2A
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. Укажите схему, соответствующую таблице.