Графы. Ориентированные и взвешенные графы

1.

Графы
Ж
Город
отправления
Д
З
Б
С
Город
прибытия
Дымчатый
Желтый
Дымчатый
Зеленый
Зеленый
Синий
Синий
Бронзовый
Синий
Дымчатый
Неориентированные графы – связь между двумя элементами не
имеет направления
Ориентированные графы – связь между двумя вершинами
действует только в одну сторону (отображается стрелкой)

2.

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

3.

Взвешенные графы
Ж
80
Д
115
З
160
40
Б
Город
отправления
55
С
Город
прибытия
Дымчатый
Желтый
Дымчатый
Зеленый
Зеленый
Синий
Синий
Бронзовый
Синий
Дымчатый
Взвешенный граф – это граф, в котором каждое ребро
обозначается числом. Это число — его вес (длина, стоимость)
Обычные графы (не взвешенные) возможно представить в виде
взвешенных, если считать, что все их рёбра обладают весом,
равным единице.

4.

Взвешенные графы
Задание 3.
Найти кратчайший путь из 0 в 4.
5

5.

Д/з
1. Знать:
- что такое граф, вершины, рёбра
- что такое степень вершины в графе
- что такое путь, цепь и цикл в графе
- какой граф называется связным
- чем отличаются неориентированные графы от ориентированных
- что такое взвешенный граф
2. Письменно в тетради привести по 3 примера ориентированных и
неориентированных графа
Д
Б
3. На рисунке – схема дорог,
связывающих города А, Б, В, Г, Д, Е,
Ж, И, К, Л. По каждой дороге можно
двигаться только в одном
направлении, указанном стрелкой.
Сколько существует различных
путей, ведущих из города А в город
Л?
Ж
В
А
Г
И
Е
Л
К