2-мерные комплексы полностью описываемые степенями своих вершин
К важнейшим задачам прикладной математики относятся многоин-дсксныс задачи большой размерности. В работе рассматриваются некоторые модели и задачи, описываемые многоиндексными симметричными бинарными (состоящими из нулей и единиц) матрицами. Такие /¿—индексные матрицы (с некоторыми ограничениями на элементы) задают (локально) к-мерные комплексы. Полученные в работе результаты важны для… Читать ещё >
2-мерные комплексы полностью описываемые степенями своих вершин (реферат, курсовая, диплом, контрольная)
Содержание
- 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. Строгая приводимость и редукционный критерий экстремальности
- 4. /с-мерные комплексы
- 4. 1. Реализуемость вектора в /с-комплекс
- 4. 2. Совершенные и экстремальные /с-комплексы и векторы
- 4. 3. к + 1-индекеные матрицы смежности и критерий экстремальности /с-комплекса
- 4. 4. База экстремальных /с-комплексов и критерий экстремальности
- 4. 5. Алгебраическая структура на множестве экстремальных л-вершинных /с-комплексов
К важнейшим задачам прикладной математики относятся многоин-дсксныс задачи большой размерности [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. /с-комплексы, многоиндексные бинарные матрицы
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с.