Гиперграфы: введение в 2-мерные комплексы
Гиперграфы и 2-мерные комплексы: введение в многоиндексные задачи
Данное методическое пособие посвящено изучению гиперграфов и, в частности, 2-мерных комплексов, рассматриваемых в контексте многоиндексных задач большой размерности. Работа фокусируется на анализе и решении задач, связанных с реализацией целочисленных неотрицательных векторов в k-комплексы, что имеет важное значение в прикладной математике.
Основные понятия и определения
Введение начинается с определения k-комплексов и многоиндексных бинарных матриц, которые служат математическим аппаратом для описания рассматриваемых моделей. Авторы вводят понятие реализуемости целочисленного неотрицательного вектора в граф, где степень вершины графа соответствует координате вектора. Рассматриваются необходимые условия реализуемости, а также проводится аналогия с многомерным случаем, вводя понятие реализуемости вектора в k-комплекс. Особое внимание уделяется матрицам смежности k-комплексов, являющимся (k+1)-индексными бинарными матрицами, которые однозначно соответствуют k-комплексам.
Редукционный критерий реализуемости Хакими и его обобщение
Центральным элементом работы является редукционный критерий реализуемости векторов в граф, предложенный Хакими. Этот критерий основан на понятиях приводимости вектора и редукционного вектора. Приводимость вектора является необходимым условием реализуемости, а редукционные шаги позволяют последовательно упрощать задачу, сводя ее к анализу более простых векторов. Авторы рассматривают алгоритм Хакими, который позволяет построить граф-реализацию вектора, если он реализуем, или установить нереализуемость, если это не так.
Далее представлено обобщение критерия Хакими, которое позволяет строить большее количество различных графов-реализаций. Это достигается за счет введения понятия p-редукционного вектора и построения старших p-редукционных векторов на каждом шаге. Обобщенный алгоритм предоставляет большую гибкость в построении графов, но не охватывает все возможные реализации.
2-мерные комплексы и редукционный критерий реализуемости
Основной акцент делается на 2-мерных комплексах. Вводятся понятия p-среза матрицы смежности, что позволяет применять методы теории графов для исследования 2-комплексов. Рассматриваются примеры 2-комплексов, включая известные правильные многогранники.
Вводится понятие 2-приводимости вектора, которое является ключевым для разработки редукционного критерия реализуемости в 2-комплекс. 2-приводимость означает, что для вектора существует граф, в котором степени вершин удовлетворяют определенным условиям. На основе этого понятия строится алгоритм, позволяющий определить, реализуем ли вектор в 2-комплекс, и, в случае положительного ответа, построить его реализацию. Алгоритм включает в себя последовательное применение редукционных шагов и построение старших 2-редукционных векторов.
В заключение формулируется теорема, содержащая необходимые и достаточные условия реализуемости вектора в 2-комплекс, основанная на понятии 2-приводимости и редукционных векторах. Эта теорема является основным результатом работы и предоставляет эффективный инструмент для решения задач, связанных с многоиндексными задачами большой размерности.
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 01.03.04: Прикладная математика
- ВО - Магистратура
- 01.04.01: Математика
- 01.04.02: Прикладная математика и информатика
Костиков Ю. А., Мокряков А. В., Павлов В. Ю., Романенков А. М. Гиперграфы: введение в 2-мерные комплексы Методическое пособие для студентов Москва
Содержание Введение 3 I. k-комплексы, многоиндексные бинарные матрицы 4 1.1. О реализуемости векторов в граф . . . . . . . . . . . . . . 4 1.2. О реализуемости вектора в k-комплекс и матрицы смежности k-комплексов . . . . . . . . . . . . . . . . . . . . . . . 6 II. Необходимые и достаточные условия реализуемости целочисленного неотрицательного вектора в 2-комплекс 15 2.1. Редукционный критерий реализуемости Хакими в граф. . 15 2.2. Обобщение критерия реализуемости Хакими . . . . . . . . 20 2.3. Примеры векторов реализуемых в 2-комплексы и простейшие необходимые условия реализуемости . . . . . . . . . . 24 2.4. 2-приводимые и редукционные векторы. . . . . . . . . . . . Литература
Введение К важнейшим задачам прикладной математики относятся многоиндексные задачи большой размерности [3, 6, 10]. В работе рассматриваются некоторые модели и задачи, описываемые многоиндексными симметричными бинарными (состоящими из нулей и единиц) матрицами. Такие k-индексные матрицы (с некоторыми ограничениями на элементы) задают (локально) k-мерные комплексы. Полученные в работе результаты важны для некоторых разделов прикладной математики. В ряде литературы изучаются геометрические фигуры, путём разбиения их некоторым правильным образом на простейшие фигуры — симплексы. Те геометрические фигуры, которые можно надлежащим образом разбить на симплексы, называются полиэдрами, а сама схема разбиения на симплексы называется комплексом [1]. Отметим, что в более общем случае комплексы называются гиперграфами [2, 4]. Но мы придерживаемся понятия комплекса, так как для наших задач оно подходит лучше. Так как каждый граф (без петель) [18] (1-мерный комплекс, если этот граф не является вполне несвязным) взаимно однозначно соответствует своей матрице смежности (2-индексной симметричной матрице), то многие дискретные двухиндексные задачи и модели решаются применением методов теории графов и актуальным является распространение этих методов на многоиндексные задачи. Отметим, что некоторые полученные результаты имеют приложение в теории многоиндексных транспортных задач [6, 10]. Характеризация комплексов целочислеными неотрицательными векторами — это важная задача, имеющая приложения в многоиндексных задачах большой размерности [3, 6].
I.
k-комплексы, многоиндексные бинарные матрицы
1.1.
О реализуемости векторов в граф
Все n-вершинные графы без петель и комплексы, где n
⩾
2,
будем рассматривать с фиксированным множеством вершин U(n) =
= {u1, . . . , un} (если не оговорено противного и кроме некоторых частных случаев). Комплексы (в том числе и графы) будем обозначать буквой G с верхним индексом, указывающим размерность комплекса; произвольную k-индексную бинарную матрицу размерности n × · · · × n
n
будем
обозначать X(k)
n
=
xij...ik
, где 1 ⩽ ij ⩽ n, 1 ⩽ j ⩽ n (причём, если таких матриц несколько, то верхний индекс слева будет обозначать номер
матрицы).
Распространим на многомерный случай понятие реализуемости целочисленного неотрицательного вектора в граф степенями вершин распространено (вершины графа — это количество рёбер графа, инцидентных
этой вершине).
Определение 1. Целочисленный неотрицательный вектор A
=
= (a1, . . . , an) называется реализуемым в граф, если существует такой
граф G = G1 (A) с множеством вершин U(n), что степень каждой вершины ui равна ai (deg ui = deg1 ui = ai). Граф G1 (A) называется реализацией вектора 12.
Пример 1. На рис. 1 изображены два (различных) графа G1
1 = G1
1 (A)
и G1
2 = G1
2 (A), являющихся реализациями вектора A = (3, 3, 3, 2, 2, 1).
Выше рис. 1 представлены матрицы смежности этих графов 1X(1)
6
(A) и
2X(1)
6
(A).
В дальнейшем будем отождествлять графы с их матрицами смежности, применяя символ «∼=» (в примере 1 имеет место G1
1 (A) ∼= 1X(1)
6
(A)
и G1
2 (A) ∼= 2X(1)
(A)).
Отметим простейшие необходимые условия реализуемости целочисленного неотрицательного вектора A = (a1, . . ., an) в граф: а) n i=1 ai = 2q, где q ∈ Z; б) max 1⩽i⩽nai меньше количества положительных координат вектора A. 1X(1) 6 (A) = 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 2X(1) 6 (A) = 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 b b b b b b u1 u2 u3 u4 u5 u6 b b b b b b u1 u2 u3 u4 u5 u6 G1 1 (A) G1 2 (A) Рис. 1 Пример 2. а) Очевидно, что векторы (3, 3, 2, 2, 2, 1) и (4, 2, 2, 2, 0) не реализуемы в графы (это следует из приведённых выше необходимых условий реализуемости). б) Вектор A = (5, 5, 3, 3, 3, 1) в граф не реализуем. Если предположить существование графа G1 (A), то в нём вершина u1 инцидентна всем
вершинам u2, . . ., u6. Тогда подграф, образованный из G1 (A) удалением вершины u1, будет являться реализацией вектора (4, 2, 2, 2, 0). А этот вектор не реализуем в граф (см. пункт а) этого примера). Заметим, что нулевой вектор реализуем во вполне несвязный граф, являющийся 0-мерным комплексом. Задача о реализуемости целочисленного неотрицательного вектора в граф полностью решена. В [18] построены аналитические необходимые и достаточные условия реализуемости вектора в граф. Редукционный (алгоритмический) критерий реализуемости построен в [12] (в [13] вместо понятия реализуемости применяется термин «разбиение»). Распространим понятие реализуемости вектора в 1-мерный комплекс на многомерный случай. 1.2. О реализуемости вектора в k-комплекс и матрицы смежности k-комплексов Будем рассматривать комплексы только следующего вида. Определение 2. Для множества вершин U(n), где n ⩾ 2, и k ∈ Z, 0 ⩽ k ⩽ n − 1, через Sk+1(n) = ui1, . . . , uik+1 : uij ∈ U(n), uip ̸= uiq при p ̸= q (1.1) обозначим множество всех (k+1)-элементных подмножеств из U(n). Пара множеств U(n), Sk+1, где Sk+1 ⊆ Sk+1(n), которую обозначим Gk = Gk U(n), Sk+1 = Sk+1 Gk, (1.2) называется k-комплексом [11].
Мощность множества M обозначим |M|. Очевидно, что
Sk+1(n)
= Ck+1
n
.
Замечание 1.а) Для 0-комплекса G0 = G0 U(n), S1имеет место
равенство S1 = S1(n).
б) Пусть Γk(n) =
Gk U(n), Sk+1— множество всех k-комплексов
с вершинами U(n). Применяя терминологию теории графов, будем полагать, что каждый 0-комплекс — это вполне несвязный k-комплекс
(n ⩾ k + 1) для любого k ⩾ 1: G0 U(n), S1∈ Γk(n) (будем полагать,
что G0 U(n), S1= Gk (U(n), ∅) при k ⩾ 1).
В топологии элементы из Sk+1(n) называются k-мерными симплексами [1]. В частности, вершины из U(n) = S1(n) называются 0-мерными
симплексами. Элементы из S2(n) в теории графов называются рёбрами.
В трёх следующих определениях применим терминологию из теории
графов.
Определение 3. Для k-комплекса Gk = Gk U(n), Sk+1вершины
ui1, . . . , uim, где 2 ⩽ m ⩽ k + 1, называются смежными, если они принадлежат некоторому симплексу из Sk+1. Симплекс
ui1, . . . , uik+1
из
Sk+1 называется инцидентным каждой вершине uij, 1 ⩽ j ⩽ k + 1, а
каждая из вершин uij, 1 ⩽ j ⩽ k + 1, называется инцидентной симплексу
ui1, . . . , uik+1
.
Замечание 2.Рассмотрим
произвольный
k-мерный
симплекс
ui1, . . . , uik+1
из Sk+1 и m ∈ Z, 1 ⩽ m ⩽ k. Любое m-элементное
подмножество вершин {ui1, . . . , uim} из множества
ui1, . . . , uik+1
является (m − 1)-мерным симплексом. В топологии симплекс {ui1, . . ., uim}
называется гранью симплекса
ui1, . . . , uik+1
.
а) Множество k-комплексов Γk(n) =
Gk U(n), Sk+1есть подмножество всех k-мерных комплексов с множеством вершин U(n): в
отличие от произвольного k-мерного комплекса любой k-комплекс Gk
обладает дополнительным свойством: каждый m-мерный симплекс, где
1 ⩽ m ⩽ k, этого комплекса есть грань некоторого k-мерного симплекса
k-комплекса Gk (такие комплексы в топологии относятся к класcу полных комплексов [1]). Отметим, что определение 3 допускает существование в k-комплексе изолированных вершин (то есть k-комплекс может
иметь 0-мерные симплексы, не являющиеся гранями симплексов большой размерности).
б) Любой k-комплекс Gk, не содержащий изолированные вершины,
называется локально k-мерным комплексом [1].
Определение 4. Степенью каждой вершины ui ∈ U(n) k-комплекса
Gk = Gk U(n), Sk+1называется количество k-мерных симплексов, инцидентных вершине ui:
degk ui =
{ui, ui1, . . ., uik} ∈ Sk+1.
(1.3)
Напомним: матрица, состоящая из нулей и единиц, называется бинарной.
Для произвольного k-комплекса Gk = Gk U(n), Sk+1построим
(k + 1)-индексную бинарную матрицу X
Gk= X(k+1)
n
=
xi1...ik+1
, где
xi1...ik+1 = 1 ⇐⇒ {i1 . . . ik+1} ∈ Sk+1.
Определение 5. а) Для k-комплекса Gk = Gk U(n), Sk+1матрицей
смежности называется (k + 1)-индексная (бинарная) матрица
X
Gk= X(k+1)
n
=
xi1...ik+1
.
(1.4)
б) Матрицу X(3)
n
= (xijk), где 1 ⩽ i, j, k ⩽ n, и n ⩾ 2, будем называть
кубической.
Отметим, что указывать индексы матрицы смежности X
Gkне тре
буется, так как верхний индекс равен k, а нижний — количеству вершин
комплекса.
Для матрицы (смежности) X
Gk=
xi1...ik+1
отметим, что
xi1...ik+1
=
0 тогда и только тогда, когда: а) k-мерный симплекс
{i1 . . . ik+1} не принадлежит Sk+1 или б) набор вершин i1 . . . ik+1 содержит одинаковые вершины (то есть этот набор вершин не образует kмерный симплекс). Также легко видеть, что X
Gk— симметричная
матрица (любая перестановка индексов сохраняет значения элементов
матрицы).
Легко видеть, что для матрицы смежности X
Gk=
xi1...ik+1
, имеет
место
degk ui = 1
k
1⩽i1,...,ik⩽n
xii1...ik, 1 ⩽ i ⩽ n.
(1.5)
Замечание 3.а) Если в определении 5 положить k = 0, то получим
1-индексную матрицу смежности X(1) = X
G0, являющуюся нулевым
вектором (0, . . ., 0
n
) (в этом случае G0 — 0-мерный комплекс или вполне
несвязный граф).
б) Если рассматривать 0-комплекс как вполне несвязный k-комплекс
(замечание 1), то соответствующая (k + 1)-индексная матрица состоит
только из нулевых элементов.
Определение 6. Целочисленный неотрицательный вектор A
=
= (a1, . . . , an) называется реализуемым в k-комплекс, если существует
такой k-комплекс Gk (A) = Gk U(n), Sk+1, что степень каждой вершины ui равна ai (degk ui = ai), то есть любая вершина ui инцидентна ai
симплексам размерности k. Комплекс Gk (A) называется k-реализацией
вектора A.
Матрицу смежности k-комплекса Gk (A) = Gk U(n), Sk+1будем
также обозначать X(k+1) (A) = X
Gk (A)
. Здесь указывать нижний
индекс у матрицы смежности X(k+1) (A) не требуется, так как он равен
количеству координат вектора A (для графов G1 1 (A) и G1 2 (A) примера 1 имеет место X G1 1 (A) = 1X(2) 6 (A) = 1X(2) (A) и X G1 2 (A) = = 2X(2) 6 (A) = 2X(2) (A)). Любая симметричная бинарная матрица X(k+1) n = (xi1...ik+1), для которой xi1...ik+1 = 0, если среди индексов есть хотя бы два совпадающих, есть матрица смежности одного и только одного k-комплекса с множеством вершин U(n). Поэтому при заданном n между всеми такими матрицами и k-комплексами имеется взаимно однозначное соответствие. Будем отождествлять k-комплексы Gk (A) с их матрицами смежности X Gk (A) символом «∼=»: Gk (A) ∼= X Gk (A) . (1.6) Так как для реализуемого в k-комплекс Gk (A) вектора A = = (a1, . . . , an) каждая координата ai — это количество симплексов ui, ui1, . . ., uik+1 из Sk+1 Gk (A) (определения 4–6), то легко видеть, что для матрицы смежности X(k+1) (A) = (xijk) комплекса Gk (A) = = Gk U(n), Sk+1(Gk (A) ∼= X(k+1) (A)) имеет место 1⩽i1<···<ik⩽n xii1...ik = ai ∀i, 1 ⩽ i ⩽ n. (1.7) Отметим, что в общем случае для реализуемого в k-комплекс вектора A комплекс Gk (A) и матрица смежности X(k+1) (A) определены не однозначно. Пусть n-координатный вектор A реализуем в k-комплекс. Так как каждый k-мерный симплекс произвольного k-комплекса Gk (A) = = Gk U(n), Sk+1инцидентен k + 1 вершине, то имеет место Теорема 1. Если целочисленный неотрицательный вектор A =