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

Глава 1

Основные определения теории графов

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

Довольно часто граф изображают в виде конечного множества вершин — точек на плоскости и множества ребер (иногда также называемых дугами) — линий, связывающих пары этих точек. При этом расположение точек не имеет значения, равно как и форма линий. Линии требуются тольо для того, чтобы продемонстрировать связи между вершинами, выделить их пары. Так выглядит наиболее наглядное для человека представление важного математического объекта, называемого графом. В отличие от глаза человека, компьютер плохо воспринимает наглядные образы, для описания графа требуются совершенно другие средства.

Чтобы получить модель в виде графа, достаточно некоторое множество объектов, его вершин V , дополнить множеством E — дуг, реализующих попарные связи между этими объектами.

Вершины i V могут быть однотипными, к примеру, пространственно распределенными объектами, связи между ними — коммуникациями, временны´ми или логическими отношениями между ними. Вершины графа могут соответствовать состояниям некоторого процесса, а связи[pic 1]

— управлениям, переводящим эти состояния в последующие. Примером могут служить позиции пасьянса или логической игры, в совокупности с возможными ходами.

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

1. Примеры использования графов в качестве моделей

Представим некоторые довольно часто встречающиеся объекты, которые наиболее удобнее представить в виде графов.

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

План улиц поселка или города также является графом транспортных путей. Вершинами такого графа служат, преимущественно, уличные перекрестки и тупики, дугами — части улиц, попарно соединяющие вершины. Дуги графа транспотных путей могут различаться. По некоторым путям транспорт может двигаться только в одном направлении, по другим — в

любом, что позволяет говорить об ориентированных и неориентированных дугах.

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

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

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

Любая электрическая схема также может рассматриваться как граф, веринами которого являются контакты составляющих ее элементов, а дугами — соединяющих их проводники.

1. Любой многогранник (куб, призму, пирамиду) можно рассматривать как граф, вершины которого являются вершинами многогранника, а дуги — его ребрами.
2. У вас есть родственники? В таком случае вы можете построить собственный генеалогический граф. Вершины этого графа соответствуют вам и людям, находящимся с вами в родстве, а дуги направлены от родителей (предков) к их детям (потомкам). В генеалогическом графе все ваши родственники займут свое достойное место.
3. Многочисленные примеры графов связаны с головоломками, играми и пасьянсами. Прежде всего, отметим граф игры, вершины которого — возможные игровые позиции, а дуги соответствуют выбору ее участников. Граф игры содержит особую, выделенную вершину — начальную позицию и некоторое количество конечных позиций, которыми игра завершается. Для каждой конечной позиции указываются выигрыши всех участников, например, 0 в случае ничейного исхода и  1 в случае победы одного из игроков.[pic 2]

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

1. Многие любители интеллектуального досуга нередко встречаются с графами, не зная, что имеют дело именно с ними.

Обходы графов являются примерами задач, содержание которых неявно связано с понятием графа. Рассмотрим примеры таких задач и возможные способы их интерпретации с использованием графов.