2-мерные комплексы полностью описываемые степенями своих вершин тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Мокряков, Алексей Викторович

• Мокряков, Алексей Викторович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Мокряков, Алексей Викторович

Введение

I. ^-комплексы, многоиндексные бинарные матрицы

1.1. О реализуемости векторов в граф.

1.2. О реализуемости вектора в ^-комплекс и матрицы смежности £;-комплексов.

1.3. Подробный план исследований в следующих

главах

II. Необходимые и достаточные условия реализуемости целочисленного неотрицательного вектора в 2-комплекс

2.1. Редукционный критерий реализуемости Хакими в граф.

2.2. Обобщение критерия реализуемости Хакими.

2.3. Примеры векторов реализуемых в 2-комплексы и простейшие необходимые условия реализуемости.

2.4. 2-приводимые и редукционные векторы.

ШЭкстремальные 2-комплексы

3.1. Экстремальные графы.

3.2. 2-экстрсмальные векторы и экстремальные 2-комплсксы

3.3. Матрицы смежности экстремальных 2-комплексов.

3.4. База экстремального 2-комплекса и критерии экстремальности.

3.5. Алгебраическая структура на множестве экстремальных 2-комплсксов.

3.6. Строгая приводимость и редукционный критерий экстремальности

1У./с-мерные комплексы

4.1. Реализуемость вектора в /с-комплекс.

4.2. Совершенные и экстремальные /¿-комплексы и векторы.

4.3. к + 1-индекеные матрицы смежности и критерий экстремальности /¿-комплекса.

4.4. База экстремальных /с-комплексов и критерий экстремальности.

4.5. Алгебраическая структура на множестве экстремальных л-вершинных /с-комплексов.

Введение диссертации (часть автореферата) на тему «2-мерные комплексы полностью описываемые степенями своих вершин»

К важнейшим задачам прикладной математики относятся многоин-дсксныс задачи большой размерности [1 5, 10, 14]. В работе рассматриваются некоторые модели и задачи, описываемые многоиндексными симметричными бинарными (состоящими из нулей и единиц) матрицами. Такие /¿-индексные матрицы (с некоторыми ограничениями на элементы) задают (локально) к-мерные комплексы. Полученные в работе результаты важны для некоторых разделов прикладной математики.

В ряде литературы изучаются геометрические фигуры, путём разбиения их некоторым правильным образом на простейшие фигуры — симплексы. Тс геометрические фигуры, которые можно надлежащим образом разбить на симплексы, называются полиэдрами, а сама схема разбиения на симплексы называется комплексом [2]. Отмстим, что в более общем случае комплексы называются гиперграфами [4, 6, 7, 8]. Но мы придерживаемся понятия комплекса, так как для наших задач оно подходит лучше.

Так как каждый граф (без петель) [3, 22, 23, 24] (1-мерный комплекс, если этот граф не является вполне несвязным) взаимно однозначно соответствует своей матрице смежности (2-индексной симметричной матрице), то многие дискретные двухиндексные задачи и модели решаются применением методов теории графов и актуальным является распространение этих методов на многоиндсксныс задачи. Отметим, что некоторые полученные результаты имеют приложение в теории многоиндексных транспортных задач [10, 14].

Характеризация комплексов целочислеными неотрицательными векторами — это важная задача, имеющая приложения в многоиндексных задачах большой размерности [5, 10].

В первой главе введены основные понятия: ^-комплексы, реализусмость вектора в /с-комплекс, матрица смежности ^-комплекса. Построен ряд простейших свойств рассматриваемых объектов [11]. Приведён подробный план исследований в следующих трёх главах.

Во второй главе приведены известные редукционные критерии реализуемости вектора в 1-комплекс (граф)[16, 23]. Методы, которые применяются в 1-мерном случае распространены на 2-мерный случай и построен редукционный (алгоритмический) критерий реализуемости вектора в 2-комплекс. [11, 12, 19, 20]

Третья глава посвящена векторам, реализуемым в единственные 2-комплексы и этим 2-комплексам. В начале главы приведён известный редукционный алгоритм реализуемости вектора в единственный граф (1-комплекс) [11, 13, 14, 16, 17]. Такие векторы и их реализации называются экстремальными. Поэтому рассматриваемые объекты 2-мерного случая, также называются экстремальными. Построены необходимые и достаточные условия реализуемости вектора в экстремальный 2-комплекс [12, 21]. Применены алгебраические понятия частично упорядоченного множества и дистрибутивной решётки [9]. Приведены алгебраические свойства экстремальных графов и множеств п-вершипных экстремальных графов, которые распространены на 2-мерный случай. Введением отношения частичного порядка и двух бинарных операций на множестве всех -вершинных экстремальных 2-комплсксов построена дистрибутив-пая решётка [11, 18]. Получен ряд необходимых и достаточных условий, при которых 2-комплекс есть экстремальный.

Четвёртая глава посвящена /с-комплексам, являющимся единственными реализациями своих векторов, где /с-произвольно. Такие комплексы называются экстремальными. Основные результаты об экстремальных 2-комплексах (третья глава) распространены на многомерный случай. Построен ряд критериев, при которых к-комплекс есть экстремальный. На множестве всех тг-вершинных экстремальных /с-комплексов введён частичный порядок и определены две бинарные операции. Этим, на рассматриваемом множестве комплексов, образована алгебраическая структура дистрибутивной решётки [15].

I. /с-комплексы, многоиндексные бинарные матрицы

Список литературы диссертационного исследования кандидат физико-математических наук Мокряков, Алексей Викторович, 2010 год

1. Авондо-Бодино Дж. Применение в экономике теории графов. М.: Прогресс, 1966.

2. Александров П. С. Комбинаторная топология. М.: Гос. изд. технико-теоретической литературы, 1947.

3. Берж К. Теория графов и сё применение. М.: ИЛ, 1962.

4. Berge С., Ray-Chaudhuri D. // "Hypergraph Seminar, Ohio State University 1972 Lecture Notes in Mathematics 411 Springer-Verlag.

5. Емеличсв В. А., Ковалёв M. M., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. 342 с.

6. Зыков А. А. Гиперграфы. //Успехи математических наук, вып. 6 (180), 1972.

7. Зыков А. А. О некоторых свойствах линейных комплексов // Математический сборник, вып. 24 (2), 1949. 163-188.

8. Зыков А. А. Теория конечных графов. Новосибирск: Наука, 1969.

9. Калужнин JI. А. Введение в общую алгебру. М.: Наука, 1973.

10. Кириченко И. О., Раскин JI. Г. Многоиндексные задачи линейного программирования (теория, методы, приложения). М.: Радио и связь, 1982.

11. Mironov A. A., Mokryakov А. V., Sokolov A. A. About Realization of Integer Non-Negative Numbers Tuple into 2-Dimensional Complexes // Applied and Computational Mathematics, V. 6, N. 1, pp. 58-68, 2007.

12. Миронов А. А., Мокряков А. В. Двумерные комплексы полностью описываемые степенями вершин // Труды ИСА РАН. Динамика неоднородных систем (под редакцией член.-корр. РАН Попкова Ю. С.), 2006 №10(1). 2006 г.

13. Миронов А. А. Геометрия точек пространства Rn реализуемых, в граф //УМН, т. XXII, №6, 1977.

14. Миронов А. А., Цурков В. И. Графическое представление многоиндексных иерархических структур. //Известия РАН, Техническая кибернетика, №3, 1991.

15. Миронов А. А., Мокряков А. В., Колбанов В. М. О /с-мерных комплексах полностью описываемые степенями вершин // Труды ИСА РАН. Динамика неоднородных систем (под редакцией член.-корр. РАН Попкова 10. С.), 2006 №10(2). 2006 г.

16. Миронов А. А. О реализуемости наборов чисел в граф и свойства графов с заданным набором степеней вершин. //Тр. Гор. ГУ, 1981.

17. Миронов А. А. Равномерные обобщённые графы. //ДАН, т. 351, №4, 1996.

18. Мокряков А. В. Алгебра 2-комплексов // Научные труды международной конференции «XXXIII Гагаринские чтения», Москва, 2007.

19. Мокряков А. В. О локально двумерных комплексах полностью описываемых степенями вершин // Научные труды международной конференции «XXXI Гагаринские чтения», Москва, 2005.

20. Мокряков А. В. О реализуемости неотрицательного целочисленного вектора в двумерный комплекс // Научные труды международной конференции «XXXII Гагаринские чтения», Москва, 2006.

21. Мокряков А. В. О реализуемости целочисленных векторов в 2-комплекс // Научные труды международной конференции «XXXIII Гагаринские чтения», Москва, 2007.

22. Ope О. Теория графов. М.: Наука, 1968. 352с.

23. Хакими С. П. О реализуемости множества целых чисел степенями вершин графа. М.: Мир, Кибернетика сб. нов. сер., вып. 2, 1966.

24. Харари Ф. Теория графов. М.: УРСС, 2003. 300с.