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

Удаление ребра графа и объединение его узлов

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

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

Определение

Операция сжатия ребра происходит относительно конкретного ребра . Ребро удаляется, а две его инцидентные вершины и объединяются в новую вершину , где ребра, инцидентные каждой, соответствуют ребру, инцидентному либо или . В более общем смысле, операцию можно выполнить над набором ребер путем сжатия каждого ребра (в любом порядке). ^[1] ${\displaystyle e}$ ${\displaystyle e}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle u}$ ${\displaystyle v}$

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

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

Как определено ниже, операция сжатия ребер может привести к созданию графа с несколькими ребрами, даже если исходный граф был простым графом . ^[2] Однако некоторые авторы ^[3] запрещают создание кратных ребер, поэтому сжатие ребер, выполняемое на простых графах, всегда приводит к созданию простых графов.

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

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

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

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

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

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

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

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

скручивание

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

Приложения

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

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

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

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

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

Смотрите также

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

Примечания

1. Гросс и Йеллен 1998, стр. 264
2. Кроме того, петли могут возникать, когда граф начинался с нескольких ребер или, даже если граф был простым, из-за многократного применения сжатия ребер.
3. Розен 2011, с. 664
4. Оксли 2006, стр. 147–8 §5.3 Теорема Уитни о 2-изоморфизме
5. Оксли 2006, с. 148
6. Гросс и Йеллен 1998, стр. 264
7. Вест 2001, с. 221

Рекомендации

• Гросс, Джонатан; Йеллен, Джей (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

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

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