В теории графов , ребро сжатие является операцией , которая удаляет ребро из графа, одновременно объединяя две вершины , которые она ранее присоединившейся. Сжатие ребер - фундаментальная операция в теории миноров графов . Идентификация вершин - менее ограничительная форма этой операции.
Определение
Операция сжатия края происходит относительно определенного края,. Край удаляется и две его инцидентные вершины, а также , объединяются в новую вершину , где ребра, инцидентные каждому соответствует ребро, инцидентное либо или же . В более общем смысле, операция может выполняться на наборе ребер путем сжатия каждого ребра (в любом порядке). [1]
Полученный индуцированный граф иногда записывают как . (Сравните это с, что означает удаление края .)
Как определено ниже, операция стягивания ребер может привести к графу с несколькими ребрами, даже если исходный граф был простым графом . [2] Однако некоторые авторы [3] запрещают создание нескольких ребер, так что сжатие ребер, выполняемое на простых графах, всегда дает простые графы.
Формальное определение
Позволять граф ( или ориентированный граф ), содержащий ребро с участием . Позволять - функция, отображающая каждую вершину в в себя, а в противном случае отображает его в новую вершину . Сокращение приводит к новому графику , где , , и для каждого , падает на край тогда и только тогда, когда соответствующее ребро, имеет отношение к в .
Идентификация вершины
Идентификация вершин (иногда называемая сжатием вершин ) снимает ограничение, согласно которому сжатие должно происходить по вершинам, имеющим общее инцидентное ребро. (Таким образом, стягивание ребер является частным случаем идентификации вершин.) Операция может выполняться на любой паре (или подмножестве) вершин в графе. Иногда удаляют ребра между двумя сужающимися вершинами. Если а также являются вершинами различных компонент , тогда мы можем создать новый график путем выявления а также в как новая вершина в . [4] В более общем смысле, учитывая разбиение множества вершин, можно идентифицировать вершины в разбиении; полученный граф называется фактор-графом .
Скалывание вершин
Разделение вершин , которое аналогично разделению вершин, означает, что одна вершина разбивается на две, где эти две новые вершины смежны с вершинами, с которыми была смежна исходная вершина. Это операция, обратная идентификации вершины, хотя, как правило, для идентификации вершины смежные вершины двух идентифицированных вершин не являются одним и тем же множеством.
Сужение пути
Сужение пути происходит на наборе ребер на пути, которые сжимаются, образуя единственное ребро между конечными точками пути. Ребра, инцидентные вершинам на пути, либо удаляются, либо произвольно (или систематически) соединяются с одной из конечных точек.
Скручивание
Рассмотрим два непересекающихся графа а также , где содержит вершины а также а также содержит вершины а также . Предположим, мы можем получить график путем определения вершин из а также из как вершина из и определение вершин из а также из как вершина из . В скручивании из относительно множества вершин , вместо этого мы идентифицируем с участием а также с участием . [5]
Приложения
Методы сжатия ребер и вершин ценны при доказательстве индукцией по количеству вершин или ребер в графе, где можно предположить, что свойство выполняется для всех меньших графов, и это может быть использовано для доказательства свойства для большего графа.
Край сжатия используется в рекурсивной формулы для числа остовных деревьев произвольного связного графа , [6] и в рекуррентной формуле для хроматического многочлена простого графа. [7]
Сокращения также полезны в структурах, где мы хотим упростить граф, идентифицируя вершины, которые представляют по существу эквивалентные объекты. Одним из наиболее распространенных примеров является редукция общего ориентированного графа к ациклическому ориентированному графу путем сжатия всех вершин в каждой сильно связной компоненте . Если отношение, описываемое графом, является транзитивным , информация не теряется до тех пор, пока мы помечаем каждую вершину набором меток вершин, которые были сжаты для ее образования.
Другой пример - объединение, выполняемое при распределении регистров раскраски глобального графа , где вершины сужаются (где это безопасно), чтобы исключить операции перемещения между отдельными переменными.
Сжатие кромок используется в пакетах 3D-моделирования (вручную или с помощью некоторых функций программного обеспечения для моделирования), чтобы последовательно уменьшать количество вершин, помогая создавать низкополигональные модели.
Смотрите также
Заметки
- ^ Гросс и Йеллен 1998 , стр. 264
- ^ Кроме того, петли могут возникать, когда граф начинался с нескольких ребер или, даже если граф был простым, из-за многократного применения стягивания ребер.
- Перейти ↑ Rosen 2011 , p. 664
- Перейти ↑ Oxley, 1992 , pp. 147-148
- Перейти ↑ Oxley 1992 , p. 148
- ^ Гросс и Йеллен 1998 , стр. 264
- Перейти ↑ West 2001 , p. 221
Рекомендации
- Гросс, Джонатан; Йеллен, Джей (1998), теория графов и ее приложения , CRC Press, ISBN 0-8493-3982-0
- Оксли, Джеймс (1992), Теория матроидов , Oxford University Press
- Розен, Кеннет (2011), Дискретная математика и ее приложения (7-е изд.), McGraw-Hill, ISBN 9780073383095
- Уэст, Дуглас Б. (2001), Введение в теорию графов (2-е изд.), Прентис-Холл, ISBN 0-13-014400-2