XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 54
Текст из файла (страница 54)
С учетом идемпотентности сложения получим < хг =хг+хз +О, ХЗ =Х2 +О, х4 = х2+ хз + х4+ 1. Из второго уравнения имеем хг = 1'(хз+ 0). В полукольце В итерация любого элемента равна единице полукольца. Поэтому хг = хз+ О. Исключив хг из системы, получим < хз=хз +О, х4 = хз + х4 + 1. х1 = х2 = хз= х4 =х1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 хг+хз+х4+1, х2+хз +О~ Х2 4-0, +хз +О. 5.6. Задача о аутах Далее вычислим хз =1'0 =1 0=0. Подставив хз =0 в последнее уравнение, найдем Х4 = 1'1 = 1.
Итак, первый столбец А' есть Второй столбец определяется из системы Исключая Х1, получаем < х2 =х2+хз + 1, ХЗ=Х2 +О, Х4 = хз+хз+ха+О. Из второго уравнения имеем хз =1'(хз+1) =хз+1. Далее находим < хз=хз +1~ Х4 = Хз+ Х4+ 1. Отсюда хз = 1'1 = 1 и х4 = х4 + 1. В итоге Х4 = 1" 1 = 1, хз = =1+1=1, х1=1+1+1+0=1. Такимобраэом, второйстолбец А' есть Х4= хз = х4 = Х1 Х2+ ХЗ+ Х4+ О, х2+хз +1, хз +О, +хз +О. 334 б. ТЕОРИЯ ГРАФОВ Аналогично вычисляем третий и четвертый столбцы и в результате получаем матрицу А'. 1 1 1 1 0 1 1 0 0 1 1 0 1 1 1 1 Анализ этой матрицы показывает (см. 5.2), что данный граф связен и имеет две бикомпоненты: (ем е4) и (еэ, ез). Заметим, что в полукольце 8 можно упростить решение систем уравнений, воспользовавшись свойствами полукольца.
Легко видеть, что наименьшее решение уравнения хь =~ а х4+1 есть хь = 1 и не зависит от значений переменных в правой части уравнения. С учетом этого решение системы (5.3) упростится. Так, иэ первого уравнения сразу получаем х4 = 1. Тогда четвертое уравнение принимает вид х4 = хз + 1, откуда х4 = 1. Поскольку х4 и х4 не входят в оставшиеся два уравнения, их решение нужно искать, используя метод исключения. Пример 5.10. Для графа, изображенного на рис. 5.27, вычислим матрицу кратчайпих расстояний, перейдя к полукольцу Я+. Договоримся, что для упрощения записи оо здесь будем понимать как +со.
Наш взвешенный ориентированный граф задается теперь следующей матрицей: оо 5 10 1 оо 2 3 оо оо 1 оо оо 3 оо 4 оо (5.4) 335 5.6. Задача о путах Система для вычисления первого столбца матрицы А' имеет вид бхз + 10хз + 1х4 + О, 2хз+ Зхз +ос, 1х2 +со, + 4хз +со. х1 = Х2 = хз= х4 = Зхз хз = 2'(Зхз+со) = Зхз. Исключая хз из остальных уравнений системы и учитывая, что х1 = О, получаем С хз = Зхз+со, хз = 1(Зхз) + оо, х4=3 О+4хз+со. Далее, ю второго уравнения имеем хз =(1 З)хз+оо =4хз+оо, откуда хз =4" со=со, и поэтому х4 = 3 0+ 4 оо+ оо = 3+ оо = 3. Обратим внимание на нюансы, свюанные с работой в полукольце Я+: элементы 1 и О не являются единицей и иулеа4 полукольца, т.е.
х фх+О и х ф 1 х в общем случае. Напомним, что сложение в полукольце 1с+ — взятие наименьшего из двух чисел, а умножение — обычное арифметическое сложение. Заметим, что наличие слагаемого О в любой сумме (в полукольце) означает, что вся сумма равна О; слагаемое +со можно не за; писывать (как нуль полукольца). Из первого уравнения системы сразу следует, что х1 — — О, так как одно ю слагаемых в правой части есть элемент О. Напомним, что итерация любого элемента в рассматриваемом полукольце равна единице полукольца.
Учитавая этот факт, ю второго уравнения получаем 336 б. ТЕОРИЯ ГРАФОВ Подставляя найденное значение хз в выражение для яз, полу- чаем хэ = оо. Первый столбец искомой матрицы вычислен: Этот столбец содержит кратчайшие расстояния от всех вершин графа до вершины о~. Наличие в нем нулей полукольца во второй и третьей строках говорит о том, что вершина о~ не достижима иэ вершин ез и ез. Аналогично вычисляются остальные столбцы матрицы А". Результат будет следующим: 0 5 5 1 оо 0 3 оо оо 1 0 оо 3 5 4 0 Для данного простого ориентированного графа легко сопоставить полученный алгебраический результат с результатом „визуального" анализа ориентированного графа. Рассмотрим, например, пару вершин (ем ез).
В ориентированном графе есть различные пути вз вершины о~ в вершину ез. Легко видеть, что заведомо „не выгодны" пути, содержащие контуры и петли, поэтому их рассматривать не будем и вычислим метки по просшмм пушлм. По пути е~ -+ и4 -+ еэ сумма меток равна 5, по пути е~ -+ ез — 10, а по пути е~ -+ оэ -+ из — 8. Кратчайшее расстояние — 5, что совпадает с ответом, полученным алгебраически: элемент а~з также равен 5. Помимо изложенного есть еще один способ вычисления замыкания матрицы с элементами в замкнутом полукольце. Он основан на понятии пути ранга Й нз вершины гч в вершину е.. Пусть в ориентированном графе выбрана и зафиксирована нумерация вершин. Будем полагать, что все вершины пронумерованы подряд натуральными числами, начиная с 1. 5.6.
Задача о путал 337 Путь е14 -+ еб -1... -+ е; длины п1 называют путем ранга й при гп ) 1, если й — наибольшее среди чисел 31, ..., з,а 1, и путем ранга О при 1н = 1. Путь нулевой длины также считают путем ранга О. Таким образом, ра44г 43упан — это максимальный номер вершины, в которую разрешено заходить по пути из е4 в еу (исключая вершины е; и е ). Путь ранга О не содержит промежуточных вершин.
Максимальный ранг пути в ориентированном графе при указанном вьппе способе нумерапни равен числу его вершин. Пример 5.11. В ориентированном графе, изображенном на рис. 5.27, путь е1 -+ о4 ~ е1 имеет ранг 4, путь е4-+ е1 -+ -+ е2 — ранг 1, путь е4 -+ е1 -+ из -+ е2 — ранг 3. Пути е4 -+ нз -+ п2, п4 -4 е1 -+ ез -4 е2 и п4-+ с2 -+ п2 -+ ез-+ п2 также имеют ранг 3. ф Обозначим через С1") матрицу стоимостей прохождения между различными парами вершин по всем путям ранга, не превосходящего Й. Ее элемент с; содержит стоимость прохо- 13) ждения из вершины е; в вершину е по всем путям рангов О, 1, ..., й — 1, й. Выведем формулу для вычисления элемента с," матрицы (3) С1").
Для этого заметим следующее. По пути ранга, не боль- шего Й, из вершины е4 в вершину е можно пройти следующими способами: 1) идя иэ вершины гч в вершину е по некоторому пути ранга, не превосходящего Й вЂ” 1, т.е. минуя вершину еа, 2) сначала идя из е4 в еа по пути ранга, не большего й — 1, затем „покрутившись" "1 любое число раз (а может быть, и ни разу) по какому-либо контуру или любому замкнутому пути из еа в па ранга, не большего й — 1, и, наконец, идя из вершины еа в вершину е. по цути ранга, не большего й — 1 (рис. 5.28). ЗЗ8 0.
ТЕОРИЯ ГРАФОВ (ь-ц ~ (ь-ц~' (ь-ц с,и ~сьь ~ сь Таким образом, словесное описание „путешествия" из е; в ез по путям ранга, не большего й, приводит к следующей формуле для вычисления элемента матрицы С("): (ь) (ь-ц (ь-ц(' (ь-ц)' (ь-ц с ° = с + с1и ~слл ~ сь (5.5) Пусть а; — элементы машрипм мешок дуг ориентированного графа. Поскольку каждый путь ранга 0 между несовпа- При первом способе следования стоимость прохождения из вершины о; в е по всем путям ранга, не большего й — 1, составит с;. (л-ц При втором способе следования стоимость прохождения из 01 в еь по всем путям ранга, не большего й — 1, будет равна сря . Стоимость прохождения иэ оь в оь по всем замкнутым (л-ц путям ранга, не большего й — 1, составит (с„„) .
(л-ц е Поясним это в частном случае, когда вершина ол содержится в каком-то одном контуре. Пусть à — такой контур, а )1г— метка этого контура. Тогда очевидно, что метка пути, образованного нуль-кратным прохождением по контуру Г, равна единице полукольца (как метка всякого пути длины 0), метка же пути, образованного ш-кратным прохождением по Г при ш ) 1, равна р~~. Следовательно, стоимость прохождения по всем путям, которые получаются при произвольном числе прохождений по контуру Г, составит 2; р~~ — — и'.
ов)0 Стоимость прохождения из вершины еь в вершину е. по пути ранга, не большего й — 1, равна с, (см. рис. 5.28). (ь-ц Таким образом, стоимость прохождения по пути ранга, не большего й, при указанном способе следования составит 339 5.б. Задачв о яутюв дающими вершинами состоит иэ одной дуги, а каждая вершина достижима сама из себя по пути нулевой длины с меткой 1 или по петле с меткой аа, то элементы матрицы С( ) имеют вид (о) ав1 ' вй 3' с; 1+авв, 4=у 3 (5.6) (й) (й-1) (й-1) (й-1) с; =с; +с,„сй.
(5.7) Вычисления по формуле (5.7) начинают с матрицы С(е), определяемой соотношением (5.6). Все дальнейшие вычисления удобно также проводить в матричном виде. Для нахождения матрицы С(й) удобно определить сначала матрицу В(й), элементы которой вычисляются по формуле ~(й) (й-1) (й-1) ву =свй йу Чтобы найти у-й столбец матрицы Фй), достаточно вв-й столбец матрицы С(" 1) умножить (в смысле соответствующего полукольца) на у-й элемент Й-й строки этой же матрицы. Решим описанным способом задачу о кратчайших расстояниях в графе, изображенном на рис.
5.27. Для него С(е) = А, где матрица А имеет вид (5А). Используя формулу (5.7), по- Тогда матрицу стоимостей С = А' можно найти, вычисляя последовательно матрицы С("), вв = О,вв, по формулам (5.5) и (5.6). Вычисления по формулам 5.5 и 5.6 образуют алеорввввьм Флойда — Уорше ьла — Клини определения стоимости прохождения между любыми парами вершин. Для полуколец В и К+ в силу того, что в них итерация любого элемента х равна единице полукольца, получим упрощенный вариант формулы (5.5): 340 3. 'ГЕОРИЯ ГРАФОВ следовательно находим 0 5 10 1 оо 0 3 оо оо 1 0 оо 3 8 4 0 0 5 8 1 С(г) оо оо 1 0 оо 3 8 4 0 С(') = 0 5 8 1 С(з) оо 0 3 оо оо 1 0 оо 3 5 4 0 0 5 5 1 оо 0 3 оо оо 1 0 оо 3 5 4 0 С(4) = Например, матрица С(2) по матрице С(1) вычисляется так.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
