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

Определение

Операция стягивания ребра производится над конкретным ребром e . Ребро e удаляется, а две его инцидентные вершины, u и v , сливаются в новую вершину w , где рёбра, инцидентные w , соответствуют рёбрам, инцидентным либо u , либо v . Более обще, операция может быть проведена на множестве рёбер путём стягивания рёбер из множества (в любом порядке) .

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

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

Пусть G =( V , E ) — граф ( или ориентированный граф ), содержащий ребро e =( u , v ) с u ≠ v . Пусть f — функция, которая отображает любую вершину в V \{ u , v } в себя, а в противном случае — в вершину w . Стягивание e приводит к новому графу G′ =( V′ , E′ ), где V′ =( V \{ u , v })∪{ w }, E′ = E \{ e }, и для любой вершины x ∈ V , вершина x′ = f ( x )∈ V′ инцидентна ребру e′ ∈ E′ тогда и только тогда, когда соответствующее ребро e ∈ E инцидентно x в G .

Отождествление вершин

Отождествление вершин (иногда называется стягиванием вершин ) не использует ограничение, что стягивание должно проводиться с вершинами, инцидентными одному ребру (таким образом, стягивание ребра является частным случаем отождествления вершин). Эта операция может быть проведена с любой парой (или подмножеством) вершин в графе. Рёбра между двумя стягиваемыми вершинами иногда удаляются. Если v и v' — вершины различных компонент графа G, то мы можем создать новый граф G' путём отождествления v и v' в G в новую вершину v в G' .

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

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

Стягивание пути

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

Скручивание

Если даны два непересекающихся графа G ₁ and G ₂ , где G ₁ содержит вершины u ₁ и v ₁ , а G ₂ содержит вершины u ₂ и v ₂ . Предположим, что мы получили граф G путём отождествления вершин u ₁ графа G ₁ и u ₂ графа G ₂ , получая вершину u в G, и отождествления вершин v ₁ графа G ₁ и v ₂ графа G ₂ , получая вершину v в G. В скручивании G' графа G относительно пары вершин {u, v}, мы отождествляем вместо указанных выше вершины u ₁ с v ₂ и v ₁ с u ₂ .

Приложения

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

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

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

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

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

См. также

• Подразбиение

Примечания

Литература

• Jonathan Gross, Jay Yellen. Graph Theory and its applications. — CRC Press, 1998. — ISBN 0-8493-3982-0 .
• (англ.) ( . Matroid Theory. — Oxford University Press , 1992.
• Kenneth Rosen. Discrete Mathematics and Its Applications. — 7th. — McGraw-Hill , 2011. — ISBN 9780073383095 .
• (англ.) ( . Introduction to Graph Theory. — 2nd. — Prentice-Hall, 2001. — ISBN 0-13-014400-2 .

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .