КНИГИ ПО ТЕОРИИ ВЕРОЯТНОСТЕЙ, СТАТИСТИКЕ, КРИПТОГРАФИИ, ДИСКРЕТНОЙ МАТЕМАТИКЕ

Сачков В.Н., Тараканов В.Е.
Комбинаторика неотрицательных матриц

Цена: 212.00 руб.

Объектом исследований, составляющих содержание книги, являются неотрицательные матрицы. Их разнообразные комбинаторные свойства широко обсуждаются в математической литературе, им посвящено значительное количество статей. Вместе с тем, монографическая литература по комбинаторным свойствам неотрицательных матриц сравнительно немногочисленна. Авторы книги старались сосредоточить внимание не на традиционных алгебраических, и, в частности, спектральных свойствах неотрицательных матриц а на том, чтобы выявить и проследить их связь с различными математическими структурами, изучение которых составляет предмет комбинаторной математики. Помимо традиционных применений неотрицательных матриц в теории графов, цепей Маркова, турниров, абстрактных автоматов, устанавливаются связи с неотрицательными матрицами таких объектов, как покрытия и минимальные покрытия конечных множеств системами их подмножеств. Наряду с изучением комбинаторных понятий, интерпретируемых с помощью неотрицательных матриц, большое внимание уделено исследованию разнообразных свойств самих матриц, а также классов, объединяющих матрицы с заданным строением. Значительное место занимает изучение асимптотических свойств неотрицательных матриц при неограниченном росте тех или иных параметров, характеризующих матрицу.

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

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

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

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

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

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

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

В заключение отметим, что отдельные части книги написаны разными авторами: В.Н.Сачковым - главы IV-VI, В.Е.Таракановым - главы I-III. Однако авторы хотели бы подчеркнуть единство подхода к материалу и общность идей, положенных в основание книги.

Содержание:

Предисловие

Список обозначений

Глава I. Матрицы и конфигурации

   Введение

1. Определения и примеры

2. Граничный ранг. Распределение положительных элементов

3. Матриц инцидентности специальных комбинаторных конфигураций

4. Комбинаторика циклических матриц

5. Матрицы и графические конфигурации

Глава II. Классы Райзера

   Введение

1. Конструктивное описание классов Райзера

2. Инвариантные множества

3. Оценки граничного ранга

Глава III. Неотрицательные матрицы и экстремальные комбинаторные задачи

   Введение

1. Запретные конфигурации

2. Задача о покрытии

3. Неотрицательные матрицы и экстремальная теория гиперграфов

4. Теорема ван дер Вардена-Егорычева-Фаликамана

Глава IV. Асимптотические методы изучения неотрицательных матриц

   Введение

1. Неотрицательные матрицы и графы

2. Асимптотика числа примитивных (0,1)-матриц

3. Асимптотика перманента случайной (0,1)-матрицы

4. Случайные решетки и булевы алгебры

5. Покрытия множеств и (0,1)-матрицы

6. Случайные покрытия множеств

7. Асимптотика числа t-минимальных покрытий множества

Глава V. Вполне неразложимые, цепочечные и простые матрицы

   Введение

1. Вполне неразложимые и цепочечные матрицы

2. Прямоугольные неотрицательные матрицы

3. Прямоугольные неотрицательные цепочечные матрицы

4. Продолжение частичных диагоналей

5. Простые булевы матрицы

6. Простые неотрицательные матрицы

7. Выпуклый многогранник дважды стохастических матриц

Глава VI. Последовательности неотрицательных матриц

   Введение

1. Орграфы неотрицательных матриц

2. Неразложимые и примитивные матрицы

3. Турнирные матрицы

4. Ассоциированный оператор

5. Последовательности степеней неотрицательной матрицы

6. Эргодичность последовательностей неотрицательных матриц

Литература

2000, 448 cтр., ISBN 5-85484-011-1, на русском языке