Главная | Обратная связь

Властивості ізоморфних графів

Твердження 7. Якщо графи G₁=(V₁,E₁) та G₂=(V₂,E₂) ізоморфні, то |V₁|=|V₂| та |E₁|=|E₂|.

Доведення. Оскільки графи G₁ й G₂ ізоморфні, то існує бієкція h:V₁®V₂, а це означає, що |V₁|=|V₂|. Щоб довести рівність |E₁|=|E₂|, побудуємо бієкцію f:E₁®E₂. Оскільки G₁ й G₂ ізоморфні, то (u,v)ÎE₁Û(h(u),h(v))ÎE₂. Визначимо відображення f:E₁®E₂ таким чином: f((u,v))=(h(u),h(v)).Покажемо, що f – бієкція. Для цього достатньо довести, що відображення f ін’єктивне та сюр’єктивне. Нехай (u₁,v₁) та (u₂,v₂) – різні ребра графу G. Покажемо, що ребра f((u₁,v₁)) та f((u₂,v₂)) також різні. Припустимо супротивне, тобто f((u₁,v₁))=f((u₂,v₂)). Маємо: f((u₁,v₁))=(h(u₁),h(v₁))=f((u₂,v₂))=(h(u₂),h(v₂)). Це означає, що виконується одна з умов: 1) h(u₁)=h(u₂), h(v₁)=h(v₂), 2) h(v₁)=h(u₂), h(u₁)=h(v₂). Розглянемо перший випадок. Оскільки h – бієкція, то u₁=u₂, v₁=v₂, отже, (u₁,v₁)=(u₂,v₂), що суперечить умові. У другому випадку маємо: v₁=u₂, u₁=v₂, але тоді ребра (u₁,v₁) та (u₂,v₂) однакові, що суперечить умові. Отже, f ін’єктивне. Покажемо сюр’єктивність f. Нехай (u,v)ÎE₂. Оскільки відображення h сюр’єктивне, то існують такі u₁ та v₁, що h(u₁)=u, h(v₁)=v. Отже, (u,v)=(h(u₁),h(v₁)) для деяких u₁, v₁ з множини V₁. Оскільки G₁ та G₂ ізоморфні, то (h(u₁),h(v₁))ÎE₂ Þ (u₁,v₁)ÎE₁, але (h(u₁),h(v₁))=f((u₁,v₁)), отже, довільний елемент множини E₂ має непорожній прообраз при відображенні f, тобто f сюр’єктивне. Твердження доведено.

Нехай A_G – матриця суміжності нетривіального графу G порядку n. Узгодженою перестановкою рядків та стовпчиків матриці A_G назвемо таке перетворення A_G. Виберемо цілі додатні числа i та j (1£i£n,1£j£n) й поміняємо місцями i-й та j-й рядки матриці A_G (результат позначимо А₁), а потім – i-й та j-й стовпчики матриці А₁ (результат позначимо А₂). Очевидно, що помінявши спочатку місцями i-й та j-й стовпчики, а потім i-й та j-й рядки, ми дістанемо також матрицю А₂, отже, надалі ми не зважатимемо на те, у якому порядку міняються місцями стовпчики й рядки.

Розглянемо приклад. Нехай граф задано матрицею суміжності А (рис.7,а). Виконаємо узгоджену перестановку другого та четвертого рядків та стовпчиків матриці А. Спочатку поміняємо місцями 2-й та 4-й рядки. В результаті маємо матрицю А₁, зображену на рис.7,б. Тепер міняємо місцями 2-й та 4-й стовпчики матриці А₁. Результат (матриця А₂) зображено на рис.7,в.

 

а)	б)	в)
	Рис. 7

Теорема 4. Скінченні графи G та H ізоморфні тоді й тільки тоді, коли матрицю суміжності одного з графів можна перетворити на матрицю суміжності іншого графу за допомогою скінченної послідовності узгоджених перестановок рядків та стовпчиків.

Доведення. Нехай G та H – графи порядку n, A_G, A_H – їх матриці суміжності. Не втрачаючи загальності, можна вважати, що множиною вершин кожного з графів є множина N_n (тобто множина перших n додатних цілих чисел). Якщо графи G та H ізоморфні, й h – ізоморфізм G та H, то елемент a_ij^(G) матриці A_G дорівнює елементу a_h(i)h(j)^(H) матриці A_H (i,jÎN_n), тому, виконавши узгоджені перестановки рядків та стовпчиків матриці A_G, побудуємо матрицю А, яка збігається з A_H. Перестановки виконуємо таким чином, що i-й рядок (i-й стовпчик) матриці A_G є h(i)-м рядком (h(i)-м стовпчиком) матриці А. Навпаки, якщо матрицю суміжності одного з графів (скажімо, A_G) можна перетворити на матрицю суміжності іншого графу за допомогою скінченної послідовності узгоджених перестановок рядків та стовпчиків, то це означає, що існує бієкція h: N_n®N_n, така що (i,j)ÎE_GÛ(h(i),h(j))ÎE_H. Побудуємо її таким чином. Будемо у тій матриці, до якої застосовується перетворення, позначати кожен рядок (стовпчик) тією вершиною, якою він був позначений до початку перетворень. Наприклад, якщо першим перетворенням, застосованим до матриці A_G, є узгоджена перестановка i-го та j-го рядків й стовпчиків, то у матриці, що побудована у результаті цього перетворення, позначимо i-й рядок (стовпчик) j-ю вершиною, а j-й рядок (стовпчик) – i-ю вершиною. Після завершення послідовності перетворень рядки (стовпчики) матриці-результату матимуть позначки. Нехай i – вершина графу G. Покладемо h(i)=j, якщо i-й рядок матриці-результату має позначку j. З побудови h випливає, що h є бієкцією (адже h(1),…, h(n) – це перестановка упорядкованої множини вершин {1,…,n}). Покажемо, що h – шукана бієкція. Нехай (i,j)ÎE_G. Тоді a_ij^(G)=1. Але у результаті послідовності перетворень, що застосовані до матриці A_G, одиниця, що знаходилася на перетині i-го рядка та j-го стовпчика, займатиме у матриці-результаті (яка збігається з матрицею A_H) позицію на перетині рядка h(i) та стовпчика h(j). А оскільки a_h(i)h(j)^(H)=1, то у графі H існує ребро (h(i),h(j)). Міркуючи аналогічним чином, дістанемо: якщо (i,j)ÏE_G, то a_ij^(G)=0, але тоді a_h(i)h(j)^(H)=0, що означає (h(i),h(j)) ÏE_H. Отже, бієкція h має властивість (i,j)ÎE_GÛ(h(i),h(j))ÎE_H. Теорему доведено.

Теорема 5. Скінченні графи G та H ізоморфні тоді й тільки тоді, коли матрицю інцидентності одного з графів можна перетворити на матрицю інцидентності іншого графу за допомогою скінченної послідовності перестановок рядків та стовпчиків.

Доведення аналогічне доведенню теореми 4.

Розглянемо приклад. Нехай задано графи G₁=({1,2,3,4,5},{(1,2),(2,3), (2,4),(4,5)}) та G₂=({1,2,3,4,5},{(1,3),(2,4),(3,4),(4,5)}) (рис.8,а,б). Використаємо теорему 4 для доведення ізоморфності G₁ та G₂. Побудуємо матриці суміжності цих графів А₁ та А₂ (рис.9,а,б). Знайдемо таку скінченну послідовність узгоджених перестановок рядків та стовпчиків матриці суміжності графу G₂, що в результаті буде побудована матриця, що збігається з матрицею суміжності графу G₁.

 

а)	б)
Рис. 8

 

Зрозуміло, що коли матриці однакові, то у цих матрицях кількість одиниць у рядках з однаковими номерами однакова.

а)	б)
в)
г)
д)
Рис. 9

Ми бачимо, що у другому рядку матриці А₁ три одиниці, а у другому рядку матриці А₂ – тільки одна. Але у матриці А₂ є рядок, що містить три одиниці (це четвертий рядок). Отже, щоб кількість одиниць у других рядках обох матриць була однакова, треба поміняти місцями другий та четвертий рядок матриці А₂. Результат заміни зображено на рис. 9,в. Тепер поміняємо місцями другий та четвертий стовпчики останньої побудованої матриці й позначимо результат А₃ (рис. 9,в). Оскільки матриці А₁ та А₃ не однакові, продовжуємо перетворення. У матриці А₁ четвертий рядок містить дві одиниці, а у матриці А₃ – одну, але дві одиниці має третій рядок матриці А₃. Отже, поміняємо місцями третій та четвертий рядки матриці А₃ (результат – на рис. 9,г), а потім поміняємо місцями третій та четвертий стовпчики останньої побудованої матриці й результат позначимо А₄ (рис. 9,г). Порівняємо матриці А₁ та А₄. Вони різні, отже, продовжуємо перетворення. Ми бачимо, що у четвертому рядку матриці А₁ одиниці стоять на другому й п’ятому місцях, а у четвертому рядку матриці А₄ – на першому та другому місцях. Поміняємо місцями перший та п’ятий стовпчики матриці А₄, а потім у щойно побудованій матриці поміняємо місцями перший та п’ятий рядки й результат позначимо А₅ (рис. 9,д). Матриці А₁ та А₅ однакові. Отже, ми знайшли послідовність з трьох перетворень матриці А₂, кожне з яких є узгодженою перестановкою рядків та стовпчиків, й результатом цих перетворень є матриця А₅, що збігається з матрицею А₁. Таким чином, за теоремою 4, графи G₁ та G₂ ізоморфні.

 

Контрольні питання

1. Які графи називаються ізоморфними?

2. Що таке узгоджена перестановка рядків та стовпчиків матриці суміжності графу?

3. Які є необхідні умови ізоморфності графів?

4. Які є необхідні та достатні умови ізоморфності скінченних графів?

5. Які є способи перевірки ізоморфності: а) довільних графів,

б) скінченних графів?

 

Задачі та вправи

I. Побудувати такі неізоморфні графи G₁=(V₁,E₁) та G₂=(V₂,E₂), що |V₁|=|V₂|, |E₁|=|E₂|.

II. Визначити, які з пар графів, поданих на рис.10-13, є ізоморфними, а які – ні.

 

а)	б)		а)	б)
Рис. 10		Рис. 11

 

а)	б)		а)	б)
Рис. 12		Рис. 13

 

ІІІ. Перевірити, чи є ізоморфними графи G та Н. Якщо графи ізоморфні, довести це, використавши теореми 4 та 5.

1) G=({1,2,3,4,5,6},{(1,2),(1,3),(3,2),(2,4),(3,4),(4,1),(4,5),(5,6),(6,1),(6,2),(5,1),(5,2)}), H=({1,2,3,4,5,6},{(1,2),(1,3),(1,4),(1,5),(1,6),(2,5),(2,6),(3,5),(3,4),(4,5),(4,6),(5,6)});

2) G=({1,2,3,4,5,6,7},{(1,2),(1,3),(3,6),(6,4),(4,2),(4,7),(5,7),(2,5),(1,4),(6,7)}),

H=({a,b,c,d,e,f,g},{(a,b),(a,c),(a,d),(b,d),(b,e),(d,e),(e,g),(g,f),(f,c),(d,f)});

3) G=({1,2,3,4,5},{(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(1,4),(1,5)}),

H=({a,b,c,d,e},{(a,b),(a,c),(a,d),(b,c),(a,e),(b,d),(b,e),(d,e),(c,d)});

4) G=({1,2,3,4,5,6},{(1,2),(1,3),(2,4),(2,3),(4,1),(2,5),(2,6),(4,6),(3,6),(3,5),(1,5),(1,6)}),

H=({a,b,c,d,e,f},{(a,b),(a,c),(c,d),(c,b),(a,d),(d,e),(b,e),(b,f),(e,f),(f,a),(a,e),(b,d)});

5) G=({1,2,3,4,5,6,7},{(1,2),(1,3),(3,4),(3,5),(2,3),(2,4),(4,5),(5,6),(6,4),(6,7),(6,1), (1,7),(7,2),(7,5)}), H=({a,b,c,d,e,f,g},{(a,b),(a,e),(b,c),(c,f),(c,d),(d,a),(a,g),(g,d), (d,e),(e,b),(e,f),(f,g),(f,b),(g,c)});

6) G=({1,2,3,4,5,6,7,8},{(1,2),(2,3),(1,4),(3,5),(4,6),(4,2),(6,7),(7,8),(7,5),(8,5)}),

H=({a,b,c,d,e,f,g,h},{(a,b),(a,c),(b,d),(c,e),(e,f),(f,g),(d,g),(g,h),(h,d),(c,f)});

7) G=({1,2,3,4,5,6},{(4,2),(4,3),(2,1),(2,3),(4,1),(2,5),(2,6),(1,6),(3,6),(3,5),(4,5),(4,6)}),

H=({a,b,c,d,e,f},{(a,b),(a,c),(a,f),(b,f),(a,d),(a,e),(d,e),(b,e),(b,c),(e,c),(b,d),(f,d)});

8) G=({1,2,3,4,5,6},{(1,2),(2,3),(3,4),(4,5),(4,6),(5,6),(5,3),(5,2),(5,1),(6,1),(6,2),(6,3)}),

H=({a,b,c,d,e,f},{(a,b),(b,c),(c,a),(a,f),(d,e),(c,d),(b,f),(b,d),(a,e),(a,d),(d,f),(e,f)});

9) G=({1,2,3,4,5,6,7,8},{(1,2),(1,4),(1,5),(2,3),(2,6),(3,4),(3,7),(4,8),(5,6),(6,7), (7,8),(5,8)}),H=({1,2,3,4,5,6,7,8},{(1,2),(3,4),(5,6),(7,8),(8,6),(3,1),(1,7),(3,5),(6,4), (8,2), (4,2),(5,7)});

10) G=({1,2,3,4,5,6},{(1,2),(3,4),(1,5),(2,6),(3,5),(3,6),(1,6),(2,5)}), H=({1,2,3,4,5,6},{(1,2),(1,3),(1,5),(4,2),(4,6),(4,5),(2,6),(3,5)}).

ІV. Довести, що якщо графи G₁=(V₁,E₁) та G₂=(V₂,E₂) ізоморфні, то для будь-якого цілого невід’ємного числа k кількість вершин степеня k в обох графах однакова.

V. Довести, що якщо графи G₁=(V₁,E₁) та G₂=(V₂,E₂) ізоморфні, то для будь-якого цілого невід’ємного числа k кількість простих циклів довжини k в обох графах однакова.

VІ. Довести, що графи G₁=(V₁,E₁) та G₂=(V₂,E₂) ізоморфні тоді й тільки тоді, коли ізоморфні їх доповнення.

VІІ. Нехай на множині графів визначено бінарне відношення R: GRH Û графи G та H ізоморфні. Довести, що R є відношенням еквівалентності.