Граф изоморфизма се може описати као граф у коме један граф може имати више облика. То значи да два различита графа могу имати исти број ивица, врхова и исту повезаност ивица. Ови типови графова су познати као графови изоморфизма. Пример графа изоморфизма је описан на следећи начин:
Горњи графикон садржи следеће ствари:
- Исти графикон је представљен у више облика.
- Дакле, можемо рећи да су ови графови графови изоморфизма.
Услови за изоморфизам графова
Било која два графика биће позната као изоморфизам ако испуњавају следећа четири услова:
- У датим графовима ће бити једнак број темена.
- У датим графовима ће бити једнак број ивица.
- На датим графовима ће бити једнака количина низа степени.
- Ако први граф формира циклус дужине к уз помоћ темена {в1, в2, в3, …. вк}, онда други граф такође мора да формира исти циклус исте дужине к уз помоћ темена {в1, в2, в3, …. вк}.
Напомена: Низ степена графа може се описати као низ степена свих врхова у растућем редоследу.
Важне тачке
- Да би било која два графика била изоморфизам, неопходни услови су горе дефинисана четири услова.
- Није неопходно да ће горе дефинисани услови бити довољни да покажу да су дати графови изоморфни.
- Ако два графа задовољавају четири горе дефинисана услова, чак ни тада није неопходно да ће графови сигурно бити изоморфизовани.
- Ако граф не испуни ниједан услов, онда можемо рећи да графови сигурно нису изоморфизам.
Довољни услови за изоморфизам графа
Ако желимо да докажемо да су било која два графа изоморфизам, постоје неки довољни услови који нам гарантују да су два графа сигурно изоморфизам. Када су два графикона успешно обрисана сва горња четири услова, тек тада ћемо проверити те графиконе на довољне услове, који су описани на следећи начин:
- Ако су комплементарни графови оба графа изоморфизам, онда ће ови графови сигурно бити изоморфизам.
- Ако су суседне матрице оба графа исте, онда ће ови графови бити изоморфизам.
- Ако се одговарајући графови два графа добију уз помоћ брисања неких темена једног графа, а њихове одговарајуће слике на другим сликама су изоморфизам, само тада ови графови неће бити изоморфизам.
Када два графа задовоље било који од горе наведених услова, онда можемо рећи да су ти графови сигурно изоморфизам.
Примери изоморфизма графова
Постоји много примера изоморфизма графова, који су описани на следећи начин:
Пример 1:
У овом примеру смо показали да ли су следећи графови изоморфни.
Решење: За ово ћемо проверити сва четири услова изоморфизма графа, који су описани на следећи начин:
Услов 1:
- У графу 1 има укупно 4 темена, тј. Г1 = 4.
- У графу 2 има укупно 4 темена, тј. Г2 = 4.
овде,
У оба графа Г1 и Г2 постоји једнак број темена. Дакле, ови графови задовољавају услов 1. Сада ћемо проверити други услов.
пвр пуна форма
Услов 2:
- У графу 1 има укупно 5 ивица, тј. Г1 = 5.
- У графику 2 има укупно 6 ивица, односно Г2 = 6.
овде,
Не постоји једнак број ивица у оба графа Г1 и Г2. Дакле, ови графови не задовољавају услов 2. Сада не можемо да проверимо све преостале услове.
Пошто ови графови крше услов 2. Дакле, ови графови нису изоморфизам.
∴ Граф Г1 и граф Г2 нису графови изоморфизма.
Пример 2:
У овом примеру смо показали да ли су следећи графови изоморфни.
Решење: За ово ћемо проверити сва четири услова изоморфизма графа, који су описани на следећи начин:
Услов 1:
- У графу 1 има укупно 4 темена, тј. Г1 = 4.
- У графу 2 има укупно 4 темена, тј. Г2 = 4.
- У графу 3 има укупно 4 темена, тј. Г3 = 4.
овде,
У свим графовима Г1, Г2 и Г3 постоји једнак број темена. Дакле, ови графови задовољавају услов 1. Сада ћемо проверити други услов.
Услов 2:
израчунавање стажа у екцелу
- У графикону 1 има укупно 5 ивица, односно Г1 = 5.
- У графу 2 има укупно 5 ивица, тј. Г2 = 5.
- У графикону 3 има укупно 4 ивица, тј. Г2 = 4.
овде,
- У оба графа Г1 и Г2 постоји једнак број ивица. Дакле, ови графови задовољавају услов 2.
- Али у графовима (Г1, Г2) и Г3 нема једнак број ивица. Дакле, графови (Г1, Г2) и Г3 не задовољавају услов 2.
Пошто графови (Г1, Г2) и Г3 крше услов 2. Дакле, можемо рећи да ови графови нису изоморфизам.
како претворити стр у инт
∴ Граф Г3 није ни изоморфизам са графом Г1 ни са графом Г2.
Пошто графови, Г1 и Г2 задовољавају услов 2. Дакле, можемо рећи да ови графови могу бити изоморфизам.
∴ Графови Г1 и Г2 могу бити изоморфизам.
Сада ћемо проверити трећи услов за графове Г1 и Г2.
Услов 3:
- На графикону 1, степен низа с је {2, 2, 3, 3}, тј. Г1 = {2, 2, 3, 3}.
- На графикону 2, степен низа с је {2, 2, 3, 3}, тј. Г2 = {2, 2, 3, 3}.
Ево
На оба графа Г1 и Г2 постоји једнак број низова степена. Дакле, ови графови задовољавају услов 3. Сада ћемо проверити четврти услов.
Услов 4:
Граф Г1 формира циклус дужине 3 уз помоћ темена {2, 3, 3}.
Граф Г2 такође формира циклус дужине 3 уз помоћ темена {2, 3, 3}.
овде,
То показује да оба графа садрже исти циклус јер оба графа Г1 и Г2 формирају циклус дужине 3 уз помоћ темена {2, 3, 3}. Дакле, ови графови задовољавају услов 4.
Тако,
- Графикони Г1 и Г2 задовољавају сва горња четири неопходна услова.
- Дакле, Г1 и Г2 могу бити изоморфизам.
Сада ћемо проверити довољно услова да покажемо да су графови Г1 и Г2 изоморфизам.
Провера довољних услова
Како смо научили да ако су комплементарни графови оба графа изоморфизам, два графа ће сигурно бити изоморфизам.
Дакле, нацртаћемо графове комплемента Г1 и Г2, који су описани на следећи начин:
је кат тимпф адвокат
У горњим графовима комплемента Г1 и Г2 можемо видети да су оба графа изоморфизам.
∴ Графови Г1 и Г2 су изоморфизам.
Пример 3:
У овом примеру смо показали да ли су следећи графови изоморфни.
Решење: За ово ћемо проверити сва четири услова изоморфизма графа, који су описани на следећи начин:
Услов 1:
јава стринг цонцатенате
- У графу 1 има укупно 8 врхова, односно Г1 = 8.
- У графу 2 има укупно 8 врхова, односно Г2 = 8.
овде,
У оба графа Г1 и Г2 постоји једнак број темена. Дакле, ови графови задовољавају услов 1. Сада ћемо проверити други услов.
Услов 2:
- У графикону 1, укупан број ивица је 10, односно Г1 = 10.
- У графикону 2, укупан број ивица је 10, односно Г2 = 10.
овде,
У оба графа Г1 и Г2 постоји једнак број ивица. Дакле, ови графови задовољавају услов 2. Сада ћемо проверити трећи услов.
Услов 3:
- На графикону 1, степен низа с је {2, 2, 2, 2, 3, 3, 3, 3}, тј. Г1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- На графикону 2, степен низа с је {2, 2, 2, 2, 3, 3, 3, 3}, тј. Г2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Ево
На оба графа Г1 и Г2 постоји једнак број низова степена. Дакле, ови графови задовољавају услов 3. Сада ћемо проверити четврти услов.
Услов 4:
- Граф Г1 формира циклус дужине 4 уз помоћ врхова степена 3.
- Граф Г2 не формира циклус дужине 4 уз помоћ темена јер темена нису суседна.
овде,
И графови Г1 и Г2 не чине исти циклус исте дужине. Дакле, ови графови крше услов 4.
Пошто графови Г1 и Г2 крше услов 4. Дакле, због кршења услова 4, ови графови неће бити изоморфизам.
∴ Графови Г1 и Г2 нису изоморфизам.