Graf izomorfizma lahko opišemo kot graf, v katerem ima lahko en sam graf več kot eno obliko. To pomeni, da imata lahko dva različna grafa enako število robov, vozlišč in isto povezljivost robov. Te vrste grafov so znane kot grafi izomorfizma. Primer grafa izomorfizma je opisan takole:
Zgornji graf vsebuje naslednje stvari:
- Isti graf je predstavljen v več kot eni obliki.
- Zato lahko rečemo, da so ti grafi izomorfizmi.
Pogoji za izomorfizem grafov
Katera koli dva grafa bosta znana kot izomorfizem, če izpolnjujeta naslednje štiri pogoje:
- V danih grafih bo enako število vozlišč.
- V danih grafih bo enako število robov.
- V danih grafih bo enako število stopenj.
- Če prvi graf tvori cikel dolžine k s pomočjo vozlišč {v1, v2, v3, …. vk}, potem mora tudi drug graf tvoriti isti cikel enake dolžine k s pomočjo vozlišč {v1, v2, v3, …. vk}.
Opomba: Zaporedje stopenj grafa je mogoče opisati kot zaporedje stopenj vseh vozlišč v naraščajočem vrstnem redu.
Pomembne točke
- Da bi bila katera koli dva grafa izomorfizem, so nujni pogoji štirje zgoraj definirani pogoji.
- Ni nujno, da bodo zgoraj definirani pogoji zadostovali za dokaz, da so podani grafi izomorfni.
- Če dva grafa izpolnjujeta zgoraj definirane štiri pogoje, tudi takrat ni nujno, da bosta grafa zagotovo izomorfna.
- Če graf ne izpolnjuje nobenega pogoja, potem lahko rečemo, da grafa zagotovo nista izomorfizem.
Zadostni pogoji za izomorfizem grafa
Če želimo dokazati, da sta katera koli dva grafa izomorfizem, obstaja nekaj zadostnih pogojev, ki nam bodo zagotovili, da sta grafa zagotovo izomorfizem. Ko bosta dva grafa uspešno počistila vse zgornje štiri pogoje, bomo šele takrat preverili te grafe glede zadostnih pogojev, ki so opisani kot sledi:
- Če sta komplementna grafa obeh grafov izomorfizem, potem bosta ta grafa zagotovo izomorfizem.
- Če sta sosednji matriki obeh grafov enaki, bosta ta grafa izomorfizem.
- Če sta ustrezna grafa dveh grafov pridobljena s pomočjo brisanja nekaterih vozlišč enega grafa in sta njuni ustrezni sliki v drugih slikah izomorfizem, le takrat ti grafi ne bodo izomorfizem.
Če dva grafa izpolnjujeta katerega od zgornjih pogojev, potem lahko rečemo, da sta ta grafa zagotovo izomorfna.
Primeri izomorfizma grafov
Obstaja veliko primerov izomorfizma grafov, ki so opisani na naslednji način:
Primer 1:
V tem primeru smo pokazali, ali so naslednji grafi izomorfizem.
binarno drevo proti bst
rešitev: Za to bomo preverili vse štiri pogoje izomorfizma grafa, ki so opisani takole:
Pogoj 1:
- V grafu 1 je skupno 4 oglišča, tj. G1 = 4.
- V grafu 2 je skupno 4 oglišča, tj. G2 = 4.
tukaj,
V obeh grafih G1 in G2 je enako število vozlišč. Ti grafi torej izpolnjujejo pogoj 1. Zdaj bomo preverili drugi pogoj.
2. pogoj:
- V grafu 1 je skupaj 5 robov, tj. G1 = 5.
- V grafu 2 je skupaj 6 robov, tj. G2 = 6.
tukaj,
V obeh grafih G1 in G2 ni enakega števila robov. Torej ti grafi ne izpolnjujejo pogoja 2. Zdaj ne moremo preveriti vseh preostalih pogojev.
Ker ti grafi kršijo pogoj 2. Torej ti grafi niso izomorfizem.
∴ Graf G1 in graf G2 nista grafa izomorfizma.
Primer 2:
V tem primeru smo pokazali, ali so naslednji grafi izomorfizem.
rešitev: Za to bomo preverili vse štiri pogoje izomorfizma grafa, ki so opisani takole:
Pogoj 1:
- V grafu 1 je skupno 4 oglišča, tj. G1 = 4.
- V grafu 2 je skupno 4 oglišča, tj. G2 = 4.
- V grafu 3 je skupno 4 oglišča, tj. G3 = 4.
tukaj,
V vseh grafih G1, G2 in G3 je enako število vozlišč. Ti grafi torej izpolnjujejo pogoj 1. Zdaj bomo preverili drugi pogoj.
vprašanja za razgovor v jeziku java
2. pogoj:
- V grafu 1 je skupaj 5 robov, tj. G1 = 5.
- V grafu 2 je skupaj 5 robov, tj. G2 = 5.
- V grafu 3 je skupno 4 robov, tj. G2 = 4.
tukaj,
- V obeh grafih G1 in G2 je enako število robov. Ti grafi torej izpolnjujejo pogoj 2.
- Toda v grafih (G1, G2) in G3 ni enakega števila robov. Torej grafa (G1, G2) in G3 ne izpolnjujeta pogoja 2.
Ker grafa (G1, G2) in G3 kršita pogoj 2. Torej lahko rečemo, da ti grafi niso izomorfizem.
instanciranje jave
∴ Graf G3 ni niti izomorfizem z grafom G1 niti z grafom G2.
Ker grafa G1 in G2 izpolnjujeta pogoj 2. Torej lahko rečemo, da sta ta grafa lahko izomorfizem.
∴ Grafa G1 in G2 sta lahko izomorfizem.
Zdaj bomo preverili tretji pogoj za grafa G1 in G2.
Pogoj 3:
- V grafu 1 je stopnja zaporedja s {2, 2, 3, 3}, tj. G1 = {2, 2, 3, 3}.
- V grafu 2 je stopnja zaporedja s {2, 2, 3, 3}, tj. G2 = {2, 2, 3, 3}.
Tukaj
V obeh grafih G1 in G2 je enako število stopinjskih zaporedij. Ti grafi torej izpolnjujejo pogoj 3. Zdaj bomo preverili četrti pogoj.
Pogoj 4:
Graf G1 tvori cikel dolžine 3 s pomočjo vozlišč {2, 3, 3}.
Tudi graf G2 tvori cikel dolžine 3 s pomočjo vozlišč {2, 3, 3}.
tukaj,
Kaže, da oba grafa vsebujeta isti cikel, ker oba grafa G1 in G2 tvorita cikel dolžine 3 s pomočjo vozlišč {2, 3, 3}. Ti grafi torej izpolnjujejo pogoj 4.
torej
- Grafa G1 in G2 izpolnjujeta vse zgornje štiri potrebne pogoje.
- Torej sta lahko G1 in G2 izomorfizem.
Zdaj bomo preverili zadostne pogoje, da pokažemo, da sta grafa G1 in G2 izomorfizem.
Preverjanje zadostnih pogojev
Kot smo se naučili, če sta komplementna grafa obeh grafov izomorfizem, bosta oba grafa zagotovo izomorfizem.
Tako bomo narisali komplementna grafa G1 in G2, ki sta opisana takole:
V zgornjih grafih komplementa G1 in G2 lahko vidimo, da sta oba grafa izomorfizem.
∴ Grafa G1 in G2 sta izomorfizem.
Primer 3:
V tem primeru smo pokazali, ali so naslednji grafi izomorfizem.
sklearn ocena natančnosti
rešitev: Za to bomo preverili vse štiri pogoje izomorfizma grafa, ki so opisani takole:
Pogoj 1:
- V grafu 1 je skupno 8 točk, tj. G1 = 8.
- V grafu 2 je skupno 8 točk, tj. G2 = 8.
tukaj,
V obeh grafih G1 in G2 je enako število vozlišč. Ti grafi torej izpolnjujejo pogoj 1. Zdaj bomo preverili drugi pogoj.
2. pogoj:
nadrejeni jquery
- V grafu 1 je skupno število robov 10, tj. G1 = 10.
- V grafu 2 je skupno število robov 10, tj. G2 = 10.
tukaj,
V obeh grafih G1 in G2 je enako število robov. Ti grafi torej izpolnjujejo pogoj 2. Zdaj bomo preverili tretji pogoj.
Pogoj 3:
- V grafu 1 je stopnja zaporedja s {2, 2, 2, 2, 3, 3, 3, 3}, tj. G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- V grafu 2 je stopnja zaporedja s {2, 2, 2, 2, 3, 3, 3, 3}, tj. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Tukaj
V obeh grafih G1 in G2 je enako število stopinjskih zaporedij. Ti grafi torej izpolnjujejo pogoj 3. Zdaj bomo preverili četrti pogoj.
Pogoj 4:
- Graf G1 tvori cikel dolžine 4 s pomočjo oglišč stopnje 3.
- Graf G2 ne tvori cikla dolžine 4 s pomočjo oglišč, ker oglišča niso sosednja.
tukaj,
Grafa G1 in G2 ne tvorita istega cikla z enako dolžino. Torej ti grafi kršijo pogoj 4.
Ker grafa G1 in G2 kršita pogoj 4. Torej zaradi kršitve pogoja 4 ta grafa ne bosta izomorfizem.
∴ Grafa G1 in G2 nista izomorfizem.