Краевое сжатие

Стягивание ребра между указанными вершинами приводит к графу G/{uv}.

В теории графов сжатие ребра — это операция , которая удаляет ребро из графа и одновременно объединяет две вершины , которые оно ранее соединяло. Сжатие ребер — фундаментальная операция в теории миноров графов . Идентификация вершин является менее ограничительной формой этой операции.

Определение

Операция сжатия ребра происходит относительно конкретного ребра, $e$. Край $e$ удаляется и две инцидентные ему вершины, $u$ и $v$, объединяются в новую вершину $w$, где ребра, падающие на $w$ каждый соответствует ребру, инцидентному либо $u$ или $v$. В более общем смысле, операцию можно выполнить над набором ребер путем сжатия каждого ребра (в любом порядке).

Полученный график иногда записывается как $G/e$. (Сравните это с $G\setminus e$, что означает простое удаление края $e$ без объединения его инцидентных вершин.)

Сжатие ребра без создания нескольких ребер.

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

Формальное определение

Позволять $G=(V,E)$ быть графом ( или ориентированным графом ), содержащим ребро $e=(u,v)$ с $u\neq v$. Позволять $f$ быть функцией, которая отображает каждую вершину в $V\setminus \{u,v\}$ самому себе, а в противном случае отображает его в новую вершину $w$. Сокращение $e$ приводит к новому графику $G'=(V',E')$, где $V'=(V\setminus \{u,v\})\cup \{w\}$, $E'=E\setminus \{e\}$, и для каждого $x\in V$, $x'=f(x)\in V'$ инцидентен ребру $e'\in E'$ тогда и только тогда, когда соответствующее ребро $e\in E$ случается с $x$ в $G$.

Идентификация вершин

Идентификация вершин (иногда называемая сокращением вершин ) снимает ограничение, заключающееся в том, что сокращение должно происходить над вершинами, имеющими общее инцидентное ребро. (Таким образом, сжатие ребер является частным случаем идентификации вершин.) Операция может выполняться с любой парой (или подмножеством) вершин графа. Ребра между двумя сжимающимися вершинами иногда удаляются. Если $v$ и $v'$ являются вершинами различных компонент $G$, то мы сможем создать новый график $G'$ путем выявления $v$ и $v'$ в $G$ как новая вершина ${\textbf {v}}$ в $G'$. В более общем смысле, учитывая раздел множества вершин, можно идентифицировать вершины в этом разделе; результирующий граф известен как факторграф .

Расщепление вершин

Расщепление вершин , то же самое, что и разделение вершин, означает, что одна вершина разбивается на две, причем эти две новые вершины соседствуют с вершинами, с которыми была смежна исходная вершина. Это обратная операция идентификации вершин, хотя, как правило, для идентификации вершин соседние вершины двух идентифицированных вершин не являются одним и тем же набором.

Сокращение пути

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

скручивание

Рассмотрим два непересекающихся графа $G_{1}$ и $G_{2}$, где $G_{1}$ содержит вершины $u_{1}$ и $v_{1}$ и $G_{2}$ содержит вершины $u_{2}$ и $v_{2}$. Предположим, мы можем получить график $G$ путем определения вершин $u_{1}$ из $G_{1}$ и $u_{2}$ из $G_{2}$ как вершина $u$ из $G$ и определение вершин $v_{1}$ из $G_{1}$ и $v_{2}$ из $G_{2}$ как вершина $v$ из $G$. В скручивании $G'$ из $G$ относительно множества вершин $\{u,v\}$, вместо этого мы определяем, $u_{1}$ с $v_{2}$ и $v_{1}$ с $u_{2}$.

Приложения

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

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

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

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

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

См. также

• Подразделение (теория графов)

Ссылки

• Гросс, Джонатан; Йеллен, Джей (1998), Теория графов и ее приложения , CRC Press, ISBN  0-8493-3982-0
• Оксли, Джеймс (2006) [1992], Теория матроидов , Oxford University Press, ISBN  978-0-19-920250-8
• Розен, Кеннет (2011), Дискретная математика и ее приложения (7-е изд.), McGraw-Hill, ISBN  978-0-07-338309-5
• Уэст, Дуглас Б. (2001), Введение в теорию графов (2-е изд.), Прентис-Холл, ISBN  0-13-014400-2

Внешние ссылки

• Вайсштейн, Эрик В. «Сокращение краев» . Математический мир .