Читать онлайн «Комбинаторика неотрицательных матриц»

В. Н. САЧКОВ, В. Е. ТАРАКАНОВ КОМБИНАТОРИКА НЕОТРИЦАТЕЛЬНЫХ МАТРИЦ Предисловие Объектом исследований, составляющих содержание книги, являются неотрицательные матрицы. Их разнообразные комбинаторные свойства широко обсуждаются в математической литературе, им посвящено значительное количество статей. Вместе с тем, монографическая литература по комбинаторным свойствам неотрицательных матриц сравнительно немногочисленна. Авторы книги старались сосредоточить внимание не на традиционных алгебраических, и, в частности, спектральных свойствах неотрицательных матриц, а на том, чтобы выявить и проследить их связь с различными математическими структурами, изучение которых составляет предмет комбинаторной математики. Помимо традиционных применений неотрицательных матриц в теории графов, цепей Маркова, турниров, абстрактных автоматов, устанавливаются связи с неотрицательными матрицами таких объектов, как покрытия и минимальные покрытия конечных множеств системами их подмножеств. Наряду с изучением комбинаторных понятий, интерпретируемых с помощью неотрицательных матриц, большое внимание уделено исследованию разнообразных свойств самих матриц, а также классов, объединяющих матрицы с заданным строением. Значительное место занимает изучение асимптотических свойств неотрицательных матриц при неограниченном росте тех или иных параметров, характеризующих матрицу. В книге представлены как перечисленные задачи, так и экстремальные проблемы комбинаторики. При изучении перечислительных задач вместе с использованием чисто комбинаторных методов, применяются также вероятностные подходы. Среди экстремальных задач изучаются как проблемы, непосредственно связанные с самими матрицами, так и те, в которых неотрицательные матрицы являются удобным инструментом исследования. В связи с принятым в книге комбинаторным подходом весьма существенную роль играет «бинарная» структура неотрицательной матрицы — взаимное расположение ее положительных элементов и нулей. От нее зависят и такие особенности матриц, которые, с первого взгляда, не имеют комбинаторного характера. Примером могут служить вопросы эргодичности для цепей Маркова, рассмотренные в гл. IV. Эта «бинарная» природа неотрицательных матриц проявляется в том, что их многие существенные свойства определяются свойствами носителей — (0,1)-матриц, получающихся заменой положительных элементов матрицы на единицы. Поэтому много внимания в книге уделено именно (0,1)-матрицам. При изучении свойств неотрицательных матриц мы проводим их разграничение на глобальные и локальные свойства. Если первые характеризуют матрицу в целом, то вторые связаны с соотношениями между отдельными ее частями. Примерами глобальных свойств служат такие характеристики, как распределение положительных элементов по строкам и столбцам, граничный ранг и ранг покрытия. К локальным свойствам относятся, например, различные условия на скалярные произведения строк и столбцов матрицы (понимаемых как векторы в соответствующем пространстве над действительными числами) или наличие (а также отсутствие) в ней подматриц заданной структуры.