Термин «граф» впервые ввел в 1936 г. венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (рис. 1).
Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Только спустя столетие теория графов получила следующий импульс с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам. На современном этапе развития применение теории графов широко и разнообразно:
• в химии для описания структур химических элементов [1] и числа теоретически возможных изомеров углеводородов и других органических соединений [2];
• в информатике и программировании (граф — блок-схема алгоритма);
• в коммуникационных и транспортных системах для поиска кратчайшего пути на сети дорог [3]. В частности, для маршрутизации данных в Интернете. Алгоритмы нахождения кратчайшего пути применяются для нахождения путей между физическими объектами на таких картографических сервисах, как карты Google или OpenStreetMap;
• в дискретной математике [4]. Без методов теории графов невозможно обойтись при анализе и синтезе различных дискретных преобразователей: функциональных блоков компьютеров, комплексов программ и т.д.;
• в геоинформационных системах. Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги (инженерные сети, линии электропередачи и т. д.) — как ребра. Используя различные алгоритмы теории графов, можно найти, например, кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут [1];
• в логистике [4];
• при замене оборудования;
• при проектировании газопроводов и многое другое.
Согласно постановлению Правительства РФ от 22.06.2004 № 303 «О порядке эвакуации населения, материальных и культурных ценностей в безопасные районы», разработанному в соответствие Федеральным законом «О гражданской обороне», эвакуация населения в мирное время — это комплекс мероприятий по организованному вывозу (выводу) населения из зон чрезвычайной ситуации (ЧС) или вероятной ЧС природного и техногенного характера и его кратковременному размещению в заблаговременно подготовленных по условиям первоочередного жизнеобеспечения безопасных (вне зон действия поражающих факторов источника ЧС) районах [5].