Глава 8. Графы

8.1. История теории графов

Графические представления - удобный способ иллюстрации различных понятий, отображения исследуемого процесса. Все более распространенным становится представление количественных показателей в виде гистограмм, круговых и столбцовых диаграмм, по наглядным характеристикам которых (высота, ширина, площадь, радиус и др.) можно судить о количественных соотношениях сравниваемых объектов, значительно упрощая их анализ.

Мощным и наиболее исследованным классом объектов, относящихся к графическим представлениям, являются так называемые графы. В теории графов используется геометрический подход к изучению объектов. Фактически граф - это модель некоторой реальной системы. Моделирование сегодня - быстро развивающийся, эффективный метод познания окружающего мира.

Основоположником теории графов считают Леонарда Эйлера. Ученый, родившийся в Швейцарии, работавший в Берлине и полжизни отдавший России, член Петербургской академии наук, виртуозный алгоритмист Л. Эйлер в 1736 г. опубликовал решение известной задачи о кенигсбергских мостах. Протоки реки Преголь в пределах города Кенигсберга образуют два острова, а участки суши соединяют 7 мостов (рис. 8.1). Издавна жителей города и многих математиков занимала задача: найти маршрут, по которому, выйдя из дома, можно вернуться назад, пройдя по всем мостам только один раз. Однако пешеходам не удавалось решить задачу практически, а математикам - теоретически.

Рис. 8.1. Иллюстрация задачи о кенигсбергских мостах

Рис. 8.2. Граф для задачи о кенигсбергских мостах

Эйлер доказал, что задача не имеет решений. Для этого он обозначил каждую часть суши точкой, а каждый мост - линией. Получился граф, представленный на рис. 8.2. Если вы внимательно рассмотрите граф и попытаетесь из любой точки A, B, C или D пройти по всем линиям только один раз и вернуться в исходную точку, то достаточно быстро убедитесь, что сделать это невозможно. Таким образом, моделирование графом дает быстрое наглядное решение задачи о невозможности нахождения указанного маршрута.

Л. Эйлер обобщил постановку задачи, изучил свойства графов и сделал ряд общих выводов, которые сегодня относятся к теории графов.

Существенный вклад в теорию графов внесли в первой половине XIX в. немецкие ученые Густав Кирхгоф и Гарольд Келли. Изучение Кирхгофом электрических цепей привело к разработке основных понятий и получению ряда теорем, касающихся деревьев в графах. Келли подошел к изучению деревьев, решая задачи исследования химических веществ с различными типами молекулярных соединений.

Дальнейшее развитие теории графов связывают с именем венгерского математика Денеша Кёнига. В 30-е гг. XX столетия его работы позволили рассматривать теорию графов как отдельную математическую дисциплину.

Однако широкое распространение теория графов получила лишь с 50-х гг. XX в. в связи со становлением кибернетики и развитием вычислительной техники, когда теория графов существенно обогатилась новыми материалами и подходами. Тогда же началось системное изучение графов с различных точек зрения (структурная, информационная и др.). В это время формулировались проблематика и методы теории графов.

Графы находят применение при проектировании вычислительных машин, в теории программирования, в изучении физических и технологических процессов, в решении задач сетевого планирования и управления, в проектировании организационных структур управления, в лингвистических и социологических исследованиях и т. д.