Граф ізоморфізму можна описати як граф, у якому один граф може мати більше однієї форми. Це означає, що два різних графи можуть мати однакову кількість ребер, вершин і однакову зв’язність ребер. Ці типи графів відомі як графи ізоморфізму. Приклад графа ізоморфізму описується так:
Наведений вище графік містить такі речі:
- Один і той самий графік представлений у кількох формах.
- Отже, ми можемо сказати, що ці графи є графами ізоморфізму.
Умови ізоморфізму графа
Будь-які два графи будуть відомі як ізоморфізм, якщо вони задовольняють такі чотири умови:
- У даних графах буде однакова кількість вершин.
- У даних графах буде однакова кількість ребер.
- У наведених графіках буде однакова кількість ступенів.
- Якщо перший граф утворює цикл довжини k за допомогою вершин {v1, v2, v3, …. vk}, то інший граф також повинен утворювати такий же цикл такої ж довжини k за допомогою вершин {v1, v2, v3, …. vk}.
Примітка. Послідовність ступенів графа можна описати як послідовність ступенів усіх вершин у порядку зростання.
Важливі моменти
- Щоб будь-які два графи були ізоморфізмом, необхідними умовами є чотири визначені вище умови.
- Необов'язково, що визначені вище умови будуть достатніми, щоб показати, що дані графи ізоморфні.
- Якщо два графи задовольняють визначеним вище чотирьом умовам, навіть тоді необов’язково, що вони будуть ізоморфізмом.
- Якщо граф не задовольняє жодних умов, то можна сказати, що графи точно не є ізоморфізмом.
Достатні умови ізоморфізму графа
Якщо ми хочемо довести, що будь-які два графи є ізоморфізмами, є деякі достатні умови, які ми надамо нам, щоб гарантувати, що два графи точно є ізоморфізмами. Коли два графіки будуть успішно очищені від усіх чотирьох вищевказаних умов, лише тоді ми перевіримо ці графіки на достатні умови, які описані таким чином:
- Якщо графи доповнення обох графів є ізоморфізмами, то ці графи обов’язково будуть ізоморфізмами.
- Якщо суміжні матриці обох графів однакові, то ці графи будуть ізоморфізмом.
- Якщо відповідні графи двох графів отримані за допомогою видалення деяких вершин одного графа, а відповідні їм зображення в інших зображеннях є ізоморфізмом, то тільки тоді ці графи не будуть ізоморфізмом.
Якщо два графи задовольняють будь-яку з наведених вище умов, ми можемо сказати, що ці графи точно є ізоморфізмом.
Приклади ізоморфізму графів
Існує багато прикладів ізоморфізму графів, які описуються наступним чином:
приклад 1:
У цьому прикладі ми показали, чи є наступні графи ізоморфізмом.
рішення: Для цього ми перевіримо всі чотири умови ізоморфізму графа, які описані наступним чином:
Умова 1:
- У графі 1 всього 4 вершини, тобто G1 = 4.
- У графі 2 всього 4 вершини, тобто G2 = 4.
тут,
В обох графах G1 і G2 однакова кількість вершин. Отже, ці графіки задовольняють умову 1. Тепер перевіримо другу умову.
Умова 2:
- У графі 1 всього 5 ребер, тобто G1 = 5.
- У графі 2 всього 6 ребер, тобто G2 = 6.
тут,
В обох графах G1 і G2 немає однакової кількості ребер. Отже, ці графіки не задовольняють умову 2. Тепер ми не можемо перевірити всі інші умови.
Оскільки ці графи порушують умову 2. Отже, ці графи не є ізоморфізмом.
∴ Граф G1 і граф G2 не є графами ізоморфізму.
приклад 2:
У цьому прикладі ми показали, чи є наступні графи ізоморфізмом.
рішення: Для цього ми перевіримо всі чотири умови ізоморфізму графа, які описані наступним чином:
Умова 1:
- У графі 1 всього 4 вершини, тобто G1 = 4.
- У графі 2 всього 4 вершини, тобто G2 = 4.
- У графі 3 всього 4 вершини, тобто G3 = 4.
тут,
дискета
У всіх графах G1, G2 і G3 однакова кількість вершин. Отже, ці графіки задовольняють умову 1. Тепер перевіримо другу умову.
Умова 2:
- У графі 1 всього 5 ребер, тобто G1 = 5.
- У графі 2 всього 5 ребер, тобто G2 = 5.
- У графі 3 всього 4 ребра, тобто G2 = 4.
тут,
- В обох графах G1 і G2 однакова кількість ребер. Отже, ці графіки задовольняють умову 2.
- Але в графах (G1, G2) і G3 немає рівної кількості ребер. Отже, графіки (G1, G2) і G3 не задовольняють умову 2.
Оскільки, графи (G1, G2) і G3 порушують умову 2. Тож можна сказати, що ці графи не є ізоморфізмом.
∴ Граф G3 не є ізоморфізмом ні з графом G1, ні з графом G2.
Оскільки графи G1 і G2 задовольняють умову 2. Отже, ми можемо сказати, що ці графи можуть бути ізоморфізмом.
∴ Графи G1 і G2 можуть бути ізоморфізмом.
Тепер перевіримо третю умову для графів G1 і G2.
Умова 3:
- У графі 1 ступінь послідовності s дорівнює {2, 2, 3, 3}, тобто G1 = {2, 2, 3, 3}.
- У графі 2 ступінь послідовності s дорівнює {2, 2, 3, 3}, тобто G2 = {2, 2, 3, 3}.
тут
У обох графах G1 і G2 є однакова кількість послідовностей ступенів. Отже, ці графіки задовольняють умову 3. Тепер перевіримо четверту умову.
Умова 4:
Граф G1 утворює цикл довжиною 3 за допомогою вершин {2, 3, 3}.
обрізка рядка java
Граф G2 також утворює цикл довжиною 3 за допомогою вершин {2, 3, 3}.
тут,
Це показує, що обидва графи містять один і той же цикл, оскільки обидва графи G1 і G2 утворюють цикл довжиною 3 за допомогою вершин {2, 3, 3}. Отже, ці графіки задовольняють умову 4.
Таким чином,
- Графи G1 і G2 задовольняють усі чотири необхідні умови.
- Отже, G1 і G2 можуть бути ізоморфізмом.
Тепер перевіримо достатні умови, щоб показати, що графи G1 і G2 є ізоморфізмом.
Перевірка достатніх умов
Як ми дізналися, якщо графи доповнення обох графів є ізоморфізмами, то обидва графи обов’язково будуть ізоморфізмами.
Отже, ми намалюємо графи доповнення G1 і G2, які описані наступним чином:
У наведених вище графах доповнення G1 і G2 ми бачимо, що обидва графи є ізоморфізмами.
∴ Графи G1 і G2 є ізоморфізмами.
приклад 3:
У цьому прикладі ми показали, чи є наступні графи ізоморфізмом.
рішення: Для цього ми перевіримо всі чотири умови ізоморфізму графа, які описані наступним чином:
Умова 1:
- У графі 1 всього 8 вершин, тобто G1 = 8.
- У графі 2 всього 8 вершин, тобто G2 = 8.
тут,
В обох графах G1 і G2 однакова кількість вершин. Отже, ці графіки задовольняють умову 1. Тепер перевіримо другу умову.
Умова 2:
- У графі 1 загальна кількість ребер дорівнює 10, тобто G1 = 10.
- У графі 2 загальна кількість ребер дорівнює 10, тобто G2 = 10.
тут,
В обох графах G1 і G2 однакова кількість ребер. Отже, ці графіки задовольняють умову 2. Тепер перевіримо третю умову.
Умова 3:
- На графіку 1 ступінь послідовності s дорівнює {2, 2, 2, 2, 3, 3, 3, 3}, тобто G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- На графіку 2 ступінь послідовності s дорівнює {2, 2, 2, 2, 3, 3, 3, 3}, тобто G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
тут
У обох графах G1 і G2 є однакова кількість послідовностей ступенів. Отже, ці графіки задовольняють умову 3. Тепер перевіримо четверту умову.
Умова 4:
- Граф G1 утворює цикл довжини 4 за допомогою вершин ступеня 3.
- Граф G2 не утворює цикл довжиною 4 за допомогою вершин, оскільки вершини не є суміжними.
тут,
Обидва графи G1 і G2 не утворюють однаковий цикл однакової довжини. Отже, ці графіки порушують умову 4.
Оскільки графи G1 і G2 порушують умову 4. Отже, через порушення умови 4 ці графи не будуть ізоморфізмом.
∴ Графи G1 і G2 не є ізоморфізмом.