Формальное изучение сетей началось в середине XVIII века, когда переживал пору расцвета восточнопрусский город Кёнигсберг, родина философа Иммануила Канта. Среди достопримечательностей Кёнигсберга были семь мостов через реку Прегель[124]
, соединявших противоположные берега с двумя островками посреди реки, а также сами эти островки между собой (см. илл. 4). Местные жители давно заметили, что невозможно пройти по всем семи мостам, не пройдя по одному из них хотя бы дважды[125]. Эта задача привлекла внимание великого математика Леонарда Эйлера, уроженца Швейцарии, и в 1735 году он разработал теорию графов, чтобы наглядным и научным способом доказать, почему такой маршрут невозможен. На упрощенном графе, или схеме (см. илл. 5), четыре “вершины” обозначают два берега реки и два острова, больший и меньший, а семь “ребер” обозначают соединяющие их мосты. Строго говоря, Эйлер продемонстрировал, что возможность существования пути, который пересекал бы каждое ребро всего один раз, зависит отВ XIX веке ученые стали применять этот принцип ко всему – от картографии до электрических цепей и до изомерии органических соединений[126]
. О том, что могут существовать еще и