Дискретно-непрерывная математика (стр. 88 )

5.32. Графы и собственные значения неотрицательных матриц

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

k-разделимым (k≥2) тогда и только тогда, когда множество вершин V можно разделить на k множеств V1,...,Vk так, что все дуги удовлетворяют следующему свойству: если некоторая дуга имеет начальную вершину в Vp, то ее конечная вершина находится в Vp+1 при p<k в в V1 при p=k. Любой n×n-матрнце A={аij) можно поставить в соответствие ориентированный граф, коэф­фициенты матрицы смежности которогo равны единице, если соответствующие аij≠0. Если этот граф контурно k-разделимый, то разделению V1, ..., Vk соответствует перестановочная матрица Р такая, что

где О1, …., Оk — нулевые матрицы и каждый элемент Р-1АР, не принадлежащий В1, ..., Вk, равен нулю. Мат­рицы В1, ..., Вk известны под названием циклических компонент А.

Таким образом, контурно k-разделимый граф имеет структуру, показанную на рис. 5.74.

Рис. 5.74.

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

начальная и конечная вершины находятся в Vi и Vj со­ответственно, то j≡i+n(mod k). В частности, длина каждого контура кратна k.

Матрица А размера n×n имеет k диагональных компонент А1, А2, ..., Аk, если существует перестано­вочная матрица Р такая, что

Р-1АА = диагонали {А1, .. ., Аk). Указанная матрица Р существует, например, если А неприводима (это аналогично требованию силь­ной связности графа, соответствующего А).

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

Теорема 5.12. Если А — такая матрица, что соответ­ствующий ей ориентированный граф циклически k-разделимый и А1, А2, ..., Ak — множество диагональных компонент Аk, то существует нормированный многочлен f(λ) и неотрицательное целое число р такие, что f(0)≠0, при этом характеристический многочлен Аk есть f(λk)λp,a характеристический многочлен Аk есть [f(λk)]λp Кроме того, существуют целые числа р1,..., рk с суммой, равной р, такие, что характеристический многочлен Аi есть f(λk)λpi (i=l,..-, k) и для любого ненулевого корня f(λ) простейшие делители одинаковы для каждого А.

Упражнение 32. Используя пример Далмэджа и Мендельсона для

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

и циклических компонентах

Показать, что граф также является контурно 2-разделимым при раз­биении V1 = { v4, v4}, V2={v2, v3}, и в этом случае

Показать, что диагональные компоненты А при обоих разбиениях одинаковы и равны

Наконец, показать, что искомый многочлен имеет вид

и что все р в обоих случаях равны нулю.

5.33. Задача ранжирования

Рассмотрим задачу ранжирования элементов некото­рого множества

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

1. Любое лицо побеждает любое другое, либо терпит поражение от него.

2. Отношение «может победить» — транзитивно.

В первом случае существующее линейное упорядоче­ние восстанавливается с помощью последовательности попарных взвешиваний объектов на весах. Во втором — необходимо провести последовательность состязаний между парами лиц. Если t последовательных состязаний проводятся с 2t различными лицами, то можно считать, что они проходят одновременно. Однако в данном случае для нас интересно общее число состязаний, а не число уровней в иерархии частично совпадающих по времени состязаний.

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

Мы хотим найти процедуру, которая минимизирует Sp(n). He будем останавливаться на формальном определении того, что есть процедура. Пусть под процедурой имеется в виду правило выполнения после­дующего сравнения (или останова), которое полностью определяется исходами предыдущих сравнений и может быть реализовано при любом возможном наборе преды­дущих исходов.

Для решения задачи Штейнгауз предложил следующую процедуру. В первый момент сравнить два любых элемента. Затем в общем случае после полного ранжирования подмножества из k элементов взять любой (k+1)-й элемент sk+1 и сравнить его со средним из уже проранжированных k элементов (с любым из средних, если k четно). В зависимости от исхода этого сравнения сравнить sk+1, со средним элементом подмножества эле­ментов, имеющих более высокий или менее высокий ранг по отношению к элементу, участвовавшему при первом сравнении. Так, последовательными дихотомиями точно устанавливается ранг sk+1 элемента в совокупности (k+1) элемента.

Полученная ранжировка используется далее как сле­дующая опорная точка при определении ранга любого нового sk+2-го элемента. Рассмотренный процесс продол­жается до тех пор, пока не будут установлены ранги всех элементов.

Пусть в качестве примера мы проранжировали эле­менты от s1 до s15: а истинный ранг s16 находится между s10 и s11. Последовательность выполняемых сравнений показана дугами и на рис. 5.75.

Рис. 5.75.

Сравниваемые элементы обозначены своими индексами. Таким образом, элемент s16 сравнивается с s8, sl2, sl0 и s11.

В общем случае, можно показать, что для установле­ния ранга любого (k+1)-го элемента при наличии полностью упорядоченного подмножества из К элементов требуется не более S(k) = l + [log2 k] сравнений, где [log2k] обозначает целую часть log2k. Mожно также показать, что если рассмотренная процедура использу­ется для последовательного ранжирования п элементов, то при этом потребуется выполнение не более

и не менее

сравнений.

Форд и Джонсон предложили более эффектив­ный способ ранжирования, основанный на методе Штейнгауза. Пусть нужно проранжировать 2r или (2r+1) элементов. Образуем r непересекающихся пар и сравним эти пары. Возьмем r элементов, выбранных в процессе этих сравнений (т. е. элементы с максимальными ранга­ми из 2r исходных) и проранжируем их по методу Штейнгауза.

На рис. 5.76 представлены результаты ранжирования для случая множества, со­стоящего из 19 элементов.

Рис. 5.76

На первом этапе сравнения было отобрано п элементов в порядке убывания рангов J, I, Н,..., С, В. Девять вершин, расположенных ниже названных, соответствуют элементам, отброшенным на первом этапе, причем каждая вершина располагается под соответствующим отобранным элементом (крайний левый эле­мент вообще не уча­ствовал в сравнении на первом этапе). Так как 10 элементов множества А, В, С, ..., J уже проранжировано, остается найти ранги остальных девя­ти. Для этой цели использовалась процедура Штейнгауза. Порядок ранжирования элементов показан на рис. 5.76 числами без скобок. Этот порядок выбран с учетом минимизации максимального требуемого числа сравне­ний. Числа в скобках указывают максимальное число срав­нений при определении ранга соответствующего элемента. Показано, что такой метод требует (при п элементах) не более U(n) сравнений, где