 |
|
Поняття ізоморфізму графів
Графи G1=(V1,E1) та G2=(V2,E2) називаються ізоморфними, якщо існує така бієкція h:V1®V2, що "u,vÎV1 (u,v)ÎE1Û(h(u),h(v))ÎE2. Бієкція (взаємно однозначне відображення) h називається ізоморфізмом графів G1 та G2.
Наприклад, графи G1=({a,b,c,d},{(a,c),(b,c),(c,d)}) та G2=({1,2,3,4}, {(1,2),(1,3),(1,4)}) ізоморфні, оскільки існує таке взаємно однозначне відображення h множини {a,b,c,d} у множину {1,2,3,4}, а саме: h={<a,3>,<b,2>,<c,1>,<d,4>}, що для будь-яких вершин u та v графу G1 пара (u,v) є ребром графу G1 тоді й тільки тоді, коли пара (h(u),h(v)) є ребром графу G2. Дійсно, розглянемо ребро (а,с) графу G1. З означення відображення h маємо: h(а)=3, h(с)=1. Пара (1,3) є ребром графу G2. Для кінців ребра (b,c) графу G1 маємо: h(b)=2, h(c)=1. Пара (1,2) є ребром графу G2. Для ребра (c,d) графу G1 маємо: h(с)=1, h(d)=4. Пара (1,4) є ребром графу G2. Тепер розглянемо ребра графу G2, знайдемо прообрази кінців кожного ребра при відображенні h й перевіримо, чи є кожна пара цих прообразів ребром графу G1. Кінці ребра (1,2) мають такі прообрази: h-1(1)=c, h-1(2)=b. Пара (b,c) є ребром графу G1. Для ребра (1,3) маємо: h-1(1)=c, h-1(3)=а; пара (а,с) є ребром графу G1. Для ребра (1,4) маємо: h-1(1)=c, h-1(4)=d; пара (c,d) є ребром графу G1. Таким чином, умова ізоморфності для графів G1 та G2 виконується, отже, G1 та G2 ізоморфні.
Наведемо приклад графів, що не є ізоморфними. Розглянемо графи G та H (рис.6). Покажемо, що ці графи не ізоморфні. Скориста-ємося методом доведення від супротивного. Припустимо, що G та H ізоморфні. Тоді має існувати таке взаємно однозначне відображення h:{1,2,3,4}®{1,2,3,4}, що "u,vÎV1 (u,v)ÎE1Û(h(u),h(v))ÎE2, де V1 – множина вершин графу G, E1 – множина ребер графу G, а E2 – множина ребер графу H. Вершина 4 графу H має бути образом деякої вершини графу G (позначимо цю вершину w). Зауважимо, що вершина w має принаймні одне інцидентне ребро (позначимо його (w,s)), адже у графі G є лише вершини степеня 1 або 2. Тоді у графі H має бути ребро (h(w),h(s)). За нашим припущенням h(w)=4. Таким чином, виходить, що у графі H має бути ребро, що інцидентне вершині 4, але це неможливо, адже вершина 4 ізольована у графі H. Отже, маємо суперечність, а це означає, що наше припущення про ізоморфність графів G та H не правильне. Таким чином, графи G та H не ізоморфні.
| 
|
| а) | б) |
| Рис. 6 |