Граф

1. Граф. Весовая матрица графа. Длина пути между вершинами графа. Вычисление количества путей в направленном ациклическом графе.

2. Граф

Граф — это математическая структура,
состоящая из множества вершин (узлов) и
множества рёбер (связей между
вершинами).
Граф состоит из вершин, связанных линиями.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется
ребром.
Линия, выходящая из некоторой вершины и входящая
в неё же, называется петлей.
ребро
дуга
В
А
петля
С

3. Неориентированный граф

Неориентированный граф - граф, не имеющий
выделенного направления, вершины такого графа
соединены ребрами.
Юра
Маш
а
Кол
я
Ан
я
Вит
я

4. Ориентированный граф

Ориентированный граф - граф, вершины
которого соединены дугами.
Юра
Маш
а
Кол
я
Ан
я
Вит
я

5. Взвешенный граф

Это граф, рёбрам или дугам которого
поставлены в соответствие числовые величины
(они могут обозначать, например, расстояние между
городами или стоимость перевозки).
Вес графа равен сумме весов его рёбер.
4
B
C
2
3
2
A
1
E
D
A
B
C
D
Е
A B C D Е
3 1
4
2
3 4
2
1
2 2
Таблице (она называется весовой
матрицей) соответствует граф.

6.

7. Решение 1) 1-2-3=4+3=7 2) 1-5-3=3+4=7 3) 1-4-6-3=1+2+2=5 4) 1-4-5-3=1+1+4=6 Ответ: 5

8.

1.На рисунке изображена схема дорог, связывающих
торговые точки А, Б, В, Г, Д, Е, К. По каждой дороге можно
двигаться только в направлении, указанном стрелкой.
Сколько существует различных путей от точки А до точки К?
Решение
В-1
Г-1
Е-2
Б-3
Д-5
К-7
Ответ 7

9.

Количество путей
Сколько существует различных путей из А в Ж?
Д
Б
Г
А
Ж
В
Е
9

10.

11. Домашняя работа Прочитать п 1.3 Записать в тетрадь определение графа. Выполнить задание 7 стр.30 задание 15 стр.61 Работу

прислать на почту
tnbelokon2016@yandex.ru