5.5. Матрица смежности вершин

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

В общем случае, имеет место следующая теорема, касающаяся матрицы смежности V графа.

Теорема 5.5. Матрица дает число ориентированных маршрутов длины между любыми двумя вершинами ориентированного графа.

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

Замечание. Очевидно, если при некотором для то в графе нет циклов. Если в графе нет циклов, то элементы дают число простых путей между любыми двумя вершинами графа.

(см. скан)

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

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

случае будет существовать еще один путь длины два из а, в и матрица будет иметь элементы

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

Индекс примитивности

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

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

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

называется индексом примитивности и обозначается

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

Определение. Если подграф графа то порядком назовем число вершин подграфа

Определение. Если ориентированный маршрут (ориентированная последовательность дуг) в ориентированном графе то длиной называется число дуг в (считая и повторения).

Лемма 5.6. Если -примитивный граф, с индексом примитивности то для всех целых существует ориентированный маршрут длины из и ориентированный маршрут длины из

Доказательство. Заметим, что если примитивная матрица, то каждая строка и каждый столбец должны содержать, по крайней мере, один ненулевой элемент. Из этого следует, что произведение содержит только положительные элементы. Действительно, произведение где любое положительное целое число, содержит только положительные элементы.

Теорема 5.7. Необходимым и достаточным условием примитивности сильно связного графа с числом вершин 2 является равенство единице наибольшего общего делителя длины всех простых циклов графа

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

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

где неотрицательное целое число для каждого

Покажем теперь, что для каждого можно так брать что окажется - константой, т. е. не будет зависеть от (Зависимость от исключается выбором

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

Теперь для каждого целого и каждого целого определяем (при достаточно больших целых

Отсюда

Последнее выражение является константой, так как не зависит от Следовательно, существует фиксированное целое

такое, что для каждой упорядоченной пары существует ориентированный маршрут длины из Таким образом, существует целое число такое, что если -матрица вершин графа то (Чтобы показать, как реализуется требуемый путь длины напомним, что

Необходимость. Предположим, что примитивный граф с 2 и индекс примитивности равен По предположению (в силу примитивности), граф сильно связен. Выберем контур (из некоторой вершины так, чтобы каждый простой контур в проходился, по крайней мере, один раз и где длина Так как можно разбить на последовательность простых контуров (обобщение упражнения 2.3 на замкнутые последовательности дуг), то число можно записать как линейную комбинацию порядков простых контуров, где все коэффициенты положительны. Далее по лемме 4,6 существует замкнутая последовательность дуг длины из и в и. Тогда по той же лемме существует замкнутая последовательность дуг (дважды и 5 длины соответственно. Заметим, что оба числа могут быть записаны как линейные комбинации чисел строго положительными коэффициентами). Отмеченное выше обобщение упражнения 2.3 можно применить к

замкнутой последовательности дуг длины и последовательность длина которой

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

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

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

Упражнении

(см. скан)

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

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

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

Теорема 5.8. Пусть примитивный граф и V — его матрица смежности. Если длина кратчайшего простого контура в то индекс примитивности матрицы

V удовлетворяет неравенству

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

Далее согласно упраженению 5.15, в существует последовательность дуг длины из в любую Таким образом, в графе последовательность дуг из имеет длину а последовательность из имеет длину

Следовательно, и

Следствие 5.9. В примитивном графе наибольший общий делитель длин всех простых циклов равен единице и, следовательно, Отсюда следует, что

Хип и Линн [11] показали, что если граф, соответствующий матрице имеет, по крайней мере, простых циклов, длины которых различны и взаимно простые, то показатель примитивности не превышает