Методы теории графов
Содержание:
↑ Методы теории графов
Основоположником теории графов является швейцарский математик Л. Эйлер (1736). В дальнейшем теории графов уделялось малое внимание. Начало бурного развития и практического применения теории графов было положено венгерским математиком Д. Кенигом, который опубликовал в 1936 г. монографию «Теория конечных и бесконечных графов». Российский академик Л. В. Канторович разработал метод решения транспортных задач для их сетевой постановки. В настоящее время имеется большое количество работ по теории графов, включая прикладное направление.
Теория графов используется в исследованиях по экономической географии с целью глубокого познания внутренних взаимосвязей в пространственных структурах и закономерностей их развития.
Простые и лаконичные формы графов неразрывно связаны с глубинной сущностью отображаемых явлений и процессов, позволяют вскрыть неточности, допущенные в ходе теоретических построений. Их можно использовать в классификации объектов.
↑ Элементы теории графов
Фигура, состоящая из точек (вершин) и соединяющих их линий (ребер), называется графом (рис. 9.1). Вершины А ·—· В называются смежными (связанными). Граф называется связным, если любая пара его вершин связаны. Граф может состоять только из вершин (нуль-граф). Расположению вершин, длине и форме ребер или дуг не придается значения. Существенно лишь то, какие вершины соединены. Ребра (дуги) графов указывают на соответствие между вершинами в графе. Граф может быть представлен геометрически в виде определенной фигуры или в виде матрицы, в которой для каждой вершины записывается число связанных с ней ребер (дуг).
Нумерованные кружки (см. рис. 9.1) в графах служат его вершинами, которые соединены ребрами – неориентированными линиями (h, i). Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если число всех сходящихся в нем ребер нечетное.
Ориентированное ребро называют дугой (a,e, f, g, j – á), которая может быть входящей в вершину (1 – g) и выходящей из нее (1 – a, e, f). Ребра могут быть инцидентны вершине, если они являются одним из ее концов, а вершина – инцидентна каждому из входящих в нее ребер.
Каждое ребро (дуга) может соединять только две вершины. Если ребро соединяет вершину с ней же самой, то его называют петлей (b, c, d, k). Она имеет овальную форму (0). Это цикл (контур) единичной длины, т.е. образованный одним ребром (дугой), связывающим вершину саму с собой.
Вершины 3 и 5 изолированы, так как они не имеют ни одного инцидентного ей ребра (дуги). Ни одно ребро не соединяет такую вершину с другой. Вершину 3 можно назвать голой, желая подчеркнуть, что при ней нет даже петель, как в вершине 5. Рассмотренный граф содержит конечное множество вершин, но бесконечное множество (континуум) ребер (дуг).

Рис. 9.1. Элементы теории графов
Маршрут представлен в ориентированном графе путем, в неориентированном – цепью (∟), если каждое ребро графа, встречается в нем не более одного раза. Вершины и цепи могут повторяться несколько раз.
Цепь, начальная и конечная вершины которой совпадают, называется контуром (ориентированный граф) и циклом (⌂) (неориентированный граф). Они имеют форму треугольника, многоугольника.
Элементарные пути, цепи, циклы и контуры называют гамильтоновыми, простые – называются эйлеровыми. В элементарные формы графов вершины не включаются более одного раза, в простые – дуги (ребра) не включаются более одного раза. Длина цепи (пути) или цикла (контура) есть число ребер (дуг), которые их образуют.
Число ребер, сходящихся в вершине графа, называется степенью (порядком) s (G, x) вершины х в графе G = (X, U), или число ребер инцидентных этой вершине. При изоморфизме двух графов соответствующие друг другу вершины должны иметь одинаковую степень вершин. Упорядоченную систему степени его вершин называют вектором степеней графа G и кратко обозначают s (G).
Обыкновенным графом G = (X, U) называется упорядоченная пара множеств: конечного непустого Х, элементы которого называют вершинами графа G, и подмножества U