Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 48
Текст из файла (страница 48)
Предлагаем читателю, воспользовавшись теоремой 6.63, доказать следующее утверждение. ТЕОРЕМА 6.66. Пусть С вЂ” (ориентированный) граф с вершинами иы иг, из, ..., и„и матрицей смежности А. Пусть А = А ~/ Ащг М Ащз и Аем 'и' . м Ащп. Тогда А,, = 1 тогда и только тогда, когда существует путь из и, в и,. Справедливость теоремы, приведенной ниже, следует непосредственно из определения связности графов или сильной связности ориентированных графов. По сути это та же теорема 6.65. ТЕОРЕМА 6.66.
Пусть С вЂ” (ориентированный) граф с вершинами иы иг, из, ..., и„и матрицей смежности А. Пусть Аг = 1чА иАзг'иАщз'и Аем и .'иАщ" где 1 — мультипликативная единичная матрица. Тогда Аг = 1 для всех г и г тогда и только тогда, когда граф С (сильно) связный. Из теоремы 6.65 следует, что если )т — отношение, задаваемое (ориентированным) графом С, и А — матрица смежности графа С, тогда А представляет собой матрицу смежности графа, который описывает транзитивное замыкание В. В более общем случае, когда С вЂ” граф, который не обязательно связный, для матрицы Аг справедлив следующий результат.
282 ГЛАВА 6. Графы, ориентированные графы и деревья ТЕОРЕМА 6.67. Пусть С вЂ” граф с вершинами иг, иг, из, ..., о„и матрицей смежности А. Как и ранее, пусть Аг = 1ч А У Ашг 'и Агзз 'и Аем У ы Аф" Тогда (если необходимо) вершины могут быть упорядочены таким образом, что Аг будет иметь вид А1 Аг О Аз где каждое А, представляет собой квадратную матрицу, главная диагональ которой направлена вдоль главной диагонали Аг и содержит все ее элементы, равные 1.
Как указано, любой элемент Аг, который находится вне всех матриц А,, равен О. Матрица А также может быть разбита на блоки такого же размера, что и Аг, при этом А будет иметь вид Аг Аг О Аз Здесь каждое А; имеет такую же форму, как и А„и представляет собой матрицу инцидентности компоненты графа С, а любой элемент матрицы А, находяшийся вне всех матриц А„равен О. ДОКАЗАТЕЛЬСТВО. Если все вершины С, которые принадлежат одной и той же компоненте, помешены вместе, тогда, поскольку между двумя любыми такими вершинами сушествует путь, блок матрицы Аг, состояший только из строк и столбцов, обозначенных этими вершинами, содержит в качестве элементов только единицы.
Далее, любой элемент А в этой же строке или столбце, обозначенных указанными вершинами, должен быть равен нулю, поскольку не существует пути из любой другой вершины в вершину, принадлежашую компоненте. Поскольку для блоков А; вершины, обозначающие его строки и столбцы, принадлежат одной и той же компоненте, соответствуюший блок А; в матрице А представляет граф — компоненту графа С.
Как и ранее, и по той же причине, все другие элементы той же строки или столбца матрицы А, обозначенных этими вершинами, должны быть равны нулю. Матрица А может быть вычислена как А = А У Ашг У Ашз ~гАем У .. У А~", но такой способ не очень эффективен. Намного лучший метод обеспечивает алгоритм Уоршолла, известный также как алгоритм Роя-Уоршолла. Чтобы понять, как он работает, рассмотрим матрицу смежности, изображенную на рис.
6.72. РАЗДЕЛ б.б. Матрицы инцидентности и смежности 283 Ч Чзч Ч 4 1001 01 1 0 101 0 0100 ч, д= Чз Ч4 Рис. б.72 Матрица А представляет множество всех 1-путей. Теперь необходимо найти все 2-пути, где средней вершиной является и,, чтобы скомбинировать 1-пути, которые уже имеются.
Начинаем с первого столбца. Игнорируем 1 в первой строке, если имеется 1 в 2-ой строке первого столбца, так как в этом случае существует 1-путь из и, в о1. Поскольку 1 имеется в строке 3, существует 1-путь из из в иы Теперь посмотрим на первую строку. Игнорируем 1 в первом столбце, если имеется 1 в 7-ом столбце, так как в этом случае существует ребро, или 1-путь из и1 в и .
Поскольку 1 имеется в четвертом столбце, существует ребро из и4 в и4. Таким образом, имеется 2-путь из оз через из в Ч4. Обозначим это, поместив 1 в третьей строке четвертого столбца, и получим матрицу, показанную на рис. 6.73. чччч 1 2 2 4 1001 01 1 0 101 1 01 0 0 Рис. б.7З Ч1 Ч2 Чз Ч4 Рис. б.74 То же самое можно выполнить, прибавляя вторую строку к четвертой строке. Если бы 1 находилась в 2-ой строке столбца 2 и 1 находилась бы в 7чом столбце второй строки, нам надо было бы прибавить строку 2 к строке 2.
Поскольку в первом столбце и в первой строке нет других единиц, этот шаг закончен. Если бы в любой другой строке первого столбца имелась 1, скажем, в 2ьой строке, или в любом другом столбце первой строки имелась 1, скажем, в ,7-ом столбце, тогда нам нужно было бы поместить 1 в 2-ой строке 7'-ого столбца. В нашем примере, использовав ч как сложение, мы фактически просуммировали первую строку с третьей. В общем случае, если имеется 1 в 2-ой строке первого столбца, то первая строка прибавляется к 1-ой строке. Теперь необходимо найти все пути длины не больше 3, проходящие через из и/или из (если такие имеются). Рассмотрим второй столбец.
Игнорируя 1 во второй строке, ищем 1 в любой другой строке столбца 2. Поскольку имеется 1 в строке 4, то существует 1-путь из и4 в из или 2-путь из и4 через иг в из, так как это единственный способ, которым мы можем получить единицу. Игнорируя 1 во втором столбце, ищем другие 1 в любом другом столбце строки 2. Поскольку имеется 1 в столбце 3, существует 1-путь из из в из, или 2-путь из из через из в из. В любом случае существует путь из и4 в оз такой, что он проходит только через вершины иг и из. Опять обозначаем это, помещая 1 в четвертой строке третьего столбца, и получаем матрицу, показанную на рис. 6.74.
284 ГЛАВА 6. Графы, ориентированные графы и деревья Аналогично, теперь нам необходимы все пути длины 4 или менее, проходящие через иг и/или из, и/или оз (если такие имеются). Рассмотрим третий столбец и третью строку. Если имеется 1 в 1-ой строке столбца 3 и 1 имеется в ~-ом столбце строки 3, то существует путь из ш в из, который проходит только через вершины и1 и/или из (если таковой имеется) и путь из из в и, проходящий только через вершины иг и/или из (если таковой имеется).
Поэтому существует путь из и, в и,, и 1 нужно поместить на (г,/)-ой позиции. Это равносильно сложению строки 3 с любой строкой, содержащей 1 в столбце 3. Поскольку 1 имеется в третьем столбце первой и четвертой строк, строка 3 прибавляется к каждой из этих строк. Это дает матрицу, показанную на рис. 6.75. чччч г з г 1001 1 1 1 1 101 1 111 1 Рис. б.75 Окончательно, нам необходимы все пути длины 4 или менее, проходящие через иг и/или из, и/или из, и/или и4 (если таковые существуют). Прибавляем четвертую строку к любой другой строке, в которой 1 появляется в столбце 4. Ниже приведены два алгоритма вычисления А. Оба алгоритма следуют из способа, которым проводились вычисления в нашем примере. Первый способ— самый удобный для счета вручную.
Следует помнить, что в алгоритме сложение означает булево сложение. АЛГОРИТМ УОРШОЛЛА 1 1) Просмотреть столбец 1 матрицы А. Найти строку этого столбца, в которой имеется 1, и прибавить строку 1 к этой строке. 2) Просмотреть столбец 2 матрицы, построенной в пункте (1). Найти строку этого столбца, в которой имеется 1, и прибавить строку 2 к этой строке. 3) Просмотреть столбец 3 матрицы, построенной в пункте (2). Найти строку этого столбца, в которой имеется 1, и прибавить строку 3 к этой строке. 4) Продолжать процесс просмотра следующего по счету столбца матрицы, построенной на предыдущем шаге; искать строку, содержащую 1; прибавлять строку, соответствующую исследуемому столбцу, к строке, в которой имеется 1.
8) Продолжать, пока не будут рассмотрены все столбцы. Второй метод использует тот факт, что процесс начинается с первой строки и первого столбца, и если 1-цы имеются в 1-ой строке первого столбца и в 1- ом столбце первой строки, тогда 1-ца помещается в 1-ой строке 1-го столбца матрицы.
Другими словами, если Аы —— 1 и Аг — — 1, тогда полагаем А, = 1. Если А„уже было равно 1, тогда оставляем его равным 1. Это эквивалентно следующему: "для всех г А, = А,, У (Ац А Аг ), поскольку Ам Л Агу равно 1 тогда и только тогда, когда Ац = 1 и Агу = 1, и равно 0 в противоположном случае". Используя вторую строку и второй столбец, можно было бы получить РЯЗДЕЛ 6.6.
Матриц»! инцидвнтности и смежности 285 новые значениЯ длЯ А;,, положив А;, = А;, зз (Азз Я Аз ). ПРодолжаЯ пРоцесс, приходим к следующему алгоритму в псевдокодах. АЛГОРИТМ УОРШОЛЛА 2 Цикл по зс от 1 до кс Цикл по 1 от 1 до уц Цикл по 7' от 1 до гц А!1=А, н(Аз»ЯА» ); Конец цикла; Конец цикла; Конец цикла.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
