Итак, графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки. Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками. Точки называются вершинами графа, а линиями рёбрами. Ребро может иметь направление, которое указывается стрелочкой. У графа обязательно есть вершины. Граф без рёбер называется пустым. Направленная линия (со стрелкой) называется дуга. Линия ненаправленная (без стрелки) называется ребро. Линия, выходящая из некоторой вершины и входящая в неё же, называется петля...

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