Гиперграфы: введение в 2-мерные комплексы

Костиков Ю. А., Мокряков А. В., Павлов В. Ю., Романенков А. М.

Гиперграфы:
введение в 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-приводимые и редукционные векторы. . . . . . . . . . . .
31

Литература
51

Введение

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

3

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)
6
(A)).

4

Отметим простейшие необходимые условия реализуемости целочисленного неотрицательного вектора 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 инцидентна всем

5

вершинам 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].

6

Мощность множества 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

7

обладает дополнительным свойством: каждый 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не тре
8

буется, так как верхний индекс равен 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) не требуется, так как он равен

9

количеству координат вектора 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
=

10

= (a1, . . . , an) реализуем в k-комплекс, то

n
i=1
ai = (k + 1) · q, где q ∈ Z,

причём, q — количество k-мерных симплексов любого k-комплекса
Gk (A)
В следующем утверждении также заключены необходимые и условия
реализуемости вектора в k-комплекс.
Теорема 2. Пусть целочисленный неотрицательный вектор A =
= (a1, . . . , an) реализуем в k-комплекс. Тогда

а) ai ⩽ Ck
n−1, 1 ⩽ i ⩽ n;

б) (k + 1)max
1⩽i⩽nai ⩽

n
i=1
ai.

Доказательство.
a) Здесь неравенство следует из того, что в произвольном k-комплексе
каждая вершина ui, 1 ⩽ i ⩽ n, может быть смежна с любыми k различными вершинами из подмножества вершин U(n) \ui и |U(n) \ui| = n−1.
б) Если q — это количество k-мерных симплексов k-комплекса Gk (A),
то q ⩾ max
1⩽i⩽nai и последнее утверждение этой теоремы следует из теоремы 1.
Пример 3. На рис. 2 изображены четыре 2-комплекса (полиэдра) G2
1,
G2
2, G2
3 и G2
4. Причём 2-мерные симплексы, принадлежащие комплексам G2
3 и G2
4, заштрихованы. Легко видеть, что комплексы G2
1 и G2
2
являются соответственно реализациями векторов A1 = (3, 3, 3, 3)
и A2 = (5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5), а различные комплексы G2
3 и G2
4 являются реализациями одного и того же вектора A3 =

11