В математике существует целый раздел — теория графов, который изучает графы, их свойства и применение. Матюша пока изучил основные понятия и некоторые способы решения задач с помощью графов. И с радостью делится с вами полученными знаниями. Видеосюжет построен следующим образом: теория, а затем практические задания. Для их выполнения ребятам необходимо взять листок бумаги, ручку или карандаш, а ещё может пригодиться линейка.
Граф — это множество точек, которые могут соединяться линиями.
Линии указывают на связь между двумя точками.
Точки называются вершинами графа.
А линии, которые связывают вершины, называются рёбрами графа.
Знакомство с тремя видами графов будет происходить на примерах задач.
Неориентированный граф, в котором вершины соединены рёбрами без указания направлений.
Задача: между восемью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля — Юпитер; Земля — Меркурий; Меркурий — Марс; Марс — Венера; Уран — Сатурн; Юпитер — Нептун; Нептун — Марс.
Можно ли долететь на рейсовых ракетах с Земли до Урана?
Ориентированный граф, в котором вершины соединены рёбрами с указанием направлений.
Задача: На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города, А в город Ж?
Взвешенный граф, в котором вершины соединены рёбрами, которые имеют вес.
Задача: между населёнными пунктами А, B, C, D, E построены дороги. Протяжённость дорог (в километрах) приведена в таблице.
Нужно определить длину кратчайшего пути между пунктами, А и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Рассмотренные теоретические знания и решённые задачи помогут ребятам справится с задачами, которые предложены для самостоятельного выполнения. Задачи будут даны на все виды графов, рассмотренные в первой части видеосюжета.
Матюша уверен, что ребята справятся с решением без проблем.