Графы дорожных сетей и алгоритмы работы с ними. Математическая модель

Пусть G(V,X) – псевдограф и пусть вершины v и w (v¹w) данного графа можно соединить маршрутом. Тогда обязательно существует и минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута d(v, w). Положим также d(v, v) =0 для любой вершины vÎV; d(v, w) = ¥, если не существует маршрута, соединяющего v и w.

Определенная таким образом величина d(v,w) для любых вершин v и w графа G(V, X) называется расстоянием между v и w.

Число расстояний в графе с n вершинами равно числу сочетаний C n 2 .

Пусть граф G(V,X) связный. Определим для него следующие понятия:

Диаметр графа : d(G) = maxd(v, w).

Эксцентриситет (максимальное удаление) вершины : r(v) = maxd(v, w);

Радиус графа: r(G) = min r(v);

Центр графа : любая вершина vÎV,такая, что r(v) = r(G).

Диаметр графа, эксцентриситеты вершин, радиус графа и центры графа называются метрическими характеристиками графа.

Пример. Найти метрические характеристики графа, заданного диаграммой:

Найдем все расстояния, учитывая, что d(v, w) = d(w, v).

Число расстояний в данном графе С 5 2 = 5!/3!2! = 10: d(v 1 , v 2) =1, d(v 1 , v 3) = 2, d(v 1 , v 4) = 2, d(v 1 , v 5) = 3, d(v 2 , v 3) = 1, d(v 2 , v 4) = 1, d(v 2 , v 5) = 2, d(v 3 , v 4) = 1, d(v 3 , v 5) = 2, d(v 4 , v 5) = 1.

Диаметр графа d(G) =3.

Эксцентриситеты вершин: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Радиус графа r(G) = 2.

Центры графа v 2 , v 3 , v 4 .

3. Минимальные маршруты в нагруженных графах

Граф G(V, X) называется нагруженным, если на множестве ребер графа задана функция, называемая весовой, которая ставит в соответствие каждому ребру х ÎХ графа некоторое число l(x). Значение l(x) называется длиной дуги.

Величине l(x) можно придать разный смысл: затраты на транспортировку, время проезда, расстояние между пунктами, расход бензина и т.д.

Сумма длин ребер, входящих в маршрут, называется длиной маршрута.

Заметим, что если для всех х Î Х l(x) = 1, то граф можно рассматривать как ненагруженный.

Маршрут в графе G(V, X) из вершины v в вершину w (v¹w), называется минимальным, если он имеет минимальную длину среди всех маршрутов в графе G(V, X) из вершины v в вершину w.

Ограничимся графами, для которых l(x)>0.

При поиске минимального маршрута в нагруженном графе с l(x)>0

воспользуемся таким же утверждением, что и для ненагруженного графа, а именно:

любой минимальный маршрут является простой цепью.

Рассмотрим теперь задачу поиска минимального маршрута в нагруженном графе.

Пусть граф G(V,X) нагруженный, число вершин n ³ 2, необходимо построить минимальный маршрут из v 1 в v n .

Приведем алгоритм.

Шаг 1. Каждой вершине присвоить индекс a(v i): a(v 1) = 0, a(v i) = ¥, i ¹ 1. окрасить вершину v 1 и положить v = v 1 .

Шаг 2. Для каждой неокрашенной вершины v j изменить индекс по правилу:

a(v j) = min {a(v j), a(v) + l(v, v j)}.

Окрасить ту из вершин, для которой a(v j) окажется наименьшим.. окрасить также ребро, ведущее в выбранную на данном шаге вершину v j . Положить v = v j .

Шаг 3. Если v = v j , закончить процедуру, так как кратчайший маршрут из v 1 в v n . если v ¹ v n , то перейти к шагу 2.

Замечание. Шаг 2 невозможен, если все a(v j)= ¥. В этом случае вершина v n недостижима.

Применим изложенный алгоритм к заданному диаграммой графу. Найдем в нем кратчайший маршрут из v 1 в v 6 .

Шаг 1. Окрасим вершину v 1 . Присвоим вершинам индексы: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Полагаем v 1 = v.

a(v 2) = min {¥, 0+4} = 4,

a(v 3) = min {¥, 0+7} = 7,

a(v 4) = min {¥, 0+3} = 3,

a(v 5) = min {¥, 0+¥} = ¥,

a(v 6) = min {¥, 0+¥} = ¥.

Окрашиваем вершину v 4 и ребро {v 1 , v 4 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 4 .

a(v 2) = min {4, 3+¥} = 4,

a(v 3) = min {7, 3+¥} = 7,

a(v 5) = min {¥, 3+3} = 6,

a(v 6) = min {¥, 3+¥} = ¥.

Окрашиваем вершину v 2 и ребро {v 1 , v 2 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 2 .

a(v 3) = min {7, 4+3} = 7,

a(v 5) = min {6, 4+2} = 6,

a(v 6) = min {¥, 4+¥} = ¥.

Окрашиваем вершину v 5 и ребро {v 4 , v 5 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 5 .

a(v 3) = min {7, 6+¥} = 7,

a(v 6) = min {¥, 6+2} = 8.

Окрашиваем вершину v 3 и ребро {v 1 , v 3 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 3 .

a(v 6) = min {8, 7+2} = 8.

Окрашиваем вершину v 6 и ребро {v 5 , v 6 }.

Так как вершина v 6 окрашена, то работу прекращаем. Получили минимальный маршрут v 1 v 4 v 5 v 6 , длина которого равна 8 .

Заметим, что это в данном случае не единственный для вершин v 1 и v 6 минимальный маршрут, т.к. в алгоритме имелась возможность окрасить вместо ребра {v 4 , v 5 } ребро {v 2 , v 5 }, тогда бы получили другой маршрут той же длины.

4. Задачи на деревьях

Ациклическим называется граф, в котором отсутствуют циклы.

Граф без циклов называется лесом.

Дерево – это связный ациклический граф.

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

Эксцентриситет вершины графа – расстояние до максимально удаленной от нее вершины. Для графа, для которого не определен вес его ребер, расстояние определяется в виде числа ребер.

Радиус графа – минимальный эксцентриситет вершин, а диаметр графа – максимальный эксцентриситет вершин.

Центр графа образуют вершины, у которых эксцентриситет равен радиусу. Центр графа может состоять из одной, нескольких или всех вершин графа.

Периферийные вершины имеют эксцентриситет, равный диаметру.

Простая цепь с длиной, равной диаметру графа, называется диаметральной .

Теорема 12.1. В связном графе диаметр не больше ранга его матрицы смежности.

Теорема 12.2. (Жордана) Каждое дерево имеет центр, состоящий из одной или двух смежных вершин.

Теорема 12.3. Если диаметр дерева четный, то дерево имеет единственный центр, и все диаметральные цепи проходят через него, если диаметр нечетный, то центров два и все диаметральные цепи содержат ребро, их соединяющее.

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

Пример 12.5. Найти радиус, диаметр и центр графа, изображенного на рис. 12.1.

Решение. В данной задаче удобно использовать матрицу расстояний S . Элемент этой квадратной симметричной матрицы равен расстоянию между вершиной i и вершиной j . Для графа, показанного на рис. 12.1, матрица расстояний имеет следующий вид:

. (12.2)

Вычислим эксцентриситет каждой вершины. Эту величину можно определить как максимальный элемент соответствующего столбца матрицы расстояний (или строки – поскольку матрица S симметрична). Получаем

№

Радиус графа r – минимальный эксцентриситет вершин. В данном случае r = 2. Такой эксцентриситет имеют вершины № 2, № 4 и № 5. Эти вершины образуют центр графа. Диаметр графа d – максимальный эксцентриситет вершин. В данном случае d = 3. Такой эксцентриситет имеют вершины № 1 и № 3, это периферия графа. В исследованном графе вершины оказались либо центральными, либо периферийными. В графах большего порядка существуют и другие вершины.

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

Теорема 12.4. Пусть – матрица смежности графа G без петель и , где . Тогда равно числу маршрутов длины k от вершины к вершине .

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

Пример 12.6. Найти матрицу расстояний графа, изображенного на рис. 12.1, алгебраическим методом.

Решение. Матрица смежности данного графа равна:

Будем заполнять матрицу расстояний, рассматривая степени матрицы смежности. Единицы матрицы смежности показывают пары вершин, расстояние между которыми равно единице (т.е. они соединены одним ребром).

Диагональные элементы матрицы расстояний – нули. Умножаем матрицу смежности на себя:

Согласно теореме между вершинами 2 и 3, 1 и 4 и т.д. имеется некоторое число маршрутов длиной 2 (поскольку степень матрицы равна двум). Число маршрутов здесь не используется, важен сам факт наличия маршрута и его длина, на что и указывает ненулевой элемент степени матрицы, не совпадающий с элементом, отмеченным при вычислении маршрута меньшей длины. Проставляем 2 в незаполненные элементы матрицы расстояний и получаем следующее приближение:

Осталось неизвестным расстояние между вершинами 1 и 3. Будем умножать матрицу смежности саму на себя до тех пор, пока в матрице не появится ненулевой элемент . Тогда соответствующий элемент матрицы расстояний равен степени матрицы смежности: . На следующем шаге получаем

В прошлом параграфе мы подчеркнули, что введенная там матрица смежности $A$, точнее матрица вершинной смежности графа, играет весьма существенную роль в теории графов. Мы отметили в качестве преимуществ этой матрицы — она квадратная порядка, равного числу строк матрицы инцидентности $B$, т.е., как правило, содержит меньшее число элементов. Во-вторых, эта матрица сохраняет всю информацию о ребрах графа и, при заданной нумерации вершин, однозначно описывает граф. Матрица смежности, как и матрица инцидентности графа, является (0,1)-матрицей, т.е. её элементы можно рассматривать как элементы других алгебраических структур, а не только как элементы множества целых чисел. В частности мы отметили, что элементы матрицы смежности могут рассматриваться как элементы булевой алгебры, подчиненные законам булевой арифметики, но не пояснили это должным образом. Прежде чем восполнить этот пробел, подчеркнем преимущества матрицы смежности, вытекающие из её квадратности.

Для этого напомним правила умножения матриц. Пусть даны произвольные матрицы с числовыми элементами: матрица $A$ размерности $n\times m$ с элементами $a_{ik}$ и матрица $B$ размерности $m\times q$ с элементами $b_{kj}$. Матрица $C$ размерности $n\times q$ называется произведением матрицы $A$ на $B$ (порядок важен), если её элементы $c_{ij}$ определяются следующим образом: $c_{ij} = \sum\limits_{k = 1}^m {a_{ik} b_{kj}}$. Произведение матриц записывается обычным образом $AB=C$. Как видим, произведение матриц требует согласованности размеров первого и второго сомножителей (число столбцов первой матрицы-сомножителя равно числу строк второй матрицы-сомножителя). Это требование отпадает, если рассматривать квадратные матрицы одного порядка и, следовательно, можно рассматривать произвольные степени квадратной матрицы. Это одно из преимуществ квадратных матриц перед прямоугольными. Другое преимущество состоит в том, что мы можем дать графовую интерпретацию элементам степеней матрицы смежности.

Пусть матрица смежности $A$ имеет вид: $A = \left({{\begin{array}{*c} {a_{11} } & {a_{12} } & {...} & {a_{1n} } \\ {a_{21} } & {a_{22} } & {...} & {a_{2n} } \\ {...} & {...} & {...} & {...} \\ {a_{n1} } & {a_{n2} } & {...} & {a_{nn} } \\ \end{array} }} \right)$, а её $k$-ая степень — $A^k = \left({{\begin{array}{*c} {a_{11}^{(k)} } & {a_{12}^{(k)} } & {...} & {a_{1n}^{(k)} } \\ {a_{21}^{(k)} } & {a_{22}^{(k)} } & {...} & {a_{2n}^{(k)} } \\ {...} & {...} & {...} & {...} \\ {a_{n1}^{(k)} } & {a_{n2}^{(k)} } & {...} & {a_{nn}^{(k)} } \\ \end{array} }} \right)$, где $k = 2,3,...$ Очевидно, что $A^k$, как и матрица $A$ будет симметричной матрицей.

Пусть $k=2$. Тогда $a_{ij}^{(2)} = \sum\limits_{k = 1}^n {a_{il} a_{lj}}$ ($i,j = 1,2,...,n$), и каждое слагаемое $a_{il} a_{lj}$ равно либо $0$, либо $1$. Случай, когда $a_{il} a_{lj} = 1$ означает, что в графе существуют два ребра: ребро $\{i,l\}$ (поскольку $a_{il} = 1)$ и ребро $\{l,j\}$ (поскольку $a_{lj} = 1$) и, следовательно, путь $\{{ \{i,l\}, \{l,j\} }\}$ из $i$-ой вершины в $j$-ую длиной два (путь из двух ребер). Здесь речь идет именно о пути, а не цепи, поскольку указано направление — из из $i$-ой вершины в $j$-ую. Таким образом, $a_{ij}^{(2)}$ дает нам количество всех путей на графе (в геометрической интерпретации графа) длины 2, ведущих из $i$-ой вершины в $j$-ую.

Если $k=3$, то $A^3 = A^2A = AA^2 = AAA$ и $a_{ij}^{(3)} = \sum\limits_{l_1 = 1}^n {a_{il_1 } } a_{l_1 j}^{(2)} = $ $\sum\limits_{l_1 = 1}^n {a_{il_1 } } \left({\sum\limits_{l_2 = 1}^n {a_{l_1 l_2 } a_{l_2 j} } } \right) =$ $\sum\limits_{l_1 = 1}^n {\sum\limits_{l_2 = 1}^n {a_{il_1 } } } a_{l_1 l_2 } a_{l_2 j} = \sum\limits_{l_1 ,l_2 = 1}^n {a_{il_1 } a_{l_1 l_2 } a_{l_2 j} }$.

Слагаемое $a_{il_1 } a_{l_1 l_2 } a_{l_2 j} $ в случае если оно равно 1, определяет путь длины 3 идущий из $i$-ой вершины в $j$-ую и проходящий через вершины $l_1$ и $l_2$. Тогда $a_{ij}^{(3)}$ дает нам количество путей длины 3, соединяющих $i$-ую и $j$-ую вершины. В общем случае $a_{ij}^{(k)}$ задает количество путей длины $k$, соединяющих $i$-ую и $j$-ую вершины. При этом $a_{ij}^{(k)} = \sum\limits_{l_1 ,l_2 ,...,l_{k - 1} = 1}^n {a_{il_1 } a_{l_1 l_2 } ...} a_{l_{k - 2} l_{k - 1} } a_{l_{k - 1} j}$.

Ясно, что величина $a_{ii}^{(k)} $ дает нам количество замкнутых путей длины $k$, начинающихся и оканчивающихся в вершине $i$. Так, путь длины 2 — $a_{il} a_{li}$, означает путь, проходящий по ребру $\{ i,l \}$ из вершины $i$ в вершину $l$ и обратно. Поэтому $a_{ii}^{(2)} = s_i$, т.е. диагональные элементы матрицы $A^2$ равны степеням соответствующих вершин.

Рассмотрим теперь наряду с матрицей $A$ матрицу $\dot {A}$, которая отличается от матрицы $A$ только тем, что у неё элементы (числа 0 или 1) рассматриваются как элементы булевой алгебры. Поэтому действия с такими матрицами будут проводиться по правилам булевой алгебры. Поскольку действия сложения и умножения матриц с булевыми элементами сводится к действиям сложения и умножения элементов этих матриц по правилам булевой арифметики, то, надеемся, что это не приведет к затруднениям. Матрицу с булевыми элементами будем называть булевой матрицей. Очевидно, что операции сложения и умножения булевых матриц замкнуты на множестве булевых матриц, т.е. результат этих операций будет снова булевой матрицей.

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

Результатом сложения двух булевых симметричных матриц одного порядка будет булева симметричная матрица того же порядка с нулями на тех местах, на которых у обоих слагаемых стоят нули и единицами на тех местах, на которых по крайней мере у одного слагаемого стоит единица. В графовой интерпретации эта операция называется операцией сложения графов . Суммой двух графов , заданных на одном и том же множестве вершин с одной и той же их нумерацией, называется граф, у которого вершины i и j несмежные, если они несмежные у обоих графов-слагаемых, и вершины i и j смежные, если они смежные хотя бы у одного графа-слагаемого .

Проинтерпретируем теперь вторую степень булевой матрицы смежности $\dot {A}^2$ с элементами $\dot {a}_{ij}^{(2)} = \sum\limits_{l = 1}^n {\dot {a}_{il} \dot {a}_{lj} }$. Ясно, что $\dot {a}_{ij}^{(2)} = 1$, если хотя бы одно слагаемое $\dot {a}_{il} \dot {a}_{lj} $ равно 1 и $\dot {a}_{ij}^{(2)} = 0$, если все слагаемые равны 0. Если матрица $\dot {A}$ является матрицей смежности некоторого графа, т.е. является симметричной (0,1)-матрицей с нулевой главной диагональю, то матрица $\dot {A}^2$, вообще говоря, не является матрицей смежности графа в принятом нами смысле, поскольку у неё все диагональные элементы равны 1 (если у графа нет изолированных вершин). Чтобы и на такие матрицы можно было смотреть как на матрицы смежности, мы должны при рассмотрении связей между вершинами некоторой связанной системы, определяющих эту систему как граф, допустить связь некоторых вершин самих с собой. «Ребро», определяющее связь некоторой вершины самой с собой называется петлей . Мы дальше, по-прежнему, под словом граф будем понимать граф без петель, а про граф с петлями, если это не будет ясно из контекста, так и будем говорить — граф с петлями.

Рассмотрим сумму $\dot {A}^{} = \dot {A} + \dot {A}^2$. Матрица $\dot {A}^{}$ задает нам граф, полученный из исходного «насыщением» его дополнительными связями, соответствующими путям длины 2. То есть в новом графе вершины $i$ и $j$ смежные, если они смежные в исходном графе или эти вершины связаны каким-нибудь путем длины 2, и вершины $i$ и $j$ несмежные, если они несмежные в исходном графе и не существует никакого пути длины 2, соединяющего эти вершины.

Аналогично определяется $\dot {A}^{} = \dot {A} + \dot {A}^2 + \dot {A}^3$. То есть в графе, заданном матрицей $\dot {A}^{}$ вершины $i$ и $j$ смежные, если они смежные в графе $\dot {A}^{}$ или эти вершины связаны каким-нибудь путем длины 3 в исходном графе, и вершины $i$ и $j$ несмежные, если они несмежные в графе $\dot {A}^{}$ и не существует никакого пути длины 3, связывающих эти вершины в исходном графе. И так далее.

В общем случае $\dot {A}^{[k]} = \sum\limits_{i = 1}^k {\dot {A}^i} $. Нетрудно видеть, что все $\dot {A}^{[k]}$ при $k \ge n - 1$, где $n$ — порядок матрицы $\dot {A}$, равны между собой. Действительно, если вершины $i$ и $j$ связны, то существует путь (цепь) связывающий эти вершины, а, следовательно, существует простой путь (простая цепь) связывающий эти вершины. Максимальная возможная простая цепь в $n$-вершинном графе имеет длину $n-1$ (простая цепь, связывающая все различные вершины графа). Поэтому, если в матрице $\dot {A}^{}$ на месте $(i,j)$ стоит 1, то на этом же месте в матрице $\dot {A}^{[k]}$ при $k \ge n - 1$ будет также стоять 1, поскольку матрица $\dot {A}^{}$ входит в качестве булева слагаемого в определение матрицы $\dot {A}^{[k]}$. Если же в матрице $\dot {A}^{}$ на месте $(i,j)$ стоит 0, то это значит, что в графе не существует никакой простой цепи, соединяющей $i$-ую и $j$-ую вершины, а, следовательно, не существует вообще никакой цепи связывающей эти вершины. Значит, в рассматриваемом случае и в матрице $\dot {A}^{[k]}$ при $k \ge n - 1$ на месте ($i$,$j)$ будет стоять 0. Что и доказывает наше утверждение о равенстве всех матриц $\dot {A}^{[k]}$ при $k \ge n - 1$ матрице $\dot {A}^{}$ и, следовательно, между собой.

Матрицу $\dot {A}^{}$ называют матрицей транзитивного замыкания матрицы $\dot {A}$, а также матрицей смежности транзитивного замыкания графа, заданного матрицей $\dot {A}$. Достаточно очевидно, что матрицей транзитивного замыкания связного графа будет матрица смежности полного графа, т.е. квадратная матрица, состоящая из одних единиц. Это наблюдение дает нам и метод определения связности графа: граф связный тогда и только тогда, когда матрица транзитивного замыкания его матрицы смежности будет состоять из одних единиц (будет матрицей полного графа) .

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

Покажем теперь, как процедура транзитивного замыкания позволяет построить так называемую «матрицу расстояний». Для этого определим расстояние между вершинами $i$ и $j$. Если вершины $i$ и $j$ связные, то расстоянием между ними назовем длину минимального (по числу обхода ребер) простого пути, связывающего эти вершины; если вершины $i$ и $j$ несвязные, то положим расстояние равным нулю (ноль как отрицание какого-либо пути связывающего эти вершины). При таком определении расстояния расстояние между вершиной и ею же самой равно 2 (длина пути по ребру и обратно). Если же при вершине имеется петля, то расстояние между вершиной и ею же самой равно 1.

Для построения матрицы расстояний для $n$-вершинного графа с матрицей смежности $A$, которая указывала бы расстояние между любыми двумя вершинами, введем в рассмотрение матрицы $A^{\{k\}} = A^{[k]} - A^{}$, где $k = 2,3,...,n - 1$ и $A^{\{1\}} = A^{} = A$. Отсутствие точек над обозначением матриц указывает, что мы рассматриваем матрицы $A^{[k]}$ ($k = 1,2,...,n - 1)$ как числовые (0,1)-матрицы, естественным образом получаемые из матриц $\dot {A}^{[k]}$ (булевы элементы 0 и 1 мы теперь рассматриваем как числа 0 и 1). Из способа построения матриц $A^{[k]}$ следует, что $A^{[k]} \ge A^{}$ ($k = 2,3,...,n - 1$) и, следовательно, $A^{\{k\}}$ ($k = 1,2,...,n - 1$) являются (0,1)-матрицами. Причем матрица $A^{\{2\}}$ содержит 1 только на тех местах, где определяемые этим местом (номер строки и номер столбца) вершины соединены некоторым путем длины два и не соединены меньшим путем. Аналогично, $A^{\{3\}}$ содержит 1 только на тех местах, где определяемые этим местом вершины соединены путем длины три и не соединены никаким путем меньшей длины, и т.д. Таким образом, матрица $D = \sum\limits_{k = 1}^{n - 1} {k \cdot A^{\{k\}}}$ и будет искомой матрицей расстояний. Элемент $d_{ij}$ этой матрицы и будет равен расстоянию между вершинами $i$ и $j$. Расстояние между вершинами $u$ и $v$ будем также обозначать как $d(u,v)$.

Замечание. Конкретное произведение-слагаемое $a_{il_1 } a_{l_1 l_2 } ...a_{l_{k - 2} l_{k - 1} } a_{l_{k - 1} j} = 1$ элемента $a_{ij}^{(k)}$ $k$-ой степени матрицы смежности $A^k$ задает конкретный $(i,j)$-путь $i\{i,l_1\}l_1 \{l_1 ,l_2 \}l_2 ...l_{k - 2} \{l_{k - 2} ,l_{k - 1} \}l_{k - 1} \{l_{k - 1} ,j\}j$ из $i$-ой вершины в $j$-ую. Последовательность смежных вершин и соединяющих их ребер $i\{i,l_1 \}l_1 \{l_1 ,l_2 \}l_2 ...l_{k - 2} \{l_{k - 2} ,l_{k - 1} \}l_{k - 1} \{l_{k - 1} ,j\}j$ называют ещё $(i,j)$-маршрутом . Маршрут отличается от цепи, состоящей только из различных смежных ребер, ещё тем, что в маршруте допускаются равные ребра. Простой маршрут состоит из различных смежных вершин и ребер, т.е. практически совпадает с простой цепью.

Достаточно очевидно, что элемент $d_{ij} $ матрицы расстояний определяет длину минимальной цепи соединяющей $i$-ую вершину с $j$-ой.

Рассмотрим примеры графов, заданных рисунками 1 и 2, их матриц смежности и их матриц расстояний.

Рис.1 (Граф $\Gamma _1$, матрица смежности $A_1$, матрица расстояний $D_1$).
$A_1 = \left({{\begin{array}{*c} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end{array} }} \right), $
$D_1 = \left({{\begin{array}{*c} 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end{array} }} \right) $

Рис. 2 (Граф $\Gamma _2$, матрица смежности $A_2$, матрица расстояний $D_2$).
$A_2 = \left({{\begin{array}{*c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{array} }} \right)$,
$D_2 = \left({{\begin{array}{*c} 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & 3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 \\ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \end{array} }} \right). $

По матрицам $D_1$ и $D_2$ легко определяются диаметры $d_1$ графа $\Gamma _1$ и $d_2$ графа $\Gamma _2$, как максимальные значения элементов этих матриц. Так $d_1 = 3$, а $d_2 = 6$.

Кроме матрицы расстояний теория графов рассматривает и другие матрицы, элементы которых определяются через длину пути. Таковой, например, является матрица обходов . В матрице обходов $(i,j)$-й элемент равен длине наиболее длинного пути (наиболее длинной цепи) из $i$-ой вершины в $j$-ую, а если таких путей нет вообще, то в соответствии с определением расстояния $(i,j)$-ый элемент матрицы обходов полагается равным нулю.

О методах определения минимальной и максимальной цепей с использованием матрицы расстояний, соединяющих $i$-ую и $j$-ую вершины в графе, сделаем замечание в конце параграфа.

А сейчас приведем ещё некоторые определения теории графов, связанные с расстояниями между вершинами и которые легко определяются из матриц расстояний.

Эксцентриситет $e(v)$ вершины $v$ в связном графе $\Gamma$ определяется как max $d(u,v)$ по всем вершинам $u$ в $\Gamma$. Радиусом $r(\Gamma)$ называется наименьший из эксцентриситетов вершин. Заметим, что наибольший из эксцентриситетов равен диаметру графа. Вершина $v$ называется центральной вершиной графа $\Gamma$, если $e(v) = r(\Gamma)$; центр графа $\Gamma$ — множество всех центральных вершин.

Так для графа $\Gamma _1$ с рис.1, эксцентриситет вершины 13 будет равен 2 ($e(13) = 2$). Такие же эксцентриситеты будут иметь вершины 3, 5 и 10 ($e(3) = e(5) = e(10) = 2$). Эксцентриситет равный 2 будет наименьшим для графа $\Gamma _1$, т.е. $r(\Gamma _1) = 2$. Центр графа $\Gamma _1$ будет состоять из вершин 3, 5, 10 и 13. Наибольший эксцентриситет будет равен 3 и будет равен, как отмечалось выше, диаметру графа $\Gamma _1$.

Для графа $\Gamma _2$ с рис. 2 наименьший эксцентриситет будет иметь единственная вершина 4 ($e(4) = r(\Gamma _2) = 3$). Следовательно, центр графа $\Gamma _2$ состоит из одной вершины 4. Диаметр графа $\Gamma _2$, как отмечалось выше, равен 6.

Граф $\Gamma _2$ является деревом, а структуру центра любого дерева описывает приводимая ниже теорема.

Теорема Жордана—Сильвестра. Каждое дерево имеет центр, состоящий или из одной вершины или двух смежных вершин.

Доказательство. Обозначим через $K_1$ граф, состоящий из одной изолированной вершины, а через $K_2$ — граф — из двух вершин соединенных ребром. По определению положим $e(K_1) = r(K_1) = 0$. Тогда утверждение теоремы будет выполнено для $K_1$ и $K_2$. Покажем, что у любого дерева $T$ те же центральные вершины, что и у дерева ${T}"$, полученного из $T$ удалением всех его висячих вершин. Ясно, что расстояние от данной вершины $u$ до любой другой вершины $v$ может достигать наибольшего значения только тогда, когда $v$ — висячая вершина.

Таким образом, эксцентриситет каждой вершины дерева ${T}"$ точно на единицу меньше эксцентриситета этой же вершины в $T$. Отсюда вытекает, что вершины дерева $T$, имеющие наименьший эксцентриситет в $T$, совпадают с вершинами, имеющими наименьший эксцентриситет в ${T}"$, т.е. центры деревьев $T$ и ${T}"$ совпадают. Если процесс удаления висячих вершин продолжить, то мы получим последовательность деревьев с тем же центром, что и у $T$. В силу конечности $T$ мы обязательно придем или к $K_1$, или к $K_2$. В любом случае все вершины дерева полученного таким способом, образуют центр дерева, который, таким образом, состоит или из единственной вершины, или из двух смежных вершин. Доказательство закончено.

Покажем теперь, как с помощью матрицы расстояний можно определить, например, минимальную цепь соединяющую вершину 4 с вершиной 8 на графе $\Gamma _1$. В матрице $D_1$ элемент $d_{48} = 3$. Возьмем 8-ой столбец матрицы $D_1$ и найдем в столбце все элементы этого столбца равные 1. По крайней мере, один такой элемент найдется в силу связности графа $D_1$. На самом деле таких единиц в 8-ом столбце будет три, и расположены они в 5-ой, 6-ой и 7-ой строках. Возьмем теперь 4-ую строку и рассмотрим в ней элементы, расположенные в 5-ом, 6-ом и 7-ом столбцах. Эти элементы будут 2, 3 и 3 соответственно. Только элемент, расположенный в 5-ом столбце равен 2 и вместе с 1, расположенной на месте (5,8), дает сумму 3. Значит, вершина 5 входит в цепь $\{ \{4,?\}, \{?,5\}, \{5,8\} \}$. Возьмем теперь 5-ый столбец матрицы и рассмотрим 1 этого столбца. Это будут элементы расположенные в 3-ей, 6-й, 7-ой, 8-ой, 10-ой и 13-ой строках. Вновь возвращаемся к 4-ой строке и видим, что только на пересечении третьего столбца и 4-й строки стоит 1, что в сочетании с 1 на месте (3,5) дает в сумме 2. Следовательно, искомая цепь будет $\{ \{4,3\}, \{3,5\}, \{5,8\} \}$. Посмотрев теперь на рисунок 1, убеждаемся в справедливости найденного решения.

Хотя про матрицу обхода современные учебники говорят, что «эффективных методов для нахождения её элементов не существует», будем помнить, что с использованием матрицы инцидентности мы можем найти все цепи соединяющие пару вершин в связном графе, а значит и цепи максимальной длины.

Периферийные вершины имеют эксцентриситет, равный диаметру.

Простая цепь с длиной, равной диаметру графа, называется диаметральной .

Теорема 12.1. В связном графе диаметр не больше ранга его матрицы смежности.

Теорема 12.2. (Жордана) Каждое дерево имеет центр, состоящий из одной или двух смежных вершин.

Пример 12.5. Найти радиус, диаметр и центр графа, изображенного на рис. 12.1.

Пример 12.6. Найти матрицу расстояний графа, изображенного на рис. 12.1, алгебраическим методом.

Решение. Матрица смежности данного графа равна:

Диагональные элементы матрицы расстояний – нули. Умножаем матрицу смежности на себя:

следовательно, , и окончательно

Полученная матрица совпадает с матрицей расстояний S (12.2), найденной непосредственными вычислениями по рисунку.

На основе обработанных данных может быть построено несколько моделей.

Прямоугольная вещественнозначная матрица

После обработки данных получена прямоугольная вещественная матрица. Данная матрица отражает информацию о суммарной стоимости контрактов, заключенных в m регионах (напомним, что m=86) для n классов классификатора ОКПД (все контракты проведены по 62 различным кодам классификатора). Итак, полученная матрица состоит из m n-мерных векторов.

Элементы матрицы имеют сильный разброс в диапазоне от 0 до рублей. Такой большой диапазон может создать проблемы для дальнейшего анализа данных. Тем более что некоторые классификаторы являются «популярными» и по ним проводятся частые и большие объемы закупок, как, например, по классификатору с кодом 45. В то же время код классификатора 12 (Руды урановые и ториевые) содержит очень редкие закупки на небольшие суммы. В связи с вышеописанным важно каким-то образом уравнять вклад этих величин и произвести нормировку данных. Нормировка данных - это процесс изменения исходных данных и приведения их к безразмерному виду. Данный процесс приводит к повышению качества данных.

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

1) Нормировка по регионам

Для любого региона нахождение доли участия каждого классификатора в формировании суммы стоимости контрактов в регионе i.

2) Нормировка по кодам классификатора

Для любого кода классификатора нахождение доли участия каждого региона в формировании суммы стоимости контрактов по кодам классификатора j.

3) Нормировка по численности регионов

Необходимо разделить каждый элемент матрицы на численность соответствующего региона.

Также можно рассмотреть стандартные способы нормирования данных :

1) Мини-максная линейная нормализация

где - минимальное и максимальное значения затрат для каждого региона i в векторе.

Эта нормализация приводит все данные к значениям в диапазоне.

2) Приведение к распределению вида N (стандартизация данных)

где матем. ожидание,

среднеквадратическое отклонение вектора.

3) Нелинейная нормализация

Этот метод основан на нелинейной связи между исходными и нормализуемыми данными. Необходимо выбрать некий массив данных, назвать его нормализированным и по нему построить функцию нормализации. Все остальные данные нормализовать в соответствии с этой функцией .

Квадратная матрица расстояний

От прямоугольной вещественной матрицы можно перейти к матрице расстояний между регионами. Это будет квадратная матрица размера. Расстояние можно вычислить по одной из нижеперечисленных метрик.

Рассмотрим самые распространённые метрики:

1) Евклидово расстояние

Самая распространённая метрика - представляет собой геометрическое расстояние в многомерном пространстве.

2) Метрика Минковского

Так называемое степенное расстояние. В данном случае r отвечает за взвешивание больших разностей расстояний, а р - за взвешивание разностей по координатам. Отметим, что при r,p=2 совпадает с расстоянием Евклида.

3) Манхэттэнская метрика

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

4) Косинусное сходство

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

5) Расстояние Хэмминга

Является частным случаем метрики Минковского и применяется для бинарных векторов. Для того чтобы применить это расстояние при подсчете матрицы расстояний в данной задачи необходимо изначальную вещественнозначную матрицу привести к бинарной (с помощью введения некоторого порога).

Граф близости

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

Вышеописанные модели универсальны в рамках рассматриваемой задачи.

Во-первых, они могут быть применены к данным не только за 2015, но и за любой период.

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

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