Графы

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

Граф — это набор узлов (вершин) и связей между ними (ребер).

Сеть — граф, в котором вершины связаны между собой по принципу «многие ко многим».

Граф состоит из вершин, связанных линиями - рёбрами. Вершины графа изображаются кругами, овалами, точками, прямоугольниками и т. д.

Объекты – это вершины графа, а связи – его рёбра.

1

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

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

Ответ: №4

Задание ОГЭ №4

Ответ: №2

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

Задание ОГЭ №4

Задача 3. Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых приведена в таблице.
Определите кратчайший путь между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).

Отв: 7

Задание ОГЭ №4

А-В-C-D=8
A-C-D=9
A-C-E-D=8
A-E-D=9
А-В-C-Е-D=7

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
  
Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).

Ответ: 5.

Задание ОГЭ №4

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

Ответ: 7

Задание ОГЭ №9

2+1+3+1

РЕШЕНИЕ

Задача 6. Сколько существует различных путей из города А в город К, проходящих через город В?

Ответ: 10.

Посчитаем последовательно количество путей до каждого из городов:
А = 1
Б = А = 1
В = А + Б = 2
Г = В = 2 (А не учитываем)
Д = В = 2 (Б не учитываем)
Е = В + Д = 4
Ж = В + Г = 4
К = Д + Е + Ж = 2 + 4 + 4 = 10.

Задание ОГЭ №9

РЕШЕНИЕ

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

А = 1.
Б = А = 1.
В = А + Б = 2.
Г = А + В = 3.
Д = Б + В = 3.
И = В + Г = 5 (Е не учитываем)
Ж = Д = 3.
К = Ж + И + Д = 11.

Задание ОГЭ №9

Что такое граф? Из чего он состоит?
Какой граф называется неориентированным?
Что такое сеть? Какие характерные особенности имеет сеть?
Какой граф называется ориентированным?
Как по весовой матрице графа определить количество ребер (количество петель)?
Как можно обозначить отсутствие связей между вершинами при хранении весовой матрицы в памяти реального компьютера?

Домашнее задание:

1. Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых приведена в таблице.
  Определите кратчайший путь между пунктами A и Е (при условии, что передвигаться можно только по построенным дорогам).

2. Сколько существует различных путей из города А в город К, проходящих через город Д?

Ответ:10

Ответ: 9

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

А = 1.
Б = А = 1.
В = А = 1.
Г = А + Б + В = 3.
Д = Г = 3.
И = Г = 3 (Е не учитываем).
Ж = Д = 3.
К = И = 3 (Е не учитываем).
Л = Д + Ж + К = 3 + 3 + 3 = 9
 
Ответ: 9.