Сокращение края

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

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

Определение

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

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

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

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

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

Пусть будет графом ( или ориентированным графом ), содержащим ребро с . Пусть будет функцией, которая отображает каждую вершину в себе, а в противном случае отображает ее в новую вершину . Сжатие приводит к новому графу , где , , и для каждого , инцидентно ребру тогда и только тогда, когда соответствующее ребро инцидентно в . Г = ( В , Э ) {\displaystyle G=(V,E)} е = ( ты , в ) {\displaystyle e=(u,v)} ты в {\displaystyle u\neq v} ф {\displaystyle f} В { ты , в } {\displaystyle V\setminus \{u,v\}} ж {\displaystyle w} е {\displaystyle е} Г = ( В , Э ) {\displaystyle G'=(V',E')} В = ( В { ты , в } ) { ж } {\displaystyle V'=(V\setminus \{u,v\})\чашка \{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] Г 1 {\displaystyle G_{1}} Г 2 {\displaystyle G_{2}} Г 1 {\displaystyle G_{1}} ты 1 {\displaystyle u_{1}} в 1 {\displaystyle v_{1}} Г 2 {\displaystyle G_{2}} ты 2 {\displaystyle u_{2}} в 2 {\displaystyle v_{2}} Г {\displaystyle G} ты 1 {\displaystyle u_{1}} Г 1 {\displaystyle G_{1}} ты 2 {\displaystyle u_{2}} Г 2 {\displaystyle G_{2}} ты {\displaystyle u} Г {\displaystyle G} в 1 {\displaystyle v_{1}} Г 1 {\displaystyle G_{1}} в 2 {\displaystyle v_{2}} Г 2 {\displaystyle G_{2}} в {\displaystyle v} Г {\displaystyle G} Г {\displaystyle G'} Г {\displaystyle G} { ты , в } {\displaystyle \{u,v\}} ты 1 {\displaystyle u_{1}} в 2 {\displaystyle v_{2}} в 1 {\displaystyle v_{1}} ты 2 {\displaystyle u_{2}}

Повторные сокращения

При наличии конечного набора ребер порядок, в котором выполняются сжатия на графе, не меняет результат (с точностью до изоморфизма). Результат сводится к показателю того, что изоморфно для двух ребер из . [6] Г / е / ( ф / е ) {\displaystyle Г/э/(ж/э)} Г / ф / ( е / ф ) {\displaystyle G/f/(e/f)} е , ф {\displaystyle e,f} Г {\displaystyle G}

Приложения

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

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

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

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

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

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

Примечания

  1. ^ Гросс и Йеллен 1998, стр. 264
  2. ^ Кроме того, петли могут возникать, когда граф изначально имел несколько ребер или, даже если граф был простым, из-за многократного применения сжатия ребер.
  3. ^ Розен 2011, стр. 664
  4. ^ Оксли 2006, стр. 147–8 §5.3 Теорема Уитни об изоморфизме 2
  5. ^ Оксли 2006, стр. 148
  6. ^ Wolle, Thomas; Bodlaender, Hans (2004). "A Note on Edge Contraction" (PDF) . Utrecht University: Information and Computing Sciences . Получено 1 января 2025 г. Стягивание ребер в графе коммутативно.
  7. ^ Гросс и Йеллен 1998, стр. 264
  8. ^ Уэст 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-е изд.), Prentice-Hall, ISBN 0-13-014400-2
Взято с "https://en.wikipedia.org/w/index.php?title=Сокращение_края&oldid=1266610704"