Izomorfizmo grafą galima apibūdinti kaip grafą, kuriame vienas grafikas gali turėti daugiau nei vieną formą. Tai reiškia, kad dviejuose skirtinguose grafikuose gali būti tiek pat briaunų, viršūnių ir tų pačių kraštų jungčių. Šie grafikų tipai yra žinomi kaip izomorfizmo grafikai. Izomorfizmo grafiko pavyzdys aprašytas taip:
Aukščiau pateiktoje diagramoje yra šie dalykai:
- Tas pats grafikas vaizduojamas daugiau nei viena forma.
- Taigi galime pasakyti, kad šie grafikai yra izomorfizmo grafikai.
Grafo izomorfizmo sąlygos
Bet kurie du grafikai bus žinomi kaip izomorfizmas, jei jie atitinka šias keturias sąlygas:
- Pateiktuose grafikuose bus vienodas viršūnių skaičius.
- Pateiktuose grafikuose bus vienodas briaunų skaičius.
- Pateiktuose grafikuose bus vienodas laipsnio sekos kiekis.
- Jei pirmasis grafas viršūnių {v1, v2, v3, … pagalba sudaro k ilgio ciklą. vk}, tada kitas grafikas taip pat turi sudaryti tą patį tokio pat ilgio k ciklą, naudodamas viršūnes {v1, v2, v3, …. vk}.
Pastaba: Grafo laipsnio seka gali būti apibūdinta kaip visų viršūnių laipsnių seka didėjančia tvarka.
Svarbūs punktai
- Kad bet kurie du grafikai būtų izomorfizmas, būtinos sąlygos yra aukščiau apibrėžtos keturios sąlygos.
- Nebūtina, kad aukščiau apibrėžtų sąlygų pakaktų parodyti, kad pateikti grafikai yra izomorfiniai.
- Jei du grafikai tenkina aukščiau nurodytas keturias sąlygas, net ir tada nebūtina, kad grafikai būtų tikrai izomorfizmo.
- Jei grafikas netenkina jokių sąlygų, galime sakyti, kad grafikai tikrai nėra izomorfizmas.
Pakankamos grafiko izomorfizmo sąlygos
Jei norime įrodyti, kad bet kurie du grafikai yra izomorfizmas, yra keletas pakankamų sąlygų, kurias pateiksime mums garantija, kad du grafikai tikrai yra izomorfizmas. Kai abi grafikos bus sėkmingai išvalytos visos aukščiau nurodytos keturios sąlygos, tik tada patikrinsime tuos grafikus iki pakankamų sąlygų, kurios aprašytos taip:
- Jei abiejų grafikų komplemento grafikai yra izomorfizmas, tada šie grafikai tikrai bus izomorfizmas.
- Jei gretimos abiejų grafikų matricos yra vienodos, tada šie grafikai bus izomorfizmas.
- Jei dviejų grafų atitinkami grafikai gaunami išbraukiant kai kurias vieno grafo viršūnes, o juos atitinkantys vaizdai kituose vaizduose yra izomorfizmas, tik tada šie grafikai nebus izomorfizmas.
Kai du grafikai atitinka bet kurią iš pirmiau minėtų sąlygų, galime sakyti, kad tie grafikai tikrai yra izomorfizmas.
Grafo izomorfizmo pavyzdžiai
Yra daug grafų izomorfizmo pavyzdžių, kurie apibūdinami taip:
1 pavyzdys:
Šiame pavyzdyje parodėme, ar šie grafikai yra izomorfizmas.
lygus metodui java
Sprendimas: Tam patikrinsime visas keturias grafo izomorfizmo sąlygas, kurios aprašytos taip:
1 sąlyga:
- 1 diagramoje iš viso yra 4 viršūnių skaičius, ty G1 = 4.
- 2 grafike iš viso yra 4 viršūnių skaičius, ty G2 = 4.
Čia
Tiek G1, tiek G2 grafuose yra vienodas viršūnių skaičius. Taigi šie grafikai tenkina 1 sąlygą. Dabar patikrinsime antrąją sąlygą.
2 sąlyga:
- 1 diagramoje iš viso yra 5 briaunų skaičius, ty G1 = 5.
- 2 diagramoje iš viso yra 6 briaunų skaičius, ty G2 = 6.
Čia
Grafuose G1 ir G2 nėra vienodo briaunų skaičiaus. Taigi šie grafikai netenkina 2 sąlygos. Dabar negalime patikrinti visų likusių sąlygų.
Kadangi šie grafikai pažeidžia 2 sąlygą. Taigi šie grafikai nėra izomorfizmas.
∴ Grafas G1 ir grafikas G2 nėra izomorfizmo grafikai.
2 pavyzdys:
Šiame pavyzdyje parodėme, ar šie grafikai yra izomorfizmas.
Sprendimas: Tam patikrinsime visas keturias grafo izomorfizmo sąlygas, kurios aprašytos taip:
base64 dekodavimas js
1 sąlyga:
- 1 diagramoje iš viso yra 4 viršūnių skaičius, ty G1 = 4.
- 2 grafike iš viso yra 4 viršūnių skaičius, ty G2 = 4.
- 3 diagramoje iš viso yra 4 viršūnių skaičius, ty G3 = 4.
Čia
Visuose grafuose G1, G2 ir G3 yra vienodas viršūnių skaičius. Taigi šie grafikai tenkina 1 sąlygą. Dabar patikrinsime antrąją sąlygą.
2 sąlyga:
- 1 diagramoje iš viso yra 5 briaunų skaičius, ty G1 = 5.
- 2 diagramoje iš viso yra 5 briaunų skaičius, ty G2 = 5.
- 3 diagramoje iš viso yra 4 briaunų skaičius, ty G2 = 4.
Čia
- Grafuose G1 ir G2 yra vienodas briaunų skaičius. Taigi šie grafikai atitinka 2 sąlygą.
- Tačiau grafuose (G1, G2) ir G3 nėra vienodo briaunų skaičiaus. Taigi grafikai (G1, G2) ir G3 neatitinka 2 sąlygos.
Kadangi grafikai (G1, G2) ir G3 pažeidžia 2 sąlygą. Taigi galime teigti, kad šie grafikai nėra izomorfizmas.
∴ Grafas G3 nėra nei izomorfizmas su grafiku G1, nei su grafiku G2.
Kadangi grafikai, G1 ir G2 tenkina 2 sąlygą. Taigi galime teigti, kad šie grafikai gali būti izomorfizmas.
∴ Grafikai G1 ir G2 gali būti izomorfizmas.
Dabar patikrinsime trečiąją grafikų G1 ir G2 sąlygą.
3 sąlyga:
- 1 diagramoje sekos s laipsnis yra {2, 2, 3, 3}, t.y. G1 = {2, 2, 3, 3}.
- 2 diagramoje sekos s laipsnis yra {2, 2, 3, 3}, t.y. G2 = {2, 2, 3, 3}.
čia
Grafikuose G1 ir G2 yra vienodas laipsnių sekų skaičius. Taigi šie grafikai tenkina 3 sąlygą. Dabar patikrinsime ketvirtąją sąlygą.
4 sąlyga:
Grafas G1 viršūnių {2, 3, 3} pagalba sudaro 3 ilgio ciklą.
Grafas G2 viršūnių {2, 3, 3} pagalba taip pat sudaro 3 ilgio ciklą.
Čia
Tai rodo, kad abiejuose grafikuose yra tas pats ciklas, nes abu grafikai G1 ir G2 viršūnių {2, 3, 3} pagalba sudaro 3 ilgio ciklą. Taigi šie grafikai atitinka 4 sąlygą.
Taigi,
- Grafikai G1 ir G2 atitinka visas pirmiau minėtas keturias būtinas sąlygas.
- Taigi G1 ir G2 gali būti izomorfizmas.
Dabar patikrinsime, ar yra pakankamai sąlygų, kad parodytume, jog grafikai G1 ir G2 yra izomorfizmas.
np.unikali
Pakankamų sąlygų tikrinimas
Kaip mes sužinojome, kad jei abiejų grafikų komplemento grafikai yra izomorfizmas, abu grafikai tikrai bus izomorfizmas.
Taigi nubraižysime G1 ir G2 komplemento grafikus, kurie aprašomi taip:
Aukščiau pateiktuose G1 ir G2 komplemento grafikuose matome, kad abu grafikai yra izomorfiniai.
∴ Grafikai G1 ir G2 yra izomorfizmas.
3 pavyzdys:
Šiame pavyzdyje parodėme, ar šie grafikai yra izomorfizmas.
Sprendimas: Tam patikrinsime visas keturias grafo izomorfizmo sąlygas, kurios aprašytos taip:
1 sąlyga:
- 1 grafike iš viso yra 8 viršūnių skaičius, ty G1 = 8.
- 2 grafike iš viso yra 8 viršūnių skaičius, ty G2 = 8.
Čia
Tiek G1, tiek G2 grafuose yra vienodas viršūnių skaičius. Taigi šie grafikai tenkina 1 sąlygą. Dabar patikrinsime antrąją sąlygą.
java sąrašus
2 sąlyga:
- 1 diagramoje bendras briaunų skaičius yra 10, ty G1 = 10.
- 2 diagramoje bendras briaunų skaičius yra 10, ty G2 = 10.
Čia
Grafuose G1 ir G2 yra vienodas briaunų skaičius. Taigi šie grafikai tenkina 2 sąlygą. Dabar patikrinsime trečiąją sąlygą.
3 sąlyga:
- 1 diagramoje sekos s laipsnis yra {2, 2, 2, 2, 3, 3, 3, 3}, t. y. G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- 2 diagramoje sekos s laipsnis yra {2, 2, 2, 2, 3, 3, 3, 3}, t. y. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
čia
Grafikuose G1 ir G2 yra vienodas laipsnių sekų skaičius. Taigi šie grafikai tenkina 3 sąlygą. Dabar patikrinsime ketvirtąją sąlygą.
4 sąlyga:
- Grafas G1 3 laipsnio viršūnių pagalba sudaro 4 ilgio ciklą.
- Grafas G2 viršūnių pagalba nesudaro 4 ilgio ciklo, nes viršūnės nėra gretimos.
Čia
Abu grafikai G1 ir G2 nesudaro to paties ciklo vienodo ilgio. Taigi šios diagramos pažeidžia 4 sąlygą.
Kadangi grafikai G1 ir G2 pažeidžia 4 sąlygą. Taigi dėl 4 sąlygos pažeidimo šie grafikai nebus izomorfizmas.
∴ Grafikai G1 ir G2 nėra izomorfizmas.