6.8.3. Гомеоморфізм графів
Два графи гомеоморфні (або тотожні з точністю до вершин ступеня 2), якщо вони обидва можуть бути отримані з одного і того ж графа «включенням» у його ребра нових вершин ступеня 2. Якщо ребро графа зображено у вигляді лінії, то можна на ній по -
ставити крапку та вважати її новою вершиною ступеня 2. Формально ця операція визначається наступним чином.
Нехай G – будь-який граф і (a, b) – його ребро. Операцією підрозділу ребра (a,b) називається видалення з графа G ребра (a,b), додавання нової вершини c і додавання двох нових ребер (a,c) і (c,b).
Граф G 1 називається підрозділом графа G якщо G 1 може бути отриманий з G декількома підрозділами ребер.
Графи G 1 і G 2 називаються гомеоморфними якщо існують їх підрозділи, які ізоморфні.
Зображені на рис. 6.46 графи гомеомофни, і те саме можна сказати про будь-які два циклічні графи.
6.8.4. Автоморфізм графів
Автоморфізмом графа G називається ізоморфізм графа G на себе, при цьому всякий граф G має тотожний (або тривіальний) автоморфізм I, такий, що I(x) = x для кожного ребра x і кожної вершини x з G.
Автоморфізм графа є відображенням безлічі вершин на себе, що зберігає суміжність. Безліч таких автоморфізмів, що позначається Γ(G), утворює групу, яка називається групою графа G, або групою автоморфізмів графа G. Таким чином, елементи групи Γ(G) є підстановками, що діють на безлічі вершин графа.
На рис. 6.47 представлений вихідний граф та його автоморфізм.
v 2 v 3 v 3 v 2
Для підстановки теоретично графів прийнято запис
де ? 1 , ? 2 . φ n – самі числа 1, 2. n, але записані, можливо, вином порядку.
Таким чином, другий рядок підстановки утворюєперестановку ? 1 , ? 2 . φ n із чисел 1, 2. n. Різних підстановок взагалі з n елементів існує стільки ж, як і перестановок, тобто. n! = 1×2×3×. × n. Однак при побудові автоморфізмів потрібно збереження ступенів вершин та суміжності між ними, що у більшості випадків суттєво скорочує їхню кількість.
Найбільша кількість автоморфізмів у групі автоморфізмів існує у повних та порожніх графів – їх на n вершинах в обох випадках буде n!
Підстановка, що залишає на місці всі елементи, називається
початкової ( одиничної , тотожної ).
Її короткий запис α 0 =(1)(2). (n).
Для кожної підстановки А існує зворотна, тобто така, що перекладає φ i в i , вона позначається через Наприклад:
Результат послідовного застосування двох підстановок А та
У знову буде деякою підстановкою С: якщо А переводить i в i, а
У перекладає φ i в ψ i , то переводить i в ψ i . Підстановка називається добутком підстановок А і В, що записується так: С = АВ. Наприклад, якщо
При множенні підстановок не виконується закон комутативності, тобто взагалі АВ ≠ ВА, як у тому ж прикладі
Легко бачити, що IA = AI = А, = I, А (ВС) = (АВ) С (асоціативний закон).
Підстановка, що переставляє місцями лише два елементи i і j, називається транспозицією:
Підстановка, циклічно переставляє цю групу елементів, інші елементи залишає дома, називається циклом . Число елементів, що переставляються, називають довжиною циклу. Наприклад, підстановка А є цикл довжини 4: вона перекладає 1
3, 3 у 5, 5 у 4, 4 в 1, при цьому 2 залишається на своєму місці. Коротко це записується так:
Розглянемо граф G, зображений на рис.
Йогочотири вершини складають безліч
X цілих чисел 1, 2, 3, 4. Зауважимо, що слідую-
ний список підстановок:
включає всі підстановки множини X , збереження
няють відношення суміжності у графі G . Наприклад, вершини 1 і 4 суміжні G . Підстановка (1,3)(2)(4) перетворює вершини 1 і 4 вершини 3 і 4, і ці образи 3 і 4, також є суміжними. Таким чином, підстановка (1,3)(2)(4) зберігає суміжність вершин
У разі якщо в короткому записі присутні тільки цикли довжиною 2, зворотна підстановка будується завжди дуже просто, так як збігається з вихідною, наприклад, для зворотної α 1 = =(1)(3)(2,4), а для α 3 = (1,3)(2,4) оберненою є = (1,3)(2,4).
Насправді, якщо граф заданий своїм зображенням, пошук всіх автоморфізмів практично здійснюється шляхом пошуку можливих поворотів графа чи його «частин» навколо осей симетрії.
Завдання 6.15. Знайти групу автоморфізмів даного графа (рис. 6.49) і кожної підстановки навести зворотну.
Рішення . У цьому графі проглядається кілька умовних осей симетрії, щодо яких можна повертати граф.
Якщо перевернути граф щодо горизонтальної осі, отримаємо підстановку (рис.6.50):
Якщо перевернути граф щодо вертикальної осі, отримаємо підстановку (рис.6.51):
Якщо зробити ці повороти по черзі, то отримаємо четверту та останню в даному випадку підстановку (рис.6.52):
Завдання 6.16. Знайти всі графи, група підстановок яких містить підстановку (v 1, v 2, v 3, v 4, v 5).
Рішення. Такі завдання вирішуються перебірним методом, причому перебір найзручніше здійснювати за ступенями вершин.
Оскільки, як видно з цієї підстановки, у графі п'ять вершин, максимальний ступіньвершини дорівнює 4, мінімальна у разі порожнього графа дорівнює 0. Крім того, оскільки в циклі беруть участь усі п'ять вершин, це означає, що у всіх вершин ступеня однакові. Переберемо всі ступені від 0 до 4.
Нехай рівень всіх вершин дорівнює 0. Ця ситуація спостерігається в порожньому графі на п'яти вершинах, і він нам за своїми властивостями підходить. Отже, перший знайдений граф – P 5 (зазначимо, що конкретна нумерація вершин у разі не важлива).
Нехай ступінь усіх вершин дорівнює 1. Отже, сумарний ступінь вершин графа дорівнює 5, це число непарне, отже, такого графа немає.
Нехай ступінь всіх вершин дорівнює 2. Ця ситуація спостерігається у простому циклі на п'яти вершинах, за своїми властивостями він нам підходить, тільки важливо правильно пронумерувати вершини. Графічно можна зобразити знайдене рішення у вигляді кільця (рис. 6.53, а) або зірки (рис. 6.53, б). Обидва рішення еквівалентні.
Зверніть увагу на нумерацію вершин: вона повинна дозволяти здійснювати перехід 1→2→3→4→5→1. Наприклад, вершини у зірці можна було пронумерувати інакше (рис 6.53, в), але в жодному разі не можна порушувати циклічний порядок (рис. 6.53, г). В останньому випадку перестановка (1,2,3,4,5) порушить суміжність вершин (рис. 6.53, д): у вихідному графі вершина v 1 була суміжна з v 4 і v 5, а після такої перестановки стане суміжна з v 2 та v 3 . Отже, другий знайдений граф - простий цикл на 5 вершинах (з правильною нумерацією вершин).
Нехай ступінь всіх вершин дорівнює 3. Отже, сумарний ступінь вершин графа дорівнює 15, отже, такого графа немає.
Нехай ступінь всіх вершин дорівнює 4. Ця ситуація спостерігається у повному графі на п'яти вершинах, і він нам за своїми властивостями підходить (зазначимо, що нумерація вершин у цьому випадку не є важливою). Отже, знайденотри можливі графи: P 5 , Ц 5 , K 5 .