Стягивание ребра

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

Стягивание ребра между помеченными вершинами.

Определение

Операция стягивания ребра производится над конкретным ребром 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.
• James Oxley. Matroid Theory. — Oxford University Press, 1992.
• Kenneth Rosen. Discrete Mathematics and Its Applications. — 7th. — McGraw-Hill, 2011. — ISBN 9780073383095.
• Douglas B. West. Introduction to Graph Theory. — 2nd. — Prentice-Hall, 2001. — ISBN 0-13-014400-2.

Ссылки

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