Введение

Удаление ребра графа и слияние его вершин

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

Определение

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

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

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

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

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

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

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

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

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

Скручивание

Рассмотрим два непересекающихся графа G и H, где G содержит вершины u1 и u2, а H содержит вершины v1 и v2. Предположим, что мы можем получить граф G', объединив G и H, отождествляя вершины u1 и v1 в вершину w1, а вершины u2 и v2 в вершину w2. В скручивании G относительно множества вершин {w1, w2} мы вместо этого отождествляем u1 с v2 и u2 с v1.

Приложения

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