DisCollection.ru

Авторефераты и темы диссертаций

Поступления 07.11.2009

Материалы

загрузка...

Комбинаторные свойства (0,1)-матриц и взвешенные пути на решетках

Кроткин Владислав Сергеевич, 07.11.2009

 

Кроткин Владислав Сергеевич

КОМБИНАТОРНЫЕ СВОЙСТВА (0,1)-МАТРИЦ

И ВЗВЕШЕННЫЕ ПУТИ НА РЕШЕТКАХ

01.01.09 – дискретная математика и

математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата физико-математических наук

Иркутск – 2009

Работа выполнена в ГОУ ВПО «Иркутский государственный университет»

Научный руководитель: доктор физико-математических наук, профессор Кузьмин Олег Викторович

Официальные оппоненты: доктор физико-математических наук, профессор

Павлов Юрий Леонидович

кандидат физико-математических наук, доцент

Бутин Александр Алексеевич

Ведущая организация: Омский филиал Института математики

им. С. Л. Соболева СО РАН

Защита состоится 27 ноября 2009 г. в 14-30 на заседании диссертационного совета Д.212.074.01 при Иркутском государственном университете по адресу: 664003, г. Иркутск, бульвар Гагарина, 20, Институт математики, экономики и информатики.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (г. Иркутск, бульвар Гагарина, 24).

Автореферат разослан 26 октября 2009 г.

Ученый секретарь диссертационного совета,

В.Г. Антоник

Общая характеристика работы

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

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

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

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

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

Особую роль в комбинаторике неотрицательных матриц занимают матрицы, состоящие из нулей и единиц. Это связано с тем, что многие существенные свойства неотрицательных матриц общего вида определяются свойствами их носителей – (0,1)-матриц, получающихся заменой положительных элементов исходной матрицы на единицы. Целочисленные (0,1)-матрицы были введены в конце 50-х годов в работах Дж. Райзера, Д.Р. Фалкерсона и Д. Гейла и с тех пор интенсивно изучаются. Такие матрицы находят свое применение в задачах о потоках в сетях и используются при решении различных проблем логистики, в анализе и построении электронных схем, в задачах моделирования нейронных сетей. Комбинаторные свойства (0,1)-матриц изучались в работах Р.А. Бруалди, В.Н.Сачкова,

В.Е. Тараканова, Н.Н. Кузьюрина и др.

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

С классами данных матриц связано два фундаментальных вопроса:

1. Когда класс не пуст?

2. Чему равно точное число матриц в классе?

Ответом на первый вопрос служат критерии непустоты класса. Один из первых известен, как теорема Гейла-Райзера. Более сложным оказывается второй вопрос о вычислении мощности классов Райзера, так называемая проблема Райзера. Данная задача была поставлена в конце 50-х гг. 20-го века, но до сих пор не имеет общего решения. За полвека изучения проблемы Райзера были получены различные оценки мощности данных классов и вычислительные формулы для определения мощности классов Райзера для некоторых частных случаев.

Поэтому, актуальной задачей является исследование свойств квадратных матриц, состоящих из нулей и единиц, с заданным значением сумм элементов в строках и столбцах и получение вычислительных формул для определения мощности классов таких матриц.

Еще одно направление исследований в данной диссертационной работе связано с задачами перечисления взвешенных путей на целочисленных решетках. Чаще всего пути на решетках определенного вида задаются при помощи однородных рекуррентных соотношений с соответствующими весовыми коэффициентами. Задачи перечисления путей на геометрических решетках и теория однородных рекуррентных соотношений активно развиваются и широко используются при решении различных проблем комбинаторного анализа и теории вероятностей и имеют большое значение при изучении дискретных

Задачи перечисления взвешенных путей на решетках и случайных блужданий по узлам целочисленных решеток рассматривались О.В. Кузьминым,

Т.Г Тюрневой, В.Н. Докиным, Н.А. Колокольниковой, В. Феллером, Э.В. Монтроллом, Р. Стэнли, Ф. Спитцером и многими другими. В большинстве публикаций рассматриваются только одномерные и двумерные решетки и задачи блуждания на них. Принципиальную сложность имеет именно задача перехода с плоских схем на трехмерный случай, а дальнейшие обобщения носят скорее технический характер и делаются по аналогии.

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