Графиката на изоморфизма може да се опише като графа, в която една графа може да има повече от една форма. Това означава, че две различни графики могат да имат еднакъв брой ръбове, върхове и еднаква свързаност на ръбовете. Тези типове графики са известни като графи на изоморфизъм. Примерът за графика на изоморфизма е описан по следния начин:
Горната графика съдържа следните неща:
- Една и съща графика е представена в повече от една форма.
- Следователно можем да кажем, че тези графики са графики на изоморфизъм.
Условия за изоморфизъм на графа
Всеки две графики ще бъдат известни като изоморфизъм, ако отговарят на следните четири условия:
- Ще има равен брой върхове в дадените графи.
- Ще има равен брой ребра в дадените графики.
- В дадените графики ще има еднакво количество степенна последователност.
- Ако първата графа образува цикъл с дължина 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:
В този пример показахме дали следните графики са изоморфни.
Решение: За целта ще проверим всичките четири условия на изоморфизъм на графиката, които са описани по следния начин:
java динамичен масив
Условие 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}.
Граф 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 не са изоморфизъм.