Презентация по теме "Пути в графах"

ПУТИ

В ГРАФАХ

9 класс

Цели и задачи урока

• Как преобразовать информацию, представленную в табличной форме в граф

• Как определить все пути в графе

• Определить кратчайший путь

Весом пути  называется сумма путей ребер, образующих этот путь.

Следует помнить , что веса ребер – это вовсе не длины отрезков на плоскости. Для них не обязательно соблюдать известное из математики неравенство треугольника. 

Взвешенные графы удобно записывать в виде таблицы, которую называют  весовой матрицей.

Весовая матрица  – это квадратная таблица, в которой отражены все сведения о графе и весах его ребер.

А

А

Б

Б

2

2

В

В

10

10

Г

Г

8

Д

9

9

Д

8

16

16

1

1

3

3

4

4

11

11

Части таблицы, разделенные диагональю – симметричны, то есть содержат одни и те же данные. Следовательно, можно рассматривать данные любой половины таблицы, разделенной диагональю.

А

А

Б

Б

В

2

В

2

Г

10

Г

10

8

9

Д

8

Д

9

1

1

16

16

3

3

4

4

11

11

Общее правило

заполнения матрицы таково:

Каждая клетка матрицы соответствует паре вершин, расположенных в соответствующей строке и соответствующем столбце. Если две вершины графа Х и Y соединены ребром, то в клетку матрицы на пересечении строки Х и столбца Y, заносится вес ребра ХY, иначе клетка остается пустой.

Весовая матрица для неориентированного взвешенного графа всегда симметрична главной диагонали.

Для ориентированных взвешенных графов это свойство чаще всего не выполняется.

Одна из важнейших задач, возникающих при анализе графов – это  поиск минимального пути  между двумя заданными вершинами, то есть имеет наименьший вес среди всех возможных путей между заданными вершинами.

НАПРИМЕР, для транспортных графов, в которых ребра соответствуют дорогам, в зависимости от смысла весов минимальный путь может означать как путь наименьшей длины, так и путь с наименьшей стоимостью проезда, или путь с наименьшим возможным временем проезда и т.п.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых

(в километрах) приведена в таблице:

A

A

B

B

C

1

1

C

D

D

E

2

E

2

2

2

7

7

3

3

4

4

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

A

.

1

D

.

.

2

B

C

.

2

7

4

3

E

.

ABE= 1+7= 8

ABDE= 1+2+4= 7

ABCE= 1+2+3= 6 Ответ: 6