Использование графов при решении задач

В математике существует целый раздел — теория графов, который изучает графы, их свойства и применение. Матюша пока изучил основные понятия и некоторые способы решения задач с помощью графов. И с радостью делится с вами полученными знаниями. Видеосюжет построен следующим образом: теория, а затем практические задания. Для их выполнения ребятам необходимо взять листок бумаги, ручку или карандаш, а ещё может пригодиться линейка.

Граф — это множество точек, которые могут соединяться линиями.

Линии указывают на связь между двумя точками.

Точки называются вершинами графа.

А линии, которые связывают вершины, называются рёбрами графа.

Знакомство с тремя видами графов будет происходить на примерах задач.

Неориентированный граф, в котором вершины соединены рёбрами без указания направлений.

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

Можно ли долететь на рейсовых ракетах с Земли до Урана?

Ориентированный граф, в котором вершины соединены рёбрами с указанием направлений.

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

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

Взвешенный граф, в котором вершины соединены рёбрами, которые имеют вес.

Задача: между населёнными пунктами А, B, C, D, E построены дороги. Протяжённость дорог (в километрах) приведена в таблице.

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

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

Матюша уверен, что ребята справятся с решением без проблем.