Гомеоморфізм графів
Два графи G і G 'гомеоморфні, якщо існує ізоморфізм деякогопідрозділуграфа G і деякогопідрозділуграфа G ' [1] . Якщо ребра графа розуміти як відрізки, що з'єднують вершини (як зазвичай малюється на ілюстраціях), то два графи гомеоморфні у тих теорії графів, що вони гомеоморфні в топологічному сенсі.
Зміст
У загальному випадкупідрозділграфаG(іноді використовується термінрозширення[2] абопідрозділ) — це граф, отриманий поділом ребер уG. Розподіл деякого ребраeз кінцевими вершинами u,v> дає граф, що містить нову вершинуwі два ребра u,w> та w,v> замість ребраe[1] .
Наприклад, реброeз кінцями u,v>:
може бути розділено на два ребра,e1 іe2:
Зворотна операція,виключеннявершиниwз інцидентними їй ребрами (e1 ,e2), замінює суміжні вершиніwобидва ребра (e1,e2) на нове ребро, що з'єднує кінцеві точки пари. Слід підкреслити, що ця операція застосовна лише до вершин, інцидентних точно двом ребрам.
має вершину (з ім'ямw), яка може бути виключена, в результаті отримаємо:
Визначення, чи гомеоморфен графHпідграфуG, є NP-повним завданням [3] .
Барицентричні підрозділи
Барицентричний підрозділ розбиває кожне ребро графа. Це спеціальний вид підрозділу, який завжди дає дводольний граф. Цю процедуру можна повторювати, так щоn-ий барицентричний підрозділ є барицентричним підрозділом підрозділуn-1. Другий такий підрозділ завжди є простим графом.
Очевидно, що підрозділграфа зберігає планарність Теорема Понтрягіна-Куратовського стверджує, що
кінцевий граф є планарним тоді і тільки тоді, коли він не містить підграфа,гомеоморфногоK5 (повний граф з п'ятьма вершинами), абоK3,3 ( повний дводольний граф з шістьма вершинами, з яких три з'єднані з кожною з трьох, що залишилися).
У наступному прикладі графи G та H гомеоморфні.
Якщо граф G' створений підрозділом зовнішніх ребер графа G, а граф H' створений підрозділом внутрішніх ребер графа H, то G' і H' мають схожі графічні уявлення:
Таким чином, існує ізоморфізм між графами G' і H', що означає, що G і H гомеоморфні.