Сужение края - Edge contraction

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

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

Определение

Операция сжатия края происходит относительно определенного края . Ребро удаляется, а две его инцидентные вершины и , объединяются в новую вершину , где инцидентные каждой ребра соответствуют ребру, инцидентному либо или . В более общем смысле, операция может выполняться на наборе ребер путем сжатия каждого ребра (в любом порядке). ${\ 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}$

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

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

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

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

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

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

Скалывание вершин

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

Сужение пути

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

Скручивание

Рассмотрим два непересекающихся графа и , где содержит вершины и, а содержит вершины и . Предположу , что мы можем получить график отождествления вершин из и из как вершины из и отождествления вершин из и в качестве вершины из . В скручивание из относительно множества вершин , мы определяем, а, с и с . ${\ 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 \ {и, v \}}$${\ displaystyle u_ {1}}$${\ displaystyle v_ {2}}$${\ displaystyle v_ {1}}$${\ displaystyle u_ {2}}$

Приложения

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

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

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

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

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

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

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

Заметки

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

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

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

• Вайсштейн, Эрик В. «Сужение краев» . MathWorld .