Теория графов

На практике часто бывает полезно изобразить некоторую си­туацию в виде рисунков, составленных из точек (вершин), представ­ляющих основные ситуации, и линий (ребер), соединяющих опреде­ленные пары этих вершин и представляющих связи между ними. Таким способом удобно представлять структуру системы, в которой вершины – это блоки, а ребра – связи между блоками. Такие рисунки известны под общим названием графов. Графы встречаются в разных областях под разными названиями: «структуры» в гражданском строительстве, «сети» в электротехни­ке, «социограммы» в социологии и экономике, «молекулярные структуры» в химии и т.д. Удобны графы и при исследо­вании систем методом пространства состояний. В этом случае вер­шины – состояния системы, процесса, ребра – действия, которые могут изменить состояние. При решении оптимизационных задач вершинами могут быть предполагаемые решения, ребрами – прави­ла для их нахождения.

Начало теории графов как математической дисциплины было положено Эйлером в 1736 г., когда им была написана статья о Кенигсбергских мостах. Однако она была единственной в течение почти ста лет. Интерес к этой науке возродился около сере­дины XIX в связи с развитием естественных наук (исследования электрических сетей, моделей кристаллов и структур молекул), формальной логики. Кроме того, оказалось, что многие математические голово­ломки могут быть сформулированы в терминах теории графов.

Последние 35-40 лет ознаменовали новый период интенсив­ных разработок теории графов. Появились новые области прило­жения: системы телекоммуникаций, биология, психоло­гия и другие.

Основные определения