Правило смежности

Правило смежности

Январь 5, 2013

§12. Инварианты матриц смежности и необходимые условия изоморфизма графов

При формулировке задачи об изоморфизме двух графов мы отметили, что эта задача сводится к отысканию такой нумерации вершин в каждом графе и связанной с ней нумерацией ребер, чтобы их матрицы инцидентности совпадали. Если такая нумерация существует, то графы изоморфны, если не существует, то нет. Под связанностью нумерации ребер с нумерацией вершин, мы полагали порядковую нумерацию лексикографического расположения ребер $\< i,j\>$, связывающих вершины $i$ и $j$ (обозначение вершин мы отождествляем с их номерами).

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

Известно, что перестановка строк матрицы $B$ (как и любой матрицы) эквивалентна умножению её слева на некоторую матрицу перестановки $P$. Аналогично, перестановка столбцов матрицы $B$ (как и любой матрицы) эквивалентна умножению её справа на некоторую матрицу перестановки $\tilde

$ порядка совпадающего с числом столбцов матрицы $B$.

Напомним, что матрица смежности графа получалась нами из матрицы $G = BB^T$ заменой элементов главной диагонали на нули. Посмотрим, как изменится матрица $G$ при изменении нумерации ребер и нумерации вершин.

Пусть при изменении нумерации ребер матрица $B$ примет вид $\hat = B\tilde

$. Рассмотрим произведение матриц $\hat $ на $\hat ^T$, получим $\hat \hat ^T = B\tilde

(B\tilde

)^T = B\tilde

(\tilde

^TB^T) = B(\tilde

\tilde

^T)B^T = BB^T = G$.

Итак, мы видим, что при изменении нумерации ребер матрица $G$, а, следовательно, и матрица $A$ смежности графа не меняются.

Посмотрим теперь, что произойдет с матрицей $G$ при изменении нумерации вершин. Обозначим вновь, измененную через изменение нумерации вершин, матрицу $B$ через $\hat $, т.е. положим $\hat = PB$, и вычислим произведение $\hat = \hat \hat ^T$. Подставим в выражение для $\hat $ вместо $\hat = PB$ и $\hat ^T = (PB)^T = P^TB^T$ их выражения, получим $\hat = (PB)(B^TP^T) = P(BB^T)P^T = PGP^T$. Преобразование матрицы $G$ в матрицу $PGP^T$ является частным случаем преобразования подобия ($C^<-1>GC$ — общий вид преобразования подобия с невырожденной матрицей $C$). Этот частный случай будем называть преобразованием перестановочного подобия, а про матрицы$\hat $ и $G$ будем говорить, что они перестановочно подобны, если существует такая матрица перестановки $P$, что $\hat = PGP^T$. Преобразование перестановочного подобия матрицы $G$ называют также перестановкой рядов матрицы (соответствует перестановке строк и такой же перестановке столбцов). Перестановка рядов не меняет элементов матрицы, она только переставляет элементы местами. При такой перестановке элементы главной диагонали остаются на главной диагонали, меняясь местами. В этом легко убедиться, если рассмотреть перестановку двух рядов в диагональной матрице (поменяются местами два элемента), а затем припомнить, что любая перестановка может быть получена с помощью процесса последовательных перестановок двух элементов. (Отметим, что матрицы перестановок одного порядка образуют группу относительно умножения матриц, которую будем обозначать как $\Pi$).

Это замечание позволяет нам подчеркнуть, что $\hat = PGP^T = P(A + S)P^T = PAP^T + PSP^T$, т.е. матрица $A$ смежности графа и диагональ матрицы $G$ меняются по одному и том уже закону, причем матрица $PAP^T$ будет матрицей смежности графа (с измененной нумерацией вершин), поскольку она симметричная (0,1)-матрица с нулевой главной диагональю.

Итак, мы получили следующее правило: при изменении нумерации вершин, заданной матрицей $P$, матрица $A$ смежности графа переходит в перестановочно подобную матрицу $PAP^T$. Отсюда уже легко следует утверждение-теорема: два графа изоморфны тогда и только тогда, когда их матрицы смежности перестановочно подобны.

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

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

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

Читайте так же:  Как получить справку о том что судимость погашена

Разбиение всего множества матриц смежности порядка $n$ на классы перестановочно подобных между собой матриц равносильно перечислению всех $n$-вершинных графов — одному классу соответствует один граф, различным классам соответствуют различные графы. Тогда число элементов в классе перестановочно подобных матриц можно трактовать как число различных «записей» графа (матрица смежности, как одна из возможных записей графа). Проблему изоморфизма графов теперь можно сформулировать следующим образом: имея две записи графов ответить на вопрос 𔃊 это записи одного графа или различных? Понятно, что разные графы имеют, вообще говоря, разное число записей. Проблема изоморфизма тем сложнее, чем большее число возможных записей имеет граф.

Обратим внимание, что мы воспользовались очевидными свойствами матрицы перестановки $P$: $PJ = J$ и $J^TP = J^T$. Эти свойства позволяют выделить из класса (0,1)-матриц матрицы перестановок: (0,1)-матрица P будет матрицей перестановки тогда и только тогда, когда $PJ = P^TJ = J$. В передаче этой формульной записи словами это будет звучать так: (0,1)-матрица $P$ будет матрицей перестановки тогда и только тогда, когда она в каждой строке и каждом столбце будет содержать ровно одну единицу.

Вернемся вновь к инвариантам. Кроме очевидных инвариантов — числа вершин и числа ребер графа мы указали в качестве инварианта характеристический многочлен матрицы смежности. Характеристический многочлен матрицы порядка $n$ является многочленом $n$-ой степени и характеризуется $n+1$ коэффициентом. Но, поскольку у всех характеристических многочленов коэффициент при старшей степени равен 1, то будем считать, что характеристический многочлен характеризуется $n$ параметрами (коэффициентами). Это означает, что характеристический многочлен как инвариант дает нам набор из $n$ числовых инвариантов (коэффициентов характеристического многочлена).

Известно, что между коэффициентами характеристического многочлена и следами степеней матриц (до $n$-ой включительно) существует взаимно однозначное соответствие — одни величины единственным образом выражаются через другие и обратно. Поэтому вместо операций с характеристическими многочленами мы будем оперировать со степенями матриц смежности. При этом мы не будем вычислять следы степеней матриц (сумму диагональных элементов), а будем целиком использовать главную диагональ, как содержащую гораздо больше информации. Так столбец строчных сумм $S_A$ содержит больше информации, чем сумма его элементов, равная удвоенному числу ребер (равная числу элементов матрицы $A$). Столбец строчных сумм $S_A$ дает нам характеристику каждой отдельной вершины (i-ый элемент столбца $S_A$ равен степени $i$-ой вершины). Ясно, что эта информация больше содействует задаче различения графов.

www.apmath.spbu.ru

Матрицей смежности

Смежные дуги – это дуги инцидентные одной вершине.

Смежные вершины – вершины, инцидентные одной дуге.

Матрица смежности — это матрица смежных вершин.

Матрица смежности заполняется по следующему правилу:, если из i-той вершины исходит дуга в j – тую вершину; во всех остальных случаях (для удобства и наглядности на практике в матрице смежности нули не проставляются).

Для графа, представленного на рис. 3.2 матрица смежности имеет вид:

Полустепенью захода i–той вершины называется число дуг, заходящих в данную вершину.

Полустепенью исхода i-той вершины называется число дуг, исходящих из данной вершины.

Степенью i-той вершины исхода называется сумма полустепеней захода и исхода:

(3.2)

Свойства матрицы смежности:

1. Сумма единиц по строке определяет полустепень исхода;

2. Сумма единиц по столбцу определяет полустепень захода;

3. Сумма единиц по строкам и по столбцам определяет степень вершин.

Основное свойство графа:

В любых графах число вершин с нечетной степенью четно.

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

Длиной путиназывается количество пройденных дуг.

Простой путь – это такой путь, в котором дуга встречается не более одного раза.

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

Контур – путь, начинающийся и заканчивающийся в одной точке.

Петля – контур длиной в одну единицу.

Графы бывают двух видов:

· ориентированный граф (орграф) — это граф, состоящий из вершин и дуг.

· неориентированный граф – это граф, состоящий из вершин и ребер. Ребро – это дуга, не имеющая направление.

Рис. 3.3. Неориентированный граф

В неориентированном графе путь называется цепью; контур – циклом.

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

Матрица инцидентности для неориентированного графа составляется по правилу:

· , если i-тая вершина инцидентна j-тому ребру;

· , если i-тая вершина не инцидента j-тому ребру;

· , если. в i-той вершине j-тое ребро образует петлю.

Для графа, представленного на рис. 3.3, матрица инцидентности имеет вид:

studopedia.ru

Представление графов: матрица смежности

Что такое матрица смежности

Пусть есть граф с n вершинами, пронумерованными числами от 1 до n. Составляется матрица A размера n x n со следующими правилами для элементов. I. Если элемент не на диагонали, то элемент (i, j) равен: a) 1, если вершины i и j соединены ребром (для неориентированных графов) или в вершину j заходит дуга из вершины i (для ориентированных графов); b) 0, если условие a не выполнено. II. Если элемент на диагонали (i=j), он равен единице, если вершина i имеет петлю (дугу или ребро с исходом и заходом в одну и ту же вершину), и 0, если петли нет. Эта матрица и называется матрицей смежности.

Читайте так же:  Размер госпошлины в кассацию

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

Заметим, что для одного и того же графа может быть не одна матрица смежности — это видно, если менять нумерацию вершин.

Когда матрица смежности симметрична?

Нетрудно заметить, что если граф неориентированный, матрица смежности симметрична относительно главной диагонали, то есть элементы (i, j) и (j, i) равны. Стало быть, можно хранить не всю матрицу смежности, а лишь её верхний треугольник (включая диагональ):

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

Свойство степеней матрицы смежности

Сначала напомним, что такое степень матрицы. Квадрат матрицы A — произведение A на её же саму. Куб матрицы A — произведение квадрата матрицы A на матрицу A. И так далее. То есть степень m будет означать произведение степени m-1 матрицы A на саму матрицу A.

Если матрица смежности A возведена в степень m, то элемент (i, j) матрицы-степени показывает, сколько есть путей из вершины i в вершину j, состоящих ровно из m рёбер или дуг.

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

Преимущества и недостатки матрицы смежности

Главное преимущество матрицы смежности перед другими способами представления графов: можно легко ответить на вопрос, если ли дуга (ребро) между заданными вершинами.

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

Обобщение на мультиграфы и взвешенные графы. Матрица весов

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

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

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

crypto.hut2.ru

Математические методы описания моделей конструкций РЭС. Элементы теории графов

17. 2. Части графа

Граф является частью графа , если и , т.е. граф содержит все вершины и рёбра любой его части.

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

Часть, которая наряду с некоторым подмножеством рёбер графа содержит все вершины графа ( , ), называется суграфом.

Исходный граф по отношению к его подграфу называют надграфом, а по отношению к суграфу — сверхграфом.

Совокупность всех рёбер графа, не принадлежащих его подграфу (вместе с инцидентными вершинами ), образует дополнение подграфа (рис. 17.12).

Связный неориентированный граф , не содержащий циклов , называют деревом.

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

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

17. 3. Способы задания графов

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

Условные обозначения таких графов и , соответственно.

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

Матрица смежности

Из ранее сказанного известно, что две вершины и графа называются смежными, если они являются граничными вершинами ребра .

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

Для неориентированных графов такие пары неупорядочены, так что

Читайте так же:  Пособие по беременности и родам рассчитать 2018

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

Множество вершин вместе с определённым на нём отношением смежности полностью определяет граф.

Граф можно представить матрицей смежности .

Строки и столбцы матрицы соответствуют вершинам графа , а её элемент равен числу кратных рёбер, связывающих вершины и (или направленных от вершины к вершине для орграфов ).

Например, для графа рис. 17.2, а, матрица смежности имеет вид

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

В столбцах и строках, соответствующих изолированным вершинам , все элементы равны нулю. Элементы матрицы простого графа равны 0 или 1, причём, элементы главной диагонали равны 0.

Правильность составления матрицы легко проверить: для неориентированного графа сумма элементов в каждом i -том столбце или строке соответствует степени вершины . Если элементы матрицы расположенные на главной диагонали, отличны от нуля, то это свидетельствует о наличии петель в вершине .

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

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

В САПР широко используют две разновидности таких матриц: матрицу весовых соотношений и матрицу длин .

Матрица весовых соотношений

Это квадратная матрица , общий элемент которой

где — вес связи .

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

Это квадратная матрица общий элемент которой

где — длина ребра .

В евклидовой метрике расстояние между двумя точками на плоскости

где и — координаты вершин и , соответственно.

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

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

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

В этом случае расстояние между двумя точками представляется в виде степенной функции:

где — показатель степени (как правило, ).

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

Матрица инцидентности

Если вершина является концом ребра то говорят, что они инцидентны: вершина инцидентна ребру и ребро инцидентно вершине . В то время как смежность представляет собой отношение между однородными объектами ( вершинами ), инцидентность — это отношение между разнородными объектами ( вершинами и рёбрами).

При рассмотрении орграфов различают положительную инцидентность ( дуга исходит из вершины ) и отрицательную инцидентность ( дуга заходит в вершину ).

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

Для неориентированного графа элементы этой матрица определяются по следующему правилу: ij — элемент равен 1, если вершина инцидентна ребру и равен нулю, если и не инцидентны .

В случае орграфа ненулевой — элемент равен , если — начальная вершина дуги , и равен , если — конечная вершина дуги .

Приведём пример: составим матрицу инцидентности для рис. 17.2,а.

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

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

Нулевая строка соответствует изолированной вершине , а нулевой столбец — петле.

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

Правильность составления матрицы легко проверить: число единиц в i-ой строке матрицы соответствует степени вершины графа, а число единиц в каждом столбце — двум, так как каждое ребро соединяет две вершины графа . Единственное исключение составляет петля, дважды инцидентная одной и той же вершине .

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

Граф однозначно задаётся матрицами смежности и инцидентности. В свою очередь, каждая из этих матриц полностью определяет граф.

Существуют простые приёмы перехода от одной матрицы к другой.

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

www.intuit.ru

Обсуждение закрыто.
© 2021