Введение к работе
Актуальность темы. В настоящее время, в связи с усилением значимости информационных технологий, задачи теоретической кибернетики и информатики переживают бурный рост и развитие. При изучении сложных систем и построении их моделей приходится иметь дело с большим количеством параметров, учитывать всевозможные свойства систем и их различные состояния. Поэтому для исследования сложных систем все шире применяются методы дискретной математики в целом и комбинаторного анализа в частности.
Основополагающим для современного комбинаторного анализа является введенное В.Н. Сачковым понятие комбинаторной конфигурации, включающее в себя множество различных типов дискретных систем, таких как конфигурации подмножеств, тактические конфигурации и блок-схемы, графы и сети и т.д. Чаще всего на комбинаторных конфигурациях рассматривают задачи, требующие установления факта существования конфигураций, построения конфигураций определенного вида (задачи комбинаторного моделирования), задачи перечисления всех конфигураций системы (задачи перечислительной комбинаторики) и задачи о выборе конфигураций, удовлетворяющих заданным требованиям (экстремальные комбинаторные задачи). Характерная общность и высокая степень абстракции постановок задач дает возможность получения различных интерпретаций и широту их применения.
Настоящая диссертационная работа принадлежит области комбинаторного анализа и посвящена изучению свойств матриц, являющихся матрицами инцидентности комбинаторных конфигураций.
Можно говорить о том, что на стыке теории матриц и комбинаторного анализа сформировалось новое направление — комбинаторная теория матриц, использующая методы линейной алгебры и комбинаторики. Объектом изучения данной области науки являются, главным образом, неотрицательные целочислен-
ные матрицы, которые рассматриваются в качестве матриц инцидентности для различных комбинаторных конфигураций1.
Неотрицательные целочисленные матрицы находят свое приложение в теории вероятностей, в теории цепей Маркова, в теории автоматов, в задачах о существовании и покрытии множеств, в линейном программировании, при построении и анализе экономических моделей, в теории информации при разработке информационных устройств и обеспечении их надежного функционирования.
Особую роль в комбинаторике неотрицательных матриц занимают матрицы, состоящие из нулей и единиц. Это связано с тем, что многие существенные свойства неотрицательных матриц общего вида определяются свойствами их носителей - (0,1)-матриц, получающихся заменой положительных элементов исходной матрицы на единицы. Целочисленные (ОД)-матрицы были введены в конце 50-х годов в работах Дж. Райзера, Д.Р. Фалкерсона и Д. Гейла и с тех пор интенсивно изучаются. Такие матрицы находят свое применение в задачах о потоках в сетях и используются при решении различных проблем логистики, в анализе и построении электронных схем, в задачах моделирования нейронных сетей. Комбинаторные свойства (ОД)-матриц изучались в работах Р.А. Бруалди, В.Н.Сачкова, В.Е. Тараканова, Н.Н. Кузьюрина и др.
Особое значение имеют свойства матриц, состоящих из нулей и единиц, с заданным значением сумм элементов в строках и столбцах. Матрицы такого типа содержат информацию о внутренней структуре конфигурации и соотношениях между элементами исходных множеств конфигурации. Поэтому классы данных матриц связаны с широким кругом вопросов комбинаторного анализа. Так как Дж. Райзеру принадлежит наиболее весомый вклад в изучение классов таких матриц, то их называют классами Райзера.
С классами данных матриц связано два фундаментальных вопроса:
Когда класс не пуст?
Чему равно точное число матриц в классе?
1 Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц. - М.: ТВП, 2000.
Ответом на первый вопрос служат критерии непустоты класса. Один из первых известен, как теорема Гейла-Райзера. Более сложным оказывается второй вопрос о вычислении мощности классов Райзера, так называемая проблема Райзе-ра. Данная задача была поставлена в конце 50-х гг. 20-го века, но до сих пор не имеет общего решения. За полвека изучения проблемы Райзера были получены различные оценки мощности данных классов и вычислительные формулы для определения мощности классов Райзера для некоторых частных случаев.
Поэтому, актуальной задачей является исследование свойств квадратных матриц, состоящих из нулей и единиц, с заданным значением сумм элементов в строках и столбцах и получение вычислительных формул для определения мощности классов таких матриц.
Еще одно направление исследований в данной диссертационной работе связано с задачами перечисления взвешенных путей на целочисленных решетках. Чаще всего пути на решетках определенного вида задаются при помощи однородных рекуррентных соотношений с соответствующими весовыми коэффициентами. Задачи перечисления путей на геометрических решетках и теория однородных рекуррентных соотношений активно развиваются и широко используются при решении различных проблем комбинаторного анализа и теории вероятностей и имеют большое значение при изучении дискретных структур.
Задачи перечисления взвешенных путей на решетках и случайных блужданий по узлам целочисленных решеток рассматривались О.В. Кузьминым, Т.Г Тюрневой, В.Н. Докиным, Н.А. Колокольниковой, В. Феллером, Э.В. Мон-троллом, Р. Стэнли, Ф. Спитцером и многими другими. В большинстве публикаций рассматриваются только одномерные и двумерные решетки и задачи блуждания на них. Принципиальную сложность имеет именно задача перехода с плоских схем на трехмерный случай, а дальнейшие обобщения носят скорее технический характер и делаются по аналогии.
Одним из хорошо изученных и удобных объектов для описания схем перечисления путей на решетках в трехмерном пространстве является обобщенная пирамида Паскаля. В последние десятилетия сильно расширился круг исследования
как самой пирамиды Паскаля, ее частных случаев и приложений, так и ее различных пространственных аналогов и обобщений. Возродился интерес к арифметическим, геометрическим и комбинаторным свойствам пирамид, обобщающих пирамиду Паскаля.
Идеи построения пирамид и гиперпирамид и их использования высказывались многими авторами, но одни из наиболее полных и систематических исследований, посвященных обобщенной пирамиде Паскаля, сделаны Б. А. Бондаренко2 и О.В. Кузьминым3. В работах О.В. Кузьмина, Т.Г Тюрневой, В.Д. Жукова, В.Н. Докина, Н.А. Колокольниковой исследуются вопросы перечисления путей на решетках и их связь с пирамидой Паскаля, рассматриваются суммы элементов, расположенных на диагоналях обычного и обобщенного треугольника Паскаля. В частных случаях получено множество соотношений для ряда хорошо известных комбинаторных чисел и их некоторых обобщений.
Это обуславливает актуальность построения общего метода преобразования однородных рекуррентных соотношений, определяющих взвешенные пути на решетках в и-мерном пространстве, который бы позволил систематизировать методы по работе с данными соотношениями и классифицировать различные типы комбинаторных чисел, получаемых при перечислении путей на решетках.
В данной диссертационной работе изучаются квадратные (0,1)-матрицы порядка п, в каждой строке и каждом столбце которых к единиц. Устанавливается связь задачи о вычислении мощности классов данных матриц с задачами перечисления взвешенных путей на геометрических решетках на плоскости. Предложен метод преобразования однородных рекуррентных соотношений, определяющих количество и суммарный вес взвешенных путей на решетках в и-мерном пространстве.
Основная цель работы состоит в исследовании комбинаторных свойств квадратных (ОД)-матриц с заданным значением сумм элементов в строках и столбцах и получении формул для вычисления мощности классов данных матриц,
2 Бондаренко Б. А. Обобщенные треугольники и пирамиды Паскаля, их фрактали, графы и приложения. - Ташкент:
Фан, 1990
3 Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения. - Новосибирск: Наука, 2000.
а также разработке метода преобразования однородных рекуррентных соотношений, определяющих взвешенные пути на решетках в и-мерном пространстве.
Методы исследований. В диссертации используются методы комбинаторного анализа, линейной алгебры и аналитической геометрии.
Научная новизна. В работе получены новые формулы вычисления мощности классов квадратных (ОД)-матриц с заданным значением сумм элементов в строках и столбцах. Впервые установлена связь задачи вычисления мощности классов Райзера с задачами перечисления взвешенных путей на целочисленных плоских решетках. Основные результаты, представленные в диссертационной работе, являются новыми.
Основные результаты, выносимые на защиту.
Получено выражение мощности класса Райзера через взвешенные числа Моцкина и установлена связь проблемы Райзера с задачами перечисления взвешенных путей на целочисленных плоских решетках.
Получены рекуррентные формулы вычисления мощности классов квадратных (ОД)-матриц порядка п с заданным значением сумм элементов в строках и столбцах.
Предложен метод преобразования однородных рекуррентных соотношений, определяющих суммарный вес взвешенных путей на решетках в п-мерном пространстве, и разработана пошаговая процедура реализации данного метода.
Личный вклад автора состоит в развитии комбинаторной теории матриц и получении новых формул для вычисления мощности классов квадратных матриц, состоящих из нулей и единиц, с заданными значениями строчных и столбцевых сумм, а также в развитии теории перечисления взвешенных путей на плоских целочисленных решетках и разработке метода преобразования однородных рекуррентных соотношений. Все основные результаты, включенные в диссертацию, получены автором лично.
Теоретическая и практическая значимость. Полученные в диссертации результаты могут быть использованы в практических приложениях, связанных с
применением (0,1)-матриц, в теории рекуррентных соотношений и имеют значение для развития общей теории комбинаторного анализа.
Апробация работы. Результаты были представлены на Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2006), Ежегодной научно-теоретической конференции молодых ученых Иркутского государственного университета, (Иркутск, 2006), Межвузовской зональной конференции, посвященной памяти проф. Б.А. Бельтюкова (Иркутск, 2007), XV Всероссийской школе-коллоквиуме по стохастическим методам и IX Всероссийском симпозиуме по прикладной и промышленной математике (Волгоград, 2008), а также неоднократно докладывались и обсуждались на семинаре кафедры теории вероятностей и дискретной математики Иркутского государственного университета (2006 - 2009).
Публикации. По теме диссертации опубликовано 8 работ. Основное содержание представлено в работах [1-6]. В число указанных работ входит 2 статьи [1,2] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ (редакция 2008 г.)», 3 статьи [3-5] в научных сборниках, 1 полный текст доклада [6] в материалах всероссийской конференции. Работы [1-4] выполнены в нераздельном соавторстве с научным руководителем.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы, содержащего 138 наименований. Общий объем диссертации - 87 страниц, включая 7 рисунков и 4 таблицы.
