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

На правах рукописи

Мокряков Алексей Викторович

2-МЕРНЫЕ КОМПЛЕКСЫ ПОЛНОСТЬЮ ОПИСЫВАЕМЫЕ СТЕПЕНЯМИ СВОИХ ВЕРШИН

Специальность: 01.01.09 Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

" 9 ЛЕИ 2010

Москва 2010

004617066

Работа выполнена на кафедре «Прикладная математика» факультета №5 «Прикладная математика, механика и информатика» «МАТИ» — Российского государственного технологического университета имени К.Э.Циолковского.

Научный руководитель:

Доктор физико-математических наук, профессор Цурков В. И.

Официальные оппоненты:

Доктор физико-математических наук, профессор Лазарев А. А.

Кандидат физико-математических наук, профессор Фуругян М. Г.

Ведущая организация:

Учреждение Российской академии наук Институт системного анализа

Защита состоится 53 ¡2 2010г. в часов на заседании диссертационного совета Д 002.017.02 при Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: Москва, улица Вавилова, дом 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра им. А. А. Дородницына Российской академии наук

Автореферат разослан jj ноября 2010 г.

Учёный секретарь

диссертационного совета Д 002.017.02, д. ф.-м. н., профессор

ОБЩАЯ ХАРАКТЕРИСТИКА

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

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

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

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

Цели работы.

1) Построение редукционного критерия реализуемости наборов целых неотрицательных чисел в виде степеней вершин 2-комплекса, обобщающий алгоритмы Хакими и Миронова о реализуемости наборов чисел в графы.

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

3) Вывод аналитических формул, справедливость которых есть необходимое и достаточное условие реализуемости набора целых неотрицательных чисел в единственный 2-комплекс.

4) Создание алгебраической структуры - дистрибутивной решётки на тожествах п -вершинных к -комплексов, являющихся единственными реализациями наборов целых неотрицательных чисел, упорядоченных по невозрастанию.

5) Получение редукционного критерия реализуемости набора целых неотрицательных чисел для двумерных (трёхиндсксных) моделей, когда вершины комплексов принадлежат двум или трём различным множествам. Последний случай относится к задачам транспортного типа.

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

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

Апробация результатов работы. Основные результаты работы докладывались и обсуждались на трёх международных молодёжных научных конференциях: XXXI, XXXII и ХХХП1 «Гагаринские чтения».

Публикации. Основные результаты диссертации опубликованы в 7 печатных работах.

Структура работы. Диссертация состоит из введения, четырёх глав, заключения и списка литературы, содержащего 24 наименования. Общий объём работы -105 страниц.

СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЯ

Под реализуемостью в граф подразумевается следующее: набор целых неотрицательных чисел А = (а,,...,а„) реализуем в граф, если существует граф б = А) с множеством вершин и(п)=(и1,...,иГ1) такой, что степень вершины и, равна е. (degи, = а■) полагаем, что к >2 и а, > аи1 при 1 < / < к -1.

Пусть /г(о) - количество нулевых элементов набора А = (а1,...,а„) и я, <к-\-Р(6). Построим набор А' следующим образом: удалим из набора А элемент а,, у первых а1 оставшихся чисел отнимем по единице и получившийся набор чисел упорядочим по невозрастанию. Набор чисел А' называется редукционным, а процесс перехода от набора А к набору А' называется редукционным шагом. Далее, набор чисел А называется приводимым, если а,<п-1-^(0).

Теорема (Хакими). Набор целых неотрицательных чисел А = (а1,...,ап) реализуем в граф тогда и только тогда, когда он приводим и каждый набор, получившийся из набора А при последовательных редукционных шагах, также приводим.

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

Особый интерес представляют наборы целых неотрицательных чисел, упорядоченных по невозрастанию, реализуемых в единственный 2-комплекс, и реализации этих наборов.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе вводятся основные понятия: к-комплексы, реализуемость вектора в к-комплекс, матрица смежности к-комплекса. Анализируются простейшие свойства рассматриваемых объектов. Также приводится подробный план дальнейшей работы.

¿-мерный комплекс (¿-комплекс) О* = 0*(£/(и),5 =5(о4)) состоит из множества вершин ¡У(п)={и,,...,м„}, где п>к + \, и множества ¿-мерных симплексов 5 = каждый из которых будем отождествлять с

подмножеством вершин ]<к + \\си{п), задающих этот симплекс.

Очевидно, что |$|<С*+1. Введём обозначение степени вершины и, комплекса б4 = в1^/(п),8(ск)): dcgu, =||и(,и(,...,и4}б5(о':)| - количество ¿-мерных симплексов ¿ -комплекса инцидентных вершине и1.

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

Двумерный комплекс (2-комплекс) состоит из множества вершин и(п) = {их,...,ип}, где п>3, и множества 5 = 5(0) неупорядоченных троек различных вершин из и (и) (2-мерных симплексов).

Обозначим 5„ = {{и1,и],ик)'Л<1< }<к<п} - множество всех троек из V (п). Степенью вершины и. комплекса б = (и), 5) называется с^к, = =[ {(ипигик) е 5(0): V/',А} | - количество троек 2-комплекса О инцидентных вершине щ.

Обозначим 2" = {(ах,...,а„):а1 е 2,а, > 0,1 < I < п}.

Вектор Ае.2" называется реализуемым в 2-комплекс степенями вершин, если 30 = б(А) = (?((7(й),5) такой, что с^и,=а,, 1 < г < к и б(А) называется реализацией вектора А.

Заметим: если А - нулевой вектор, то его единственной реализацией является 0-мерный комплекс б(А).

Обозначим через Г(А)= {б(А)= 0([/(л),5)} - множество всех реализаций вектора А в 2-комплекс. Очевидно: если А е 21 и Г(А) Ф 0, то

я я

а) |.У(<С,3; б) "Та, =3д, где ^е2, и |.У|=<7; в) тахя. <С2,; г) Зтахя, < Уа .

Вектор В е 2" назывется вписанным в вектор А(В<А), если 6,<а, V/. Для вектора А из 2" введём обозначение множества вписанных в А векторов, реализованных в граф: М(А) = {В е 2": В < А, существует граф - реализация

вектора В}. Для А = (ах.....а„) положим А (л) = (а,,...,ап1).

В дальнейшем координаты рассматриваемых векторов будут упорядочены по невозрастанию: 2+ = {Ае2",а,+1<а(,1£<^и-1}.

Вектор А из 2+, п > 4, называется приводимым, если ап < щах УУ, /2;

^(^«»м /

для случая л = 3 приводимыми называются вектора (1,1.1) и (О ДО).

Лемма 2.1. Ясли вектор А из 2" реализуем в 2-комплекс, то А - приводим. Лемма 2.2. Пусть А - приводимый вектор из 2" где п > 4. Тогда существует А' = (а{,..., в£_[)е 2""', для которого вектор В = (^,...ДЧ) = А(1)-А' = = (я,(1) :1<г<п-1)е2""' реализуем в 2-комплекс, количество 2-мерных

которого равно а, ^ (а,а) - а,') /2 = а,- .

симплексов 1

Вектор А', построенный в лемме 1.2, называется редукционным, а переход

от вектора А е 21 к А', где п > 4, называется редукционным шагом. Если редукционный вектор А' приводим, то для него можно построить редукционный вектор (А')' = А". Пусть на к-ом редукционном шаге построен вектор А(<). Если он приводим, то можно построить редукционный вектор (А(1))' = А<<+1).

Теорема 2.1. Вектор Ае2+, где п>4, реализуем в 2-комплекс, тогда и только тогда, когда А приводим и суи^ествует приводимый редукционный вектор А', а также существует последовательность приводимых редукционных векторов А1*' на каждом к -редукционном шаге, где 1< к <п-3.

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

Для А = (а1.....ап) положим А(к) = (а,'*',...,^), где = при /<к и

а}*' = ам при к <1 < п-1. Вектор А из , л > 4, называется к - приводимым,

если ак < тах УХ /2.

1>е«(Л(*))7^ /

Лемма 2,3. Если вектор А из 2" реализуем в 2-комплекс, то А -к - приводим, при 1 <,к<п.

Лемма 2.4. Пусть А - к-приводимый вектор из 21 где п> 4. Тогда существует А' для которого вектор В = А(к)-А' =

= (з,(<) - а,': 1 < / < п -1) е реализуем в граф, количество рёбер которого равно

- 1Р'~АЬ)

Во третьей главе главное внимание уделяется наборам целых неотрицательных чисел, упорядоченных по невозрастанию, которые реализуемы в единственный 2-комплекс степенями вершин. Такие наборы чисел называется экстремальными, а сам 2-комплекс - реализация, называется экстремальным.

В данной главе построены необходимые и достаточные условия, при которых 2-комплекс - экстремален. Одно из этих условий сформулировано на языке кубических (трёхиндексных) матриц смежности 2-комплекса а другое основано на введении частичного порядка на множестве, состоящем из троек индексов.

Каждый 2-комплекс б = б(С/(«),5(0)) будем отождествлять с кубической матрицей смежности: С = (х^), где 1 < ¡,],к < п: х^ = 1 о (и, ,иу ,ик) е 5(6). Т. к. в двойной сумме участвуют две эквивалентные тройки (и.,и/,ик) и (и,,и1с, и;),то

| я я п И

==1 ^' ^

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

Понятие экстремальности вектора и 2-комплекса можно выразить с помощью кубической матрицы смежности.

Теорема 3.1. Пусть Ае2" и Г(А) Ф 0. Вектор А и комплекс <5(А) = = б(Г/(п), >?((3)) = (Хщ) являются экстремальными тогда и только тогда, когда

а) из х^ = 1 следует хря1 = 1 для Ур,д,1, где (ир,и1,и1)еЗ(о) и р < ¡',

б) из хьк - 0 следует хрц, = О для где р>1,д> ],1>к.

Другой критерий экстремальности 2-комплекса - алгебраический. Он основан на введении частичного порядка на множестве троек индексов, исследумого 2-комллекса.

Для элементов множества троек 5„ = {(и1,и1,ик): 1 </<]<к^п) установим отношение частичного порядка следующим образом: положим {ипи1,ик)<, ^ (",>"«>"<)> при причём (и¡,и1,ик)<{}1р,ич,щ), если

Теорема 3.2. 2-комплекс в = С(£/(л), 5(6)) есть экстремальный тогда и только тогда, когда приведённое выше отношение частичного порядка для элементов из индуцирует частичный порядок на 5(0).

Отметим, что эти критерии экстремальности будут распространены в четвёртой главе на к -мерный комплекс.

Пусть Аег+, где п>4, и в = С(С/(л),£((?)) -экстремальный 2-комплекс. Тогда множество троек {(и, ): 2 < / < А < и} с £((?) определено однозначно (причём количество таких троек равно Это значит, что для кубической матрицы смежности комплекса б(А) однозначно определены все элементы Хук, 1 < _/, к < п, которые задают матрицу смежности экстремального графа. Следовательно, для вектора А существует единственный редукционный вектор.

Приводимый вектор А из 1+, где п 5 4, называется строго приводимым, если существует единственный редукционный вектор А'.

Теорема 3.3. Вектор А из , где я >4, является экстремальным тогда и только тогда, когда вектор А - строго приводим, редукционный вектор А' -строго приводим, а также строго приводим каждый редукционный вектор А(*\ построенный на каждом к -редукционном шаге, где 1 < к < п -3.

Рассмотрим строго приводимый вектор А е . Из строгой приводимости следует, что разность векторов В = А(1)-А' задаёт единственный 2-комплекс

«-1 / (который, конечно, экстремален), причём У¿>( = щах УХ /2 = а{.

Построим аналитические формулы, зависящие от координат вектора А, определяющие строгую приводимость указанного вектора. Для этого приведём одно из описаний (экстремального) вектора, реализуемого в (единственный) граф степенями вершин.

Пусть / > /2 >...>/; - все различные координаты вектора Т) = (с1^...,с1„) из где и > 2, и ^ - количество координат вектора И, равных /4, 1 < & < 5. Не ограничивая общности будем предполагать, что ¿п=/г> 0. Вектор О реализуем

в единственный граф тогда и только тогда, когда /к = -Д, 1<А:<5, где

(=1

Д = 1 при 1<£<]$/2[ и Д = 0 при /2[<Аг^лг (если аег и <з>0,то ]а/2[=а/2 при а/2ег и ]а/2[=(а+1)/2 при а!2^1).

Вектор А из Х\ задаёт функцию /(*)=а1, г -1 < л < ¡', 1 < г < и. Рассмотрим уравнение /(х) =х~1. Если оно имеет решение к*, то очевидно, что к* е Z и к*> 1. В случае, когда к* = п-\ или уравнение не имеет решения, имеет место

ая >п-2. В этом случае вектор (п-2,...,и-2) из 2.* вписан в вектор А(1) и определяет единственный (полный) граф с и-1 вершинами, который экстремален и соответствует /к при з = 1.

Лемма 3.1. Пусть ке2* и ап>п-2. Вектор А строго приводим тогда и только тогда, когда а, = СгпЛ.

Рассмотрим нетривиальный случай к*<п-2 (то есть а„ < и-3) и > > <р2>...> /р, - все различные координаты вектора А(1)=(а2,...,а„), причём ^ -количество координат, равных <рк, 1 <к<,$. Найдётся такое / е 2, что ак. = (р[. Будем строить вектор И = (д.г.....с!„), реализуемый в единственный граф. Для

этого нам понадобятся значения <рк и у/к при / < к < я. Пусть к*- 1-^<р1><р1.

ыт

Положим &+1=0, и 1<^<5-< + 1.

Обозначив Рк - у/к при ? +1 < к < й, положим

!-к к к А

м у=о я>

=

а„ £>, + 1 <Ип.

¡л

Из этого следует, что вектор D = (d2,...,dj есть экстремальный.

Лемма 3.2. Если вектор D = (d2,...,dn) вписан в вектор A(l) = (а,.....ап)

и и

(D й А(1)), то имеет место Il^i ~ ^тм^^е,-, где Е = (е2.....е„).

Введём ещё один параметр Н = + £ (ft-/_ ft-м )' X / - **

Лемма 3.3 .Для вектора Э из (4) имеет место Н = 2.

ыг /

Определим строгую приводимость вектора вышеприведёнными формулами. Из лемм 3.1. - 3.3 следует

Теорема 3.4. Пусть А б 2\, где п >4, и ап> 0. Вектор А есть строго

приводимый тогда и только тогда, когда а1 = при ал > и - 2 или справедливы

соотношения и а, =Н при ал <л-3.

Теорема 3.5. Если А из где п > 4, является строго приводимым, то для единственного редукционного вектора А' = (а2,...,а|,) имеет место

, \а,-п + 2, 2 < г < л, где ап £л-2,

а1

\a¡-d¡y 2</<п, где ап<п-Ъ. В четвёртой главе. Рассматриваются к -мерные комплексы (к -комплексы) в которых каждый т -мерный симплекс есть грань т +1 -мерного симплекса, где 1 < т < к -1 (изолированные 0-мерные симплексы - вершины допускаются).

Вектор А е называется реализуемым в к -комплекс степенями вершин, если 3б* = б*(А) = в"(1Г(п),5) такой, что ¿(¡ёы, = а,, 1 < I < п, и в*(А) называется реализацией вектора А.

Заметим: если А = 0 - нулевой п -координатный вектор, то его единственной реализацией является 0-мерный комплекс, который, в виде исключения, отнесём к классу к -комплексов: О*(О) = О*(Г/(п),5=0 ). Пусть А еЯ". Обозначим через Г* (А) = {б* (А) = бк(и(п),Б)} - множество всех А:-комплексов - реализаций

п

вектора А. Легко видеть, что при Г* (А) * 0 имеет место: а) ^ а, ={к + 1)д, где

м

? 6 г , и 151= о; б) тах а, <С*:'; в) (/с + 1)таха,. < У а,.

Если А е 21 и | Г'(А) |= 1, то вектор А называется совершенным. При этом

единственный комплекс б* (А) = С* (Ц(и), £) - реализация вектора А называется совершенным к -комплексом.

Для 0*([/(л)>5) и V си(п) ¿-комплекс С1 (V,£') называется подкомплексом Ок(и(п),8) порождённым множеством вершин К, если каждый симплекс из 5 с вершинами только из V - симплекс множества 5'.

Свойство ¿-комплекса быть совершенным является наследственным для всех подкомплексов, порождённых своими вершинами.

Теорема 4.1. Пусть йк = Ок(и(п),Б) - совершенный к-комплекс. Тогда любой подкомплекс б*, порождённый множеством вершин Vс ¡У(и), также есть совершенный.

Наследственность свойства являться совершенным ¿ -комплексом позволяет доказывать важные свойства совершенных ¿ -комплексов по индукции.

Если А е и |Г*(А)|=1, то вектор А - экстремальный. Единственная реализация 0'(а) вектора А -экстремальный ¿-комплекс.

Очевидно, что совершенные вектор а и комплекс С*(а) есть экстремальные, если а е Из теоремы 4.1 следует

Теорема 4.2. Пусть в* = 0*(Щ")>5)> где п>к + 2, - экстремальный комплекс. Тогда любой подкомплекс ¿ -комплекса С*, порождённый вершинами подкомплекса, также есть экстремальный ¿ -комплекс.

Каждый ¿-комплекс (3* = б* (¡[/(л ),£((?*)) будем отождествлять с ¿ + 1-индексной матрицей смежности, состоящей из 0 и 1: <7* = (х^ ), где 1<11 <п V/, 1 < ]<к + \, причём = 1 тогда и только тогда, когда симплекс

(к, : 1 < } < к+1}е 5(о*). Легко видеть, что с^ и, , 1 ^Ип,

так как каждый симплекс {и,,и,,...,^} просчитывается к\ раз.

Понятие экстремальности можно выразить с помощью к +1 -индексной матрицы смежности.

Теорема 4.3. Пусть Ае2° и Г* (А) Вектор А и к-комплекс б*(А)= = )= Ск(и(п\8) являются экстремальными тогда и только тогда, когда

а) из равенства = 1 следует равенство х ^ = 1, где т) < V/, 1 < у < ¿ +1 и т]Фт1 при

б) из равенства х^ =0 следует равенство хщ „ы -0, где > V/, 1< }<к +1.

А: -комплекс полный, если каждые его к +1 вершина образуют симплекс.

Полный к -комплекс имеет следующие свойства. Пусть а б . Тогда:

а) если О1 (а) = б* ([/(«), 5(6')) есть полный, то а) и а - экстремальны;

б) к -комплекс С1 (а) есть полный, тогда и только тогда, когда а, = с*.,, V/;

в) к -комплекс вк - Ок(£/(л),5(ск)) есть полный о |ф*)| = С„1+1.

Через дУ* обозначим множество всех к -мерных симплексов полного к -комплекса с п вершинами. Очевидно, что = С**1.

Пусть б* = б* (¿/(и), $((?*)). Дополнением комплекса б* (до полного к-комплекса) называется комплекс йк = 0*(1/(л),5*

Теорема 4.4. Дополнение к совершенному к -комплексу есть совершенный к -комплекс.

Теорема 4.5. Для совершенных вектора Ае2" и к-комплекса О* (А) = (*(.../,«) гшеет место: а) если ар=а1- то б) если ар>ая,

то из х,,,..^ = 1 следует хр,^-\; в) если ар>ащ, то из хрЦ=0 следует

Пусть п, к е 2, & > 1. Для множества индексов 1п = {/ е 2:1 < I < п] введём обозначение к +1 -индексных упорядоченных подмножеств множества /„: п, < У/}. Определим на частичный порядок: положим ]<к+\)> (т]: 1 < ]<к + \), если ¡/ > т, V/, и (¡;: 1 < j<k + í)> >(т1\1<]<к + \) при : 1 < < £ +1)> (ти,: 1 < ] <к + \) и (/, :\<.]<к + \)* Ф (т] :1<]<к + \).

Построим конструкцию, позволяющую алгебраическим способом описать экстремальный ¿-комплекс. Для б* = (х, ,^ ) = О* (£/(«), 5)

.....= 1}= Ы,* :Ц, +

Пусть вк =С:{и(п),з(о1])-(х^и) - экстремальный £ -комплекс. Подмножество индексов (6*)= {(;',,...,гН1)} из /* называется базой для комплекса О4, если выполняются следующие условия:

а) для разных элементов ({.....«1+1) и (т,.....тм ) из 7' ((?*) отношение порядка в /* не определено;

б) для .....'ыХИ- где (/,,...,Э(т1,..,тм)е7„'(о'),чТО

Подмножество индексов (тя,,...,«^) из /'(б*) (то есть = ]) называ-

ется максимальным, если =0, V (/'1,...,г'м)> (гИр...,»!^).

Теорема 4.6. Пусть йк ~ б* ({/(л ),■?((?*)) - экстремальный к-комплекс. Тогда 1к(ок)= {(¡'¡,...,4+| )е /,((?): (¡',.....;1+1) - максимальное подмно-во индексов }.

Теорема 4.7. Любой экстремальный к-комплекс <?*=0'({/(п),5(о*))= = А)=(х, имеет единственную базу и эта база есть 7* (б*).

Теорема 4.8. Пусть 7„* : любые пары различных под-

множеств индексов не связаны отношением порядка из /'}. Тогда /„* - есть база некоторого экстремального к -комплекса.

Из теоремы 4.7 и теоремы 4.8 следует

Теорема 4.9. к-комплекс вк, является экстремальным тогда и только тогда, когда имеет базу.

На множестве всех к -комплексов введём частичный порядок и две бинарные операции.

Для вк = С*({/(п),5') и вк = 0*(с/(и),Г), где 5" положим:

а) (?/<(7* о 5'сГ;

б) операция объединение: вк = С*, где = б* ({/(«), 5" II5");

в) операция пересечение: вк П б* = б*, где вк = в* {Щп), 5' Г) 5').

Легко видеть: если йк = ) и й' = 41)- п -вершинные комплексы, то

а) С* < С2* о ^^V(/1,...,íi+1)e/* и Э Ц.....тм)е1к, что

б) в! и С?г> = б*, где ^ = (тах(^... ^, х"^));

в) О,4 П 01 = вк, где О* = (4;.^ - ))•

Очевидно, что на множестве всех и -вершинных к -комплексов выполняется закон дистрибутивности:

Через ТУ* обозначим множество всех экстремальных к -комплексов с множеством вершин и(п). Введённые выше отношение частичного порядка и бинарные операции задают на ]¥* алгебраическую структуру дистрибутивной решётки.

Лемма 4.1. Пусть б* = С* (Щп), 5'), С* = С2 (£/(л), 5*) е ^. Тогда

Лемма 4.2. #>>шь С7* = 0*(С/(л),5"), (?2* = (7г*(г7(п),5")е ЦтЦ. Тогда

Следствием лемм 1 и 2 есть

Теорема 4.10. Множество экстремальных п -вершинных к -комплексов IV* с отношением частичного порядка и бинарными операциями объединения и пересечения есть дистрибутивная решётка.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Получен редукционный критерий, реализуемости в единственный 2-комплекс.

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

4. Выведен алгебраический критерий реализуемости в единственный п -вершинный к -комплекс, основанный на введении частичного порядка, на множестве из С*-1 элементов, каждый из которых - это к-1 различных индексов множества индексов {1,...,и}.

5. На множестве л-вершинных ¿-комплексов, являющихся единственными реализациями наборов целых неотрицательных чисел, упорядоченных по невозрастанию, построены две бинарные операции - «объединение» и «пересечение» и создана алгебраическая структура - дистрибутивная решётка.

Основное содержание работы изложено в следующих публикациях:

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

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

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

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

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

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

7. 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.

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25.09.2000 г. Подписано в печать 16.11.2010 Тираж 100 экз. Усл. п.л. 1,0 Печать авторефератов (495)730-47-74,778-45-60

Введение

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].

В первой главе введены основные понятия: ^-комплексы, реализусмость вектора в /с-комплекс, матрица смежности ^-комплекса. Построен ряд простейших свойств рассматриваемых объектов [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с.