Начало: Математика для чайников. Глава 1. Что такое математическая абстракция. Предыдущая глава: Математика для чайников. Глава 14. Производная Важность теории графов трудно переоценить. Казалось бы, что такое граф? Просто набор стрелочек. Просто схема. Но вокруг этой незамысловатой схемы из стрелочек построена целая теория. И эта теория нашла очень широкое применение. Но почему? Давайте разберемся. Где можно применить такой объект, как граф? Первым делом напрашивается задача построения маршрута, как это делают навигаторы...

Не о тех, которые вельможи, а о тех, которые фигуры из вершин и рёбер. Наверное, самый часто встречаемый в быту граф – это карта движения общественного транспорта. Например, карта метро (рис 1). С ее помощью можно легко построить маршрут от одной вершины (станции) до другой. И чем больше кольцевых линий, дополнительных диаметров, пересадочных станций – тем больше вариантов маршрута можно найти. Очевидно, что, чтобы добраться от станции А до станции Б, нам нужно, чтобы они были связаны между собой ребрами (перегонами) – непосредственно или через другие вершины...