авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

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

Мокряков Алексей Викторович 2-МЕРНЫЕ КОМПЛЕКСЫ ПОЛНОСТЬЮ ОПИСЫВАЕМЫЕ СТЕПЕНЯМИ СВОИХ ВЕРШИН Специальность: 01.01.09 Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Москва 2010

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

Научный консультант:

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

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

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

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

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

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

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

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

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

Учёный секретарь диссертационного совета Д 002.017.02, д. ф.-м. н., профессор В. В. Рязанов ОБЩАЯ ХАРАКТЕРИСТИКА Актуальность темы. К рассматриваемым многоиндексным моделям и зада чам большой размерности применяются методы теории графов и некоторые поня тия из комбинаторной топологии. Отметим, что в некоторых публикациях рассма триваемые объекты называются гиперграфами. Но мы придерживаемся здесь по нятия комплекса, так как гиперграф – это более общее понятие.

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

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

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

Цели работы.

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

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

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

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

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

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

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



Апробация результатов работы. Основные результаты работы докладыва лись и обсуждались на трёх международных молодёжных научных конференциях:

XXXI, XXXII и XXXIII «Гагаринские чтения».

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

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

СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЯ Под реализуемостью в граф подразумевается следующее: набор целых неотрицательных чисел A ai,..., an реализуем в граф, если существует граф G GA с множеством вершин U n u1,..., u n такой, что степень вершины ui равна ai ( deg ui ai ) полагаем, что k 2 и ai ai 1 при 1 i k 1.

Пусть F 0 – количество нулевых элементов набора A ai,..., an и a1 k 1 F 0. Построим набор A следующим образом: удалим из набора A элемент a1, у первых a1 оставшихся чисел отнимем по единице и получившийся набор чисел упорядочим по невозрастанию. Набор чисел A называется редукционным, а процесс перехода от набора A к набору A называется редукционным шагом. Далее, набор чисел A называется приводимым, если a1 n 1 F 0.

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





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

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

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

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

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

k -мерный комплекс ( k -комплекс) G k G k U n, S S G k состоит из U n u1,..., u n, где n k 1, и множества k -мерных множества вершин S S Gk, симплексов каждый из которых будем отождествлять с u : 1 j k 1 U n, задающих этот симплекс.

подмножеством вершин ij Очевидно, что S C n 1. Введём обозначение степени вершины ul комплекса k G k G k U n, S G k : deg ul ul, ui1,..., uik S G k – количество k -мерных симплексов k -комплекса G k инцидентных вершине ul.

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

Двумерный комплекс (2-комплекс) состоит из множества вершин U (n) = {u1,..., u n }, где n 3, и множества S = S (G ) неупорядоченных троек различных вершин из U (n) (2-мерных симплексов).

Обозначим S n = {(ui,u j,u k ) : 1 i j k n} – множество всех троек из U (n).

G = G (U (n), S ) ui deg ui Степенью вершины комплекса называется | {(ui, u j, uk ) S (G ) : j, k} | – количество троек 2-комплекса G инцидентных вершине ui.

n Обозначим Z = {(a1,..., an ) : ai Z, ai 0,1 i n}.

n Вектор A Z называется реализуемым в 2-комплекс степенями вершин, если G = G ( A ) = G (U (n), S ) такой, что deg ui = ai, 1 i n и G (A) называется реализацией вектора A.

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

Обозначим через ( A) = {G ( A ) = G (U (n), S )} – множество всех реализаций n вектора A в 2-комплекс. Очевидно: если A Z и (A), то n n a 3q, где q Z, и | S |= q ;

в) max ai C n1 ;

г) 3 max ai ai.

а) | S | Cn ;

б) i 1i n 1i n i1 i n Вектор B Z назывется вписанным в вектор A ( B A ), если bi ai i.

n Для вектора A из Z введём обозначение множества вписанных в A векторов, n реализованных в граф: M ( A ) = {B Z : B A, существует граф – реализация вектора B}. Для A = (a1,..., an ) положим A (n) = a1,..., an1.

В дальнейшем координаты рассматриваемых векторов будут упорядочены n n по невозрастанию: Z = {A Z, ai 1 ai,1 i n 1}.

n n d Вектор A из Z, n 4, называется приводимым, если an max 2;

i DM ( A ( n )) i= для случая n = 3 приводимыми называются вектора (1,1,1) и (0,0,0).

n Лемма 2.1. Если вектор A из Z реализуем в 2-комплекс, то A – приводим.

n Лемма 2.2. Пусть A – приводимый вектор из Z где n 4. Тогда сущест B b1,...,bn1 A1 A A ' a1,..., a 1 Z 1, для которого вектор n вует n ai(1) ai : 1 i n 1 Z n реализуем в 2-комплекс, количество 2-мерных n1 симплексов которого равно ai ai(1) ai 2 ai.

i1 Вектор A ', построенный в лемме 1.2, называется редукционным, а переход n от вектора A Z к A ', где n 4, называется редукционным шагом. Если редукционный вектор A ' приводим, то для него можно построить редукционный вектор ( A) = A. Пусть на k -ом редукционном шаге построен вектор A (k ). Если он приводим, то можно построить редукционный вектор ( A ( k ) ) = A ( k 1).

n Теорема 2.1. Вектор A Z, где n 4, реализуем в 2-комплекс, тогда и только тогда, когда A приводим и существует приводимый редукционный вектор A ', а также существует последовательность приводимых редукционных векторов A (k ) на каждом k -редукционном шаге, где 1 k n 3.

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

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

Для A = (a1,..., an ) положим A (k ) = a1k,..., ank1, где aik ai при i k и n aik ai 1 при k i n 1. Вектор A из Z, n 4, называется k приводимым, n d если ak max 2.

i DM ( A ( k )) i = n Лемма 2.3. Если вектор A из Z реализуем в 2-комплекс, то A – k приводим, при 1 k n.

n Лемма 2.4. Пусть A – k приводимый вектор из Z где n 4. Тогда B Ak A A ' a1,..., a 1 Z 1, n существует для которого вектор n ai( k ) ai : 1 i n 1 Z 1 реализуем в граф, количество рёбер которого равно n n1 ai ai( k ) ai 2 ai.

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

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

Каждый 2-комплекс G = G (U (n), S (G )) будем отождествлять с кубической матрицей смежности: G = ( xijk ), где 1 i, j, k n : xijk = 1 (ui,u j,uk ) S (G ). Т. к. в двойной сумме участвуют две эквивалентные тройки (ui,u j,uk ) и (ui,uk,u j ), то n j 1n n deg ui = xijk = xijk, 1 i n.

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

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

n Теорема 3.1. Пусть A Z и (A). Вектор A и комплекс G (A ) G (U (n), S (G )) ( xijk ) являются экстремальными тогда и только тогда, когда а) из xijk = 1 следует x pql = 1 для p,q,l, где u p, u q, ul S G и p i, q j, l k ;

б) из xijk = 0 следует x pql = 0 для p,q,l, где p i, q j, l k.

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

Для элементов множества троек S n = {(ui,u j,u k ) : 1 i j k n} установим u, u, u отношение частичного порядка следующим образом: положим i j k u p, uq, ul, при u, u, u u, u, u, если i p, j q, k l, причём i j k p q l u, u, u u, u q, ul.

i j k p Теорема 3.2. 2-комплекс G = G (U (n), S (G )) есть экстремальный тогда и только тогда, когда приведённое выше отношение частичного порядка для эле ментов из S n индуцирует частичный порядок на S (G ).

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

n Пусть A Z, где n 4, и G = G (U (n), S (G )) – экстремальный 2-комплекс.

Тогда множество троек {(u1,u j,u k ) : 2 j k n} S (G ) определено однозначно (причём количество таких троек равно a1 ). Это значит, что для кубической матри цы смежности комплекса G (A) однозначно определены все элементы x1 jk, 1 j, k n, которые задают матрицу смежности экстремального графа. Следова тельно, для вектора A существует единственный редукционный вектор.

n Приводимый вектор A из Z, где n 4, называется строго приводимым, если существует единственный редукционный вектор A '.

n Теорема 3.3. Вектор A из Z, где n 4, является экстремальным тогда и только тогда, когда вектор A – строго приводим, редукционный вектор A ' – строго приводим, а также строго приводим каждый редукционный вектор A (k ), построенный на каждом k -редукционном шаге, где 1 k n 3.

n Рассмотрим строго приводимый вектор A Z. Из строгой приводимости следует, что разность векторов B A1 A задаёт единственный 2-комплекс n 1 n bi max d 2 a1.

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

Пусть f1 f 2... f s – все различные координаты вектора D d1,..., d n из n Z, где n 2, и Fk – количество координат вектора D, равных f k, 1 k s. Не ограничивая общности будем предполагать, что d n f s 0. Вектор D реализуем s k F, 1 k s, где в единственный граф тогда и только тогда, когда f k i i 1 при 1 k ]s / 2[ и 0 при ]s / 2[ k s (если a Z и a 0, то ]a / 2[ a / при a / 2 Z и ]a / 2[ (a 1) / 2 при a / 2 Z ).

n Вектор A из Z задаёт функцию f x ai, i 1 x i, 1 i n. Рассмот рим уравнение f x x 1. Если оно имеет решение k *, то очевидно, что k * Z и k * 1. В случае, когда k * n 1 или уравнение не имеет решения, имеет место n an n 2. В этом случае вектор n 2,..., n 2 из Z вписан в вектор A 1 и оп ределяет единственный (полный) граф с n 1 вершинами, который экстремален и соответствует f k при s 1.

n Лемма 3.1. Пусть A Z и an n 2. Вектор A строго приводим тогда и только тогда, когда a1 Cn21.

Рассмотрим нетривиальный случай k * n 2 (то есть an n 3 ) и 2... s – все различные координаты вектора A 1 a2,..., an, причём k – количество координат, равных k, 1 k s. Найдётся такое t Z, что ak * t.

Будем строить вектор D d 2,..., d n, реализуемый в единственный граф. Для s t.

этого нам понадобятся значения k и k при t k s. Пусть k * 1 i i t Положим s 1 0, F0 1 и Fk s k 1 s k 2, 1 k s t 1.

Обозначив Fk k при t 1 k s, положим s k k k F j 1, F j 1 i F j 1, 0 k s t 1, j 1 j 0 j di s t a, F j 1 i n.

i j Из этого следует, что вектор D d 2,..., d n есть экстремальный.

Лемма 3.2. Если вектор D d 2,..., d n вписан в вектор A 1 a2,..., an n n D A(1), то имеет место di Emax1 ei, где E e2,..., en.

M A i 2 i st si Введём ещё один параметр H C k2*1 s i si 1 F j k *.

j 0 i n Лемма 3.3. Для вектора D из (4) имеет место H d i 2.

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

Из лемм 3.1. – 3.3 следует n Теорема 3.4. Пусть A Z, где n 4, и an 0. Вектор A есть строго приводимый тогда и только тогда, когда a1 Cn21 при an n 2 или справедливы соотношения D A и a1 H при an n 3.

n Теорема 3.5. Если A из Z, где n 4, является строго приводимым, то для единственного редукционного вектора A a,..., a имеет место 2 n ai n 2, 2 i n, где an n 2, ai ai d i, 2 i n, где an n 3.

В четвёртой главе. Рассматриваются k -мерные комплексы ( k -комплексы) в которых каждый m -мерный симплекс есть грань m 1 -мерного симплекса, где 1 m k 1 (изолированные 0-мерные симплексы – вершины допускаются).

n Вектор A Z называется реализуемым в k -комплекс степенями вершин, если G k = G k ( A) = G k (U (n), S ) такой, что deg ui = ai, 1 i n, и G k (A) называется реализацией вектора A.

Заметим: если A 0 – нулевой n -координатный вектор, то его единственной реализацией является 0-мерный комплекс, который, в виде исключения, отнесём к.

классу k -комплексов: G k ( 0 ) G k U n, S n Пусть A Z. Обозначим через k ( A) = {G k ( A) = G k (U (n), S )} – множество всех k -комплексов – реализаций n вектора A. Легко видеть, что при k (A) имеет место: а) a (k 1)q, где i i n q Z, и | S |= q ;

б) max ai Cnk1 ;

в) (k 1) max ai ai.

1i n 1 i n i Если A Z и | k ( A) |= 1, то вектор A называется совершенным. При этом n единственный комплекс G k ( A) = G k (U (n), S ) – реализация вектора A называется совершенным k -комплексом.

Для G k (U (n), S ) и V U n k -комплекс G k (V, S ) называется подкомпле ксом G k (U (n), S ) порождённым множеством вершин V, если каждый симплекс из S с вершинами только из V - симплекс множества S.

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

Теорема 4.1. Пусть G k = G k (U (n), S ) – совершенный k -комплекс. Тогда любой подкомплекс G1k, порождённый множеством вершин V U n, также есть совершенный.

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

Если A Z n и | k ( A) |= 1, то вектор A - экстремальный. Единственная реализация G k A вектора A - экстремальный k -комплекс.

Очевидно, что совершенные вектор A и комплекс G k A есть экстремаль ные, если A Z n. Из теоремы 4.1 следует Теорема 4.2. Пусть G k = G k (U (n), S ), где n k 2, – экстремальный комплекс. Тогда любой подкомплекс k -комплекса G k, порождённый вершинами подкомплекса, также есть экстремальный k -комплекс.

Каждый k -комплекс G k G k U n, S G k будем отождествлять с k 1 индексной матрицей смежности, состоящей из 0 и 1: G k xi1...ik 1, где 1 i j n j, 1 j k 1, причём xi1...ik 1 1 тогда и только тогда, когда симплекс 1n n u : 1 j k 1 S G k. Легко видеть, что deg ul... xl i1...ik, 1 l n, ij k! i1 1 ik так как каждый симплекс ul, ui,..., u k просчитывается k! раз.

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

Теорема 4.3. Пусть A Z n и k (A). Вектор A и k -комплекс G k A G U n, S являются экстремальными тогда и только тогда, когда k xi1...ik а) из равенства xi1...ik 1 1 следует равенство xm1... mk 1 1, где m j i j j, 1 j k 1 и m j ml при j l ;

б) из равенства xi1...ik 1 0 следует равенство xm1... mk 1 0, где m j i j j, 1 j k 1.

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

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

есть полный, то G A и A – экстремальны;

а) если G k A = G k U (n), S G k k б) k -комплекс G k A есть полный, тогда и только тогда, когда ai Cnk1, i ;

есть полный S G C k k в) k -комплекс G k = G k U (n), S G k.

n k Через S n обозначим множество всех k -мерных симплексов полного k комплекса с n вершинами. Очевидно, что S n C n 1.

k k Пусть G k G k U (n), S G k. Дополнением комплекса G k (до полного k комплекса) называется комплекс G k G k U (n), S n \ S G k.

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

A Z n Для совершенных вектора и k -комплекса Теорема 4.5.

G k A xi1...ik 1 имеет место: а) если a p aq, то x p i1...ik xq i1...ik ;

б) если a p aq, то из xq i1...ik 1 следует x p i1...ik 1 ;

в) если a p aq, то из x p i1...ik 0 следует xq i1...ik 0.

Пусть n, k Z, k 1. Для множества индексов I n i Z : 1 i n введём In :

обозначение k 1 -индексных упорядоченных подмножеств множества i j i j 1 j. Определим на I n частичный порядок:

I nk i1,..., ik 1 : 1 i j n, k положим i j : 1 j k 1 m j : 1 j k 1, если i j m j j, и i j : 1 j k m j : 1 j k 1 при i : 1 j k 1 m j : 1 j k 1 и i : 1 j k j j m j : 1 j k 1.

Построим конструкцию, позволяющую алгебраическим способом описать экстремальный k -комплекс. Для G k xi1...ik 1 G k U n, S 1 i,..., i I : : 1 j k 1 S.

I G i,..., i I : x k k k k u 1 k 1 n ij 1 k 1 n i1...ik n Пусть G = G U (n), S G x – экстремальный k -комплекс. Подмно k k k i1...ik жество индексов I G i,..., i из I называется базой для комплекса G, k k k k n 1 k 1 n если выполняются следующие условия:

а) для разных элементов i1,..., ik 1 и m1,..., mk 1 из I nk G k отношение поряд k ка в I n не определено;

б) для i1,..., ik 1 I n G k, где i1,...,ik 1 I nk G k, m1,...,mk 1 I nk G k, что k i1,..., ik 1 m1,..., mk 1.

Подмножество индексов m1,..., mk 1 из I n G k (то есть xm1... mk 1 1 ) называ k ется максимальным, если xi1...ik 1 0, i1,..., ik 1 m1,..., mk 1.

Теорема 4.6. Пусть G k = G k U (n), S G k – экстремальный k -комплекс.

Тогда I nk G k i1,..., ik 1 I n G : i1,..., ik 1 – максимальное подмно-во индексов.

Теорема 4.7. Любой экстремальный k -комплекс G k G k U (n), S G k G k A xi1...i k 1 имеет единственную базу и эта база есть I nk G k.

~ I nk i1,..., ik 1 I n : любые пары различных под k Теорема 4.8. Пусть ~ множеств индексов не связаны отношением порядка из I n. Тогда I nk – есть k база некоторого экстремального k -комплекса.

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

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

Для G1k = G1k U (n), S и G2 = G2 U (n), S, где S S положим:

k k а) G1k G2k S S ;

б) операция объединение: G1k G2 G3k, где G3k = G3k U (n), S S ;

k в) операция пересечение: G1k G2 G3k, где G3k = G3k U (n), S S.

k Легко видеть: если G1k xi1...ik 1 и G2 xi1...ik 1 – n -вершинные комплексы, то k i1,..., ik 1 I nk и m1,..., mk 1 I n, что а) G1k G2k k xi1...ik 1 xi1...ik x 1...mk 1 x 1...mk 1 ;

m m б) G1k G2 G3k, где G3k = max xi1...ik 1, xi1...ik 1 ;

k = min x.

в) G1k G2 G3k, где G3k k, xi1...ik i1...ik Очевидно, что на множестве всех n -вершинных k -комплексов выполняется закон дистрибутивности:

G k G2 G3k G1k G3k G1k G2 и G1k G2 G3k G1k G3k G1k G2.

k k k k Через Wnk обозначим множество всех экстремальных k -комплексов с мно жеством вершин U n. Введённые выше отношение частичного порядка и бинар ные операции задают на Wnk алгебраическую структуру дистрибутивной решётки.

G1k = G1k U (n), S, G2 = G2 U (n), S Wnk.

k k Пусть Тогда Лемма 4.1.

G1k G2 Wnk.

k G1k = G1k U (n), S, G2 = G2 U (n), S Wnk.

k k Пусть Тогда Лемма 4.2.

G1k G2 Wnk.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Построен редукционный критерий реализуемости набора целых неотрицательных чисел в виде степеней вершин 2-комплекса.

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

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

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

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

Основное содержание работы

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

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

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

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

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

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

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

7. Mironov A. A., Mokryakov A. 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.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.