2-мерные комплексы полностью описываемые степенями своих вершин

• Автор: Мокряков, Алексей Викторович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 105 с. : ил.

С одержание
Введение

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. Алгебраическая структура на множестве экстремальных п-вершинных /с-комплексов
Литература

Введение
К важнейшим задачам прикладной математики относятся многоин-дсксныс задачи большой размерности [1 5, 10, 14]. В работе рассматриваются некоторые модели и задачи, описываемые многоиндексными симметричными бинарными (состоящими из нулей и единиц) матрицами. Такие к-индексные матрицы (с некоторыми ограничениями на элементы) задают (локально) /с-мсрныс комплексы. Полученные в работе результаты важны для некоторых разделов прикладной математики.
В ряде литературы изучаются геометрические фигуры, путем разбиения их некоторым правильным образом на простейшие фигуры — симплексы. Тс геометрические фигуры, которые можно надлежащим образом разбить на симплексы, называются полиэдрами, а сама схема разбиения на симплексы называется комплексом [2]. Отмстим, что в болсс общем случае комплексы называются гиперграфами [4, 6, 7, 8]. Но мы придерживаемся понятия комплекса, так как для наших задач оно подходит лучше.
Так как каждый граф (без петель) [3, 22, 23, 24] (1-мерный комплекс, если этот граф не является вполне несвязным) взаимно однозначно соответствует своей матрице смежности (2-индексной симметричной матрице), то многие дискретные двухиндексные задачи и модели решаются применением методов теории графов и актуальным является распространение этих методов на многоиндсксныс задачи. Отметим, что некоторые полученные результаты имеют приложение в теории многоиндексных транспортных задач [10, 14].
Характеризация комплексов целочислеными неотрицательными векторами — это важная задача, имеющая приложения в многоиндсксных задачах большой размерности [5, 10].
В первой главе введены основные понятия: к-комплексы, реализус-

•6 Тетраэдр Ф Октаэдр
Ф Икосаэдр 91 Куб

Ранее было введено обозначение Гк(п) — множество всех п-вершинных к-комплексов. Здесь к = 2 и
Г2(п) = {б?2 = С2 (С7(п), 53 = 53 (й2) : 53 ( множество всех 2-комплсксов с множеством вершин и (п) (влючая случай 53 = 0). Легко убедится, что
|Г2(п)| = 2С".