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

операція видалення ребра з графа із злиттям зв'язаних ребром вершин в одну вершину

В теорії графів стягування ребра — це операція, яка видаляє ребро з графу, а до цього зв'язані ребром вершини зливаються в одну вершину. Стягування ребра є фундаментальною операцією в теорії про мінори графів. Ототожнення вершин — інша форма цієї операції зі слабшими обмеженнями.

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

Визначення

ред.

Операція стягування ребра виконується над конкретним ребром e. Ребро e видаляється, а дві інцидентні йому вершини u і v, зливаються в нову вершину w, де ребра, інцидентні w, відповідають ребрам, інцидентним або u або v. Загальніше, операцію можна провести на множині ребер шляхом стягування ребер із множини (в будь-якому порядку)[1].

Як визначено нижче, операція стягування ребра може дати граф із кратними ребрами навіть якщо початковий граф був простим графом[2]. Однак деякі автори[3] не дозволяють створення кратних ребер, так що стягування ребер на простому графі завжди дають прості графи.

Формальне визначення

ред.

Нехай G=(V,E) — граф (чи орієнтований граф), що містить ребро e=(u,v) з uv. Нехай f — функція, яка відображає будь-яку вершину в V\{u,v} в себе, а в іншому випадку — у вершину w. Стягування e призводить до нового графу G'=(V',E'), де V'=(V\{u,v})∪{w}, E'=E\{e}, і для будь-якої вершини xV, вершина x'=f(x)∈V' інцидентна ребру e'E' тоді й лише тоді, коли відповідне ребро eE інцидентне x у G.

Ототожнення вершин

ред.

Ототожнення вершин (іноді називається стягуванням вершин) не використовує обмеження, що стягування повинне проводитися з вершинами, інцидентними одному ребру (таким чином, стягання ребра є частковим випадком ототожнення вершин). Цю операцію можна провести з будь-якою парою (або підмножиною) вершин у графі. Ребра між двома стягуваними вершинами іноді видаляються. Якщо v і v' — вершини різних компонент графу G, то ми можемо створити новий граф G' через ототожнення v і v' в G в нову вершину v в G'[4].

Розщеплення вершин

ред.

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

Стягування шляху

ред.

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

Скручування

ред.

Нехай дано два графи G1 і G2, що не перетинаються, де G1 містить вершини u1 і v1, а G2 містить вершини u2 v2. Припустимо, що ми отримали граф G шляхом ототожнення вершин u1 графу G1 і u2 графу G2, отримавши вершину u в G, і ототожнення вершин v1 графу G1 і v2 графу G2, отримавши вершину v в G. В скручуванні G' графу G відносно пари вершин {u, v}, ми ототожнюємо замість зазначених вище вершини u1 з v2 і v1 з u2[5].

Застосування

ред.

Як стягування ребра, так і стягування вершин мають важливе значення для доведення за математичною індукцією за кількістю вершин або ребер графу, де можна припустити, що властивість виконується для всіх менших графів і це можна використати для доведення властивостей великих графів.

Стягування ребра використовується в рекурсивній формулі числа стягувальних дерев довільного зв'язного графу[1] і в рекурентній формулі для хроматичного полінома простого графу[6].

Стягування також корисне в структурах, де потрібно спростити граф шляхом ототожнення вершин, які представляють істотно еквівалентні об'єкти. Найвідомішим прикладом є зведення загального орієнтованого графу до орієнтованого ациклічного графу стягуванням усіх вершин у кожній компоненті сильної зв'язності. Якщо відношення, описуване графом є транзитивним, ніяка інформація не втрачається, якщо позначити кожну вершину множиною позначок вершин, які стягнуто в цю вершину.

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

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

Див. також

ред.

Примітки

ред.
  1. а б Gross, Yellen, 1998, с. 264.
  2. Можуть також з'явитися петлі, якщо початковий граф мав кратні ребра. Петлі можуть з'явитися і з простого графу, якщо стягнути декілька ребер.
  3. Rosen, 2011, с. 664.
  4. Oxley, 1992, с. 147—148.
  5. Oxley, 1992, с. 148.
  6. West, 2001, с. 221.

Література

ред.

Посилання

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