Сужение ребра

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

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

• 1 Определение
  • 1.1 Формальное определение
  • 1.2 Идентификация вершины
  • 1.3 Раскол вершины
  • 1.4 Сокращение пути
  • 1.5 Скручивание
• 2 Приложения
• 3 См. Также
• 4 Примечания
• 5 Ссылки
• 6 Внешние ссылки

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

Результирующий индуцированный граф иногда записывается как $G\; /\; e\; \{\backslash \; displaystyle\; G\; /\; e\}$. (Сравните это с $G\; \setminus \; e\; \{\backslash \; displaystyle\; G\; \backslash \; setminus\; e\}$, что означает удаление края $e\; \{\backslash \; displaystyle\; e\}$.)

Заключение контрактов ребро без создания нескольких ребер.

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

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

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

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

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

Разделение вершин

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

Сужение пути

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

Скручивание

Даны два непересекающихся графа $G\; 1\; \{\backslash \; displaystyle\; G\_\; \{1\}\}$и $G\; 2\; \{\backslash \; displaystyle\; G\_\; \{2\}\}$, где $G\; 1\; \{\backslash \; displaystyle\; G\_\; \{1\}\}$содержит вершины $u\; 1\; \{\backslash \; displaystyle\; u\_\; \{1\}\}$и $v\; 1\; \{\backslash \; displaystyle\; v\_\; \{1\}\}$и $G\; 2\; \{\backslash \; displaystyle\; G\_\; \{2\}\}$содержит вершины $u\; 2\; \{\backslash \; displaystyle\; u\_\; \{\; 2\}\}$и $v\; 2\; \{\backslash \; displaystyle\; v\_\; \{2\}\}$. Предположим, мы можем получить граф $G\; \{\backslash \; displaystyle\; G\}$, идентифицировав вершины $u\; 1\; \{\backslash \; displaystyle\; u\_\; \{1\}\}$из $G\; 1\; \{\backslash \; displaystyle\; G\_\; \{1\}\}$и $u\; 2\; \{\backslash \; displaystyle\; u\_\; \{2\}\}$из $G\; 2\; \{\backslash \; displaystyle\; G\_\; \{2\}\}$как вершина $u\; \{\backslash \; displaystyle\; u\}$из $G\; \{\backslash \; displaystyle\; G\}$и идентификация вершин $v\; 1\; \{\backslash \; displaystyle\; v\_\; \{1\}\}$из $G\; 1\; \{\backslash \; displaystyle\; G\_\; \{1\}\}$и $v\; 2\; \{\backslash \; displaystyle\; v\_\; \{2\}\}$из $G\; 2\; \{\backslash \; displaystyle\; G\_\; \{2\}\}$как вершина $v\; \{\backslash \; displaystyle\; v\}$из $G\; \{\backslash \; displaystyle\; G\}$. При скручивании $G\; \text{'}\{\backslash \; displaystyle\; G\text{'}\}$из $G\; \{\backslash \; displaystyle\; G\}$относительно набора вершин $\{u,\; v\}\; \{\backslash \; displaystyle\; \backslash \; \{u,\; v\; \backslash \}\}$, вместо этого мы идентифицируем $u\; 1\; \{\backslash \; displaystyle\; u\_\; \{1\}\}$с $v\; 2\; \{\backslash \; displaystyle\; v\_\; \{2\}\}$и $v\; 1\; \{\backslash \; displaystyle\; v\_\; \{1\}\}$с $u\; 2\; \{\backslash \; displaystyle\; u\_\; \{2\}\}$.

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

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

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

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

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

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

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

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