Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
слово х, что o(xQ <8> у0) = х <S> Тх.
Рассмотрим отображение
<р: х(r)Тх •* xQ 0 у0,
которое заключается в том, что сортируются столбцы из х <8" Тх по верхней
букве, причем если у двух столбцов верхние буквы совпадают, то их
положения не меняются:
х (abadabbcdc\ ^ Тх \badabbcdca)
aaabbbccdd\
bdbabcdaac
*0
V
Выделим слева для каждой буквы, отличной от начальной, тот столбец,
который соответствует последнему вхождению этой буквы в слово х:
D = (Ш [сас
Очевидно, если проделать такую же операцию справа, то получится тот же
набор столбцов D.
В графе D число ребер на 1 меньше числа вершин, поэтому он является
деревом. В то же время начальная буква а отсутствует в верхней строке,
следовательно, из нее не выходит ни одного ребра. Таким образом, D
является деревом, входящим в начальную вершину а.
Если мы хотим построить отображение <р ^, обратное к отображению <р, то
мы должны, очевидно, возвращаться от (х0 0 >'0) к (дс (c) Тх) следующим
образом:
x^(aaabbbccdd\ 1 *0
bdbabcdaac
lab.., ba...
Выделяем первый столбец и вычеркиваем его. Нижняя
буква b указывает на то, что нужно найти первый столбец с буквой b
вверху. Вычеркиваем этот столбец. Теперь очередь за
столбцом и т. д.
Применим теперь отображение к произвольному графу
*0 (r) >'0, где *0 и >'0 имеют одну и ту же композицию, a
отсортировано. После очередного вычеркивания для всех букв, кроме буквы
а, выполняется свойство: число вхождений буквы в нижнее слово на 1 меньше
числа вхождений этой буквы в верхнее слово. Поэтому процесс вычеркивания
не может прерваться из-за того, что не хватит некоторой буквы в верхнем
слове.
Иначе обстоит дело с буквой а: число вхождений этой буквы в верхнее слово
на каждом шаге алгоритма на 1 меньше числа вхождений в нижнее слово.
Поэтому может оказаться, что внизу появился запрос на эту букву, а ее
лимит вверху уже исчерпан:
laaabbbccdd\
{bdbabcadacj -* (abadabc).
1352 67 4
77
Здесь дальнейшее продолжение невозможно: требуется буква а вверху, а все
такие буквы уже вычеркнуты.
Такая ситуация не может возникнуть, когда D является деревом, входящим в
вершину а. Действительно, допустим, что еще не вычеркнут некоторый
столбец из D с нижней буквой,
отличной от а, скажем, . Это значит, что вверху еще
присутствует буква с, а значит еще не вычеркнут столбец из D с буквой с
вверху. Допустим, что этот столбец имеет вид
d вверху. Поскольку все пути в графе D ведут к вершине а, найдется
невычеркнутый столбец из D с буквой а внизу, ска-
Таким образом, когда D является деревом, входящим в а, столбец из А с
буквой а внизу вычеркивается последним, когда не останется ни одного
столбца в исходном графе jcq <8> _yQ.
Отсюда возникает следующий алгоритм построения эйлерова контура:
1) Найти остовное дерево D, входящее в а, где а-произвольная вершина,
выбранная в качестве начальной. Поскольку граф связен, такое дерево
всегда существует и для его построения можно использовать алгоритм,
описанный в п. 4.4.
2) Для фиксированного отсортированного слова jcq построить
нижнее слово yQ, имеющее ту же композицию, что и xQ. Для этого буквы
слова _yQ, соответствующие последним вхождениям каждой буквы в слово jcq,
заполняем в соответствии с деревом D. Остальные буквы слова yQ заполняем
произвольным образом в
соответствии с переходной матрицей графа.
3) Найти эйлеров контур, применяя алгоритм вычеркивания.
В нашем примере остовное дерево можно выбрать следующим образом:
Заключаем, что еще не вычеркнут столбец из D с буквой
Вписываем это дерево в jcq <8> yQ:
xJaaabbbccdd yQ ad а Г
78
Заполняем остальные места слова
xQ (aaabbbccdd\ *0
bbdcbaadca
Применяем алгоритм вычеркивания:
aaabbbccdd\ , , ,, , ,ч
bbdcbaadca J ^cabbadcd)
1 4 7 2 56 3 9 8 10
4.11. Максимальный поток в сети
Под сетью будем понимать орграф, в котором каждой дуге ставится в
соответствие неотрицательное целое число с(и, v), называемое пропускной
способностью дуги. В сети выделяются две вершины, которые называются
источником s и стоком t. В источник не входит ни одна дуга, а из
стока не выходят дуги.
Говорят, что задан поток из s в t в сети, если каждой дуге
поставлено в соответствие целое число f(u, v) со следующими свойствами:
1) Для всех дуг (и, v) 0 < f(u, v) < с(и, v).
2) Для каждой вершины х * s, t ^ f(u> х) ~ 2 ^х' v)'
и -" X х -" V
Здесь ^ означает суммирование по всем вершинам, из которых и -" X
можно попасть в х. Соответственно, ^ означает суммирование
х -" v
по всем вершинам, в которые можно попасть из х.
Таким образом, второе условие представляет собой "закон сохранения" для
каждой вершины, отличной от s и (.
Соединим теперь s и t фиктивной дугой (/, s) и зададим значение f(t, s)
таким образом, чтобы закон сохранения выполнялся и для вершин s и t:
Siu *) = 2 v) = 2 0;
s -" V u -" t
fit, s) называется величиной потока из s в t.
Требуется найти поток максимальной величины.
Такая задача возникает при пересылке товаров по железной дороге (без
хранения их на промежуточных станциях), при управлении потоками
