Разреженный матроид

Матроид разреженности — это математическая структура, которая показывает, насколько плотно мультиграф заполнен ребрами. Чтобы немного раскрыть это, разреженность — это мера плотности графа , которая ограничивает количество ребер в любом подграфе. Свойство иметь конкретный матроид в качестве меры плотности инвариантно относительно изоморфизмов графов, поэтому он является инвариантом графа .

Графы, которые нас интересуют, обобщают простые ориентированные графы , допуская наличие нескольких одинаково ориентированных ребер между парами вершин. Матроиды — это довольно общая математическая абстракция, описывающая степень независимости различных точек геометрического пространства и путей в графе; применительно к характеристике разреженности матроиды описывают определенные наборы разреженных графов. Эти матроиды связаны со структурной жесткостью графов и их способностью разлагаться на непересекающиеся по ребрам остовные деревья с помощью теорем Тутта и Нэша-Вильямса . Существует семейство эффективных алгоритмов, известных как игры с камушками , для определения того, удовлетворяет ли мультиграф заданному условию разреженности.

Определения

$(k,l)$-разреженный мультиграф. . Мультиграф $G=(V,E)$ является $(k,l)$-разреженный, где $k$ и $l$ являются целыми неотрицательными числами, если для каждого подграфа $G'=(V',E')$ из $G$, у нас есть $|E|\leq k|V|-l$.

$(k,l)$-плотный мультиграф. Мультиграф $G=(V,E)$ является $(k,l)$- тесно, если так $(k,l)$-редкий и $|E|=k|V|-l$.

$[a,b]$-разреженный и плотный мультиграф. Мультиграф $G=(V,E\cup F)$ является $[a,b]$-разреженный, если существует подмножество $F'\subset F$ такой, что подграф $G'=(V,E\cup F')$ является $(a,a)$-разреженный и подграф $G''=(V,F\setminus F')$ является $(b,b)$-редкий. Мультиграф $G$ является $[a,b]$-плотно, если, кроме того, $|E\cup F|=(a+b)|V|-(a+b)$.

$(k,l)$- разреженный матроид. $(k,l)$-разреженный матроид — это матроид, основное множество которого является множеством ребер полного мультиграфа на $n$ вершины с кратностью цикла $k-l$ и кратность ребер $2k-l$, и чьи независимые множества $(k,l)$-разреженные мультиграфы на $n$ вершины. Основой матроида являются $(k,l)$-плотные мультиграфы и схемы $(k,l)$-разреженные мультиграфы $G=(V,E)$ которые удовлетворяют $|E|=k|V|-l+1$.

Первые примеры разреженных матроидов можно найти в . Не все пары $(k,l)$ вызвать матроида.

Пары (k,l), образующие матроид

Следующий результат дает достаточные ограничения на $(k,l)$ за существование матроида.

Теорема. $(k,l)$-разреженные мультиграфы на $n$ вершины являются независимыми множествами матроида, если

• $n\geq 1$ и $l\in [0,k]$;
• $n\geq 2$ и $l\in (k,{\frac {3}{2}}k)$; или
• $n=2$ или $n\geq {\frac {l}{2k-l}}$ и $l\in [{\frac {3}{2}}k,2k)$.

Некоторые следствия этой теоремы заключаются в том, что $(2,3)$-разреженные мультиграфы образуют матроид, а $(3,6)$-разреженные мультиграфы этого не делают. Следовательно, основания, т.е. $(2,3)$-плотные мультиграфы должны иметь одинаковое количество ребер и могут быть построены с использованием методов, обсуждаемых ниже. С другой стороны, без этой матроидной структуры максимально $(3,6)$-разреженные мультиграфы будут иметь разное количество ребер, и интересно определить тот, у которого максимальное количество ребер.

Связь с жесткостью и разложением

Структурная жесткость заключается в определении того, являются ли почти все, т.е. универсальные , вложения графа (простого или множественного) в некоторые $d$-мерное метрическое пространство является жестким. Точнее, эта теория дает комбинаторные характеристики таких графов. В евклидовом пространстве Максвелл показал, что независимость в матроиде разреженности необходима для того, чтобы граф был в целом жестким в любом измерении.

Максвелловское направление. Если график $G$ в общем случае минимально жёсткий в $d$-размерности, то она независима в $\left(d,{d+1 \choose 2}\right)$- разреженный матроид.

Обращение этой теоремы было доказано в $2$-размерности, что дает полную комбинаторную характеристику вообще жестких графов в $\mathbb {R} ^{2}$. Однако обратное неверно для $d\geq 3$см. комбинаторные характеристики типично жестких графов .

Другие матроиды разреженности использовались, чтобы дать комбинаторные характеристики обычно жестких мультиграфов для различных типов структур, см. жесткость для других типов структур . В следующей таблице суммированы эти результаты с указанием типа универсального жесткого каркаса в данном измерении и эквивалентного условия разреженности. Позволять $kG$ — мультиграф, полученный дублированием ребер мультиграфа $G$ $k$ раз.

Типовой минимально жесткий каркас	Условие разреженности
Шарнирный каркас в $\mathbb {R} ^{2}$	$(2,3)$-тугой
Шарнирный каркас в $\mathbb {R} ^{2}$ по общим многогранным нормам	$(2,2)$-тугой
Каркас боди-бара в $\mathbb {R} ^{d}$	$\left({d+1 \choose 2},{d+1 \choose 2}\right)$-тугой
$(d-2)$- пластинчато-стержневой каркас в $\mathbb {R} ^{d}$	$\left({d+1 \choose 2}-1,{d+1 \choose 2}\right)$-тугой
Кузовно-шарнирный каркас в $\mathbb {R} ^{d}$	$\left({d+1 \choose 2}-1\right)G$ является $\left({d+1 \choose 2},{d+1 \choose 2}\right)$-тугой
Фреймворк Body-CAD в $\mathbb {R} ^{2}$	примитивный CAD-график $\left[1,2\right]$-тугой
Каркас Body-CAD без совпадающих точек в $\mathbb {R} ^{3}$	примитивный CAD-график $\left[3,3\right]$-тугой

Теорема Тутта и Нэша-Вильямса показывает, что $(k,k)$-плотные графы эквивалентны графам, которые можно разложить на $k$ остовные деревья, не пересекающиеся по краям, называемые $k$-древесности. А $(k,a)$-дерево – это мультиграф $G$ такой, что добавление $a$ края к $G$ дает $k$- древовидная структура. Для $l\in [k,2k)$, а $(k,l)$-разреженный мультиграф – это $(k,l-k)$-дерево; это было впервые показано для $(2,3)$ разреженные графики. Кроме того, многие из приведенных выше результатов по жесткости и разреженности можно записать в терминах остовных деревьев, не пересекающихся по ребрам.

Построение разреженных мультиграфов

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

Общие (k,l)-разреженные мультиграфы

Первая конструкция предназначена для $\left(k,k\right)$-плотные графики. Обобщенный $(k,1)$-расширение тройное $(k,1,j)$, где $j$ края удаляются, т. $1\leq j\leq k$, и новая вершина $u$ соединен с вершинами этих $j$ края и до $k-j$ отдельные вершины. Обычный $(k,1)$-расширение - это $(k,1,1)$-расширение.

Теорема. Мультиграф – это $(k,k)$-плотным тогда и только тогда, когда он может быть построен из одной вершины с помощью последовательности $(k,0)$- и $(k,1,j)$-расширения.

Затем эта теорема была распространена на общие $(k,l)$-плотные графики. Рассмотрим еще одно обобщение $1$-расширение, обозначаемое $(k,1,i,j)$, для $0\leq j\leq i\leq k$, где $j$ ребра удаляются, новая вершина $u$ соединен с вершинами этих $j$ края, $i-j$ петли добавляются к $u$, и $u$ подключен к $k-i$ другие различные вершины. Кроме того, пусть $P_{l}$ обозначаем мультиграф с одним узлом и $l$ петли.

Теорема. Мультиграф $G$ является $(k,l)$-плотно для

• $l\in [1,k]$ тогда и только тогда, когда $G$ может быть построен из $P_{k-l}$ через последовательность $(k,1,i,j)$-расширения, такие что $0\leq j\leq i\leq k-1$ и $i-j\leq k-l$;
• $l=0$ тогда и только тогда, когда $G$ может быть построен из $P_{k-l}$ через последовательность $(k,1,i,j)$-расширения, такие что $0\leq j\leq i\leq k$ и $i-j\leq k-l$.

Ни одна из этих конструкций не является достаточной, если граф простой. Следующие результаты касаются $(k,l)$-разреженные гиперграфы . Гиперграф – это $s$-однородным, если каждое его ребро содержит ровно $s$ вершины. Сначала создаются условия существования $(k,l)$-плотные гиперграфы.

Теорема. Существует $n_{0}$ такой, что для всех $n\geq n_{0}$, существуют $s$-однородные гиперграфы на $n$ вершины, которые $(k,l)$-тугой.

Следующий результат распространяет теорему Тутта и Нэша-Вильямса на гиперграфы.

Теорема. Если $G$ это $(k,l)$-плотный гиперграф, для $l\geq k$, затем $G$ это $(k,l-k)$ древовидность, при которой $l-k$ добавленные ребра содержат не менее двух вершин.

Карта-гиперграф — это гиперграф, который допускает такую ​​ориентацию , что каждая вершина имеет выходную степень $1$. А $k$-map-hypergraph — это карта-гиперграф, которую можно разложить на $k$ карты-гиперграфы, не пересекающиеся по краям.

Теорема. Если $G$ это $(k,l)$-плотный гиперграф, для $k\geq l$, затем $g$ представляет собой союз $l$- древовидность и $(k-l)$-карта-гиперграф.

(2,3)-разреженные графы

Рисунок 1. А $(2,3)$-схема.

Первый результат показывает, что $(2,3)$-плотные графы, т.е. минимально жесткие графы в общем случае в $\mathbb {R} ^{2}$ имеют конструкции Геннеберга.

Теорема. График $G$ является $(2,3)$-плотный тогда и только тогда, когда его можно построить из полного графа $K_{2}$ через последовательность $0$- и $1$-расширения.

Следующий результат показывает, как построить $(2,3)$-цепи. В этой обстановке $2$-sum объединяет два графика, идентифицируя два $K_{2}$ подграфы в каждом, а затем удаляем объединенное ребро из полученного графа.

Теорема. График $G$ это $(2,3)$-схема тогда и только тогда, когда она может быть построена из непересекающихся копий полного графа. $K_{4}$ через последовательность $1$-расширения внутри связанных компонентов и $2$-суммы компонент связности.

Метод построения $3$-связанный $(2,3)$-схемы еще проще.

Теорема. График $G$ это $3$-связанный $(2,3)$-схема тогда и только тогда, когда ее можно построить по полному графу $K_{4}$ через последовательность $1$-расширения.

Эти схемы также обладают следующим комбинаторным свойством.

Теорема. Если график $G$ это $(2,3)$-схема, не являющаяся полным графом $K_{4}$, затем $G$ имеет по крайней мере $3$ вершины степени $3$ такое, что выполнение $1$-приведение к любой из этих вершин дает другую $(2,3)$-схема.

(2,2)-разреженные графы

Следующие результаты показывают, как построить $(2,2)$-схемы с использованием двух разных методов построения. Для первого метода базовые графы показаны на рисунке 2, а три операции соединения показаны на рисунке 2. $1$-join идентифицирует $K_{2}$ подграф в $G_{1}$ с краем а $K_{4}$ подграф в $G_{1}$и удаляет две другие вершины $K_{4}$. А $2$-join идентифицирует край $K_{4}$ подграф в $G_{1}$ с краем а $K_{4}$ подграф в $G_{2}$и удаляет остальные вершины на обеих $K_{4}$ подграфы. А $3$-join требует степени $3$ вершина $v_{1}$ в $G_{1}$ и степень $3$ вершина $v_{2}$ в $G_{2}$ и удаляет их, затем добавляет $3$ края между $G_{1}$ и $G_{2}$ такая, что существует биекция между соседями $v_{1}$ и $v_{2}$.

Рисунок 2. Базовые графы для построения $(2,2)$-цепи.

Рисунок 3. Сверху вниз $1$-, $2$-, и $3$-объединить операции по построению $(2,2)$-цепи.

Второй метод использует $2$-мерное расщепление вершин, определенное при построении обобщенно жестких графов , и преобразование вершин в $K_{4}$ операция замены вершины $v$ графа с $K_{4}$ граф и соединяет каждого соседа $v$ в любую вершину $K_{4}$. Теорема. График $G$ это $(2,2)$-замыкание тогда и только тогда, когда

• $G$ могут быть построены из непересекающихся копий базовых графов с помощью последовательности $1$-расширения внутри связанных компонентов и $1$-, $2$-, и $3$- суммы компонент связности;

• 

  Рисунок 4. А $(2,2)$-схема.

  $G$ может быть построен из $K_{4}$ через последовательность $0$- и $1$-расширения, вершины- $K_{4}$, и $2$-мерные операции разделения вершин

(2,1)-разреженные графы

Следующий результат дает метод построения $(2,1)$-плотные графы и распространяет на эти графы теорему Тутта и Нэша-Вильямса. Для построения базовыми графами являются $K_{5}$ с удаленным краем или $2$-сумма двух $K_{4}$ графов (общее ребро не удаляется), см. средний граф на рисунке 2. Кроме того, операция соединения ребер добавляет одно ребро между двумя графами.

Теорема. График $G$ является $(2,1)$-плотно тогда и только тогда, когда

• $G$ можно получить из $K_{5}$ с удаленным краем или $2$-сумма двух $K_{4}$ графики через последовательность $0$- и $1$-расширения, вершины- $K_{4}$, $2$-мерные операции разделения вершин и соединения ребер;
• $G$ - это непересекающееся по ребрам объединение остовного дерева и остовного графа, в котором каждый компонент связности содержит ровно один цикл.

Игры с камушками

Существует семейство эффективных алгоритмов на основе сетевых потоков для идентификации $(k,l)$-разреженные графы, где $l\in [0,2k]$. Первый из этих типов алгоритмов был предназначен для $(2,3)$- разреженные графы. Эти алгоритмы объяснены на странице игры Pebble.