Графы

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

Узлы графа – объекты или вершины, представленные в виде точек
Дуги или рёбра – это линии связи или пути между объектами.

Схема Метро

Созвездия и пути

Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:
Земля – Меркурий; Плутон – Венера;
Земля – Плутон;
Плутон – Меркурий; Меркурий – Венера;
Уран – Нептун;
Нептун – Сатурн;
Сатурн – Юпитер;
Юпитер – Марс;
Марс – Уран.
Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.

Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти?
По красной
По желтой
По зеленой

Сколько всего путей, может быть в данном зоопарке?

Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г;
Б с А, В, Д.
Сколько матчей уже сыграно?
Сколько матчей осталось сыграть?
А
Д
Г
Б
В

Граф может быть представлен
Графика
Список дуг
Таблица
(АВ; 8)
(ВС; 9)
(СD; 6)
А
В
5
С
4
3

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

На схеме нарисованы дороги между четырьмя населёнными пунктами A, B, C, D и указаны протяжённости данных дорог.
Создайте таблицу по данной схеме.
Определите кратчайшее расстояние между пунктами А и С (при условии, что передвигаться можно по указанным на схеме дорогам).
А
C
D
B
1
1
6
4
3