Graf izomorfizma može se opisati kao graf u kojem jedan graf može imati više od jednog oblika. To znači da dva različita grafa mogu imati isti broj bridova, vrhova i istu povezanost bridova. Ove vrste grafova poznate su kao grafovi izomorfizma. Primjer grafa izomorfizma opisan je na sljedeći način:
Gornji grafikon sadrži sljedeće stvari:
- Isti graf je predstavljen u više od jednog oblika.
- Dakle, možemo reći da su ovi grafovi grafovi izomorfizma.
Uvjeti za izomorfizam grafova
Bilo koja dva grafa bit će poznata kao izomorfizam ako zadovoljavaju sljedeća četiri uvjeta:
- U zadanim grafovima bit će jednak broj vrhova.
- U zadanim grafovima bit će jednak broj bridova.
- U zadanim grafovima bit će jednaka količina nizova stupnjeva.
- Ako prvi graf tvori ciklus duljine k uz pomoć vrhova {v1, v2, v3, …. vk}, onda drugi graf također mora formirati isti ciklus iste duljine k uz pomoć vrhova {v1, v2, v3, …. vk}.
Napomena: Niz stupnjeva grafa može se opisati kao niz stupnjeva svih vrhova u rastućem redoslijedu.
Važne točke
- Da bi bilo koja dva grafa bila izomorfizam, neophodni uvjeti su gore definirana četiri uvjeta.
- Nije nužno da će gore definirani uvjeti biti dovoljni da se pokaže da su dani grafovi izomorfni.
- Ako dva grafa zadovoljavaju gore definirana četiri uvjeta, čak ni tada nije nužno da će grafovi sigurno biti izomorfni.
- Ako graf ne zadovoljava nijedan uvjet, onda možemo reći da grafovi sigurno nisu izomorfizam.
Dovoljni uvjeti za izomorfizam grafa
Ako želimo dokazati da su bilo koja dva grafa izomorfizam, postoje neki dovoljni uvjeti koji će nam dati garanciju da su ta dva grafa sigurno izomorfizam. Kada su dva grafa uspješno obrisana sva gornja četiri uvjeta, tek tada ćemo provjeriti te grafove na zadovoljavajuće uvjete, koji su opisani kako slijedi:
duljina niza bash
- Ako su komplementni grafovi oba grafa izomorfizam, onda će ti grafovi sigurno biti izomorfizam.
- Ako su susjedne matrice oba grafa iste, tada će ti grafovi biti izomorfizam.
- Ako su odgovarajući grafovi dva grafa dobiveni uz pomoć brisanja nekih vrhova jednog grafa, a njihove odgovarajuće slike u drugim slikama su izomorfizam, samo tada ti grafovi neće biti izomorfizam.
Kada dva grafa zadovoljavaju bilo koji od gornjih uvjeta, tada možemo reći da su ti grafovi sigurno izomorfni.
Primjeri izomorfizma grafova
Postoji mnogo primjera izomorfizma grafova, koji su opisani na sljedeći način:
Primjer 1:
U ovom smo primjeru pokazali jesu li sljedeći grafovi izomorfizam.
Riješenje: Za ovo ćemo provjeriti sva četiri uvjeta izomorfizma grafa, koji su opisani na sljedeći način:
Uvjet 1:
- U grafu 1 postoji ukupno 4 vrha, tj. G1 = 4.
- U grafu 2 postoji ukupno 4 vrha, tj. G2 = 4.
Ovdje,
U oba grafa G1 i G2 postoji jednak broj vrhova. Dakle, ovi grafovi zadovoljavaju uvjet 1. Sada ćemo provjeriti drugi uvjet.
Uvjet 2:
upotrebe operativnog sustava
- U grafu 1 postoji ukupno 5 bridova, tj. G1 = 5.
- U grafu 2 postoji ukupno 6 bridova, tj. G2 = 6.
Ovdje,
U oba grafa G1 i G2 nema jednak broj bridova. Dakle, ovi grafovi ne zadovoljavaju uvjet 2. Sada ne možemo provjeriti sve preostale uvjete.
Budući da ovi grafovi krše uvjet 2. Dakle, ovi grafovi nisu izomorfizam.
∴ Graf G1 i graf G2 nisu grafovi izomorfizma.
Primjer 2:
U ovom smo primjeru pokazali jesu li sljedeći grafovi izomorfizam.
Riješenje: Za ovo ćemo provjeriti sva četiri uvjeta izomorfizma grafa, koji su opisani na sljedeći način:
Uvjet 1:
- U grafu 1 postoji ukupno 4 vrha, tj. G1 = 4.
- U grafu 2 postoji ukupno 4 vrha, tj. G2 = 4.
- U grafu 3 postoji ukupno 4 vrhova, tj. G3 = 4.
Ovdje,
U svim grafovima G1, G2 i G3 postoji jednak broj vrhova. Dakle, ovi grafovi zadovoljavaju uvjet 1. Sada ćemo provjeriti drugi uvjet.
Uvjet 2:
- U grafu 1 postoji ukupno 5 bridova, tj. G1 = 5.
- U grafu 2 postoji ukupno 5 bridova, tj. G2 = 5.
- U grafu 3 postoji ukupno 4 bridova, tj. G2 = 4.
Ovdje,
- U oba grafa G1 i G2 postoji jednak broj bridova. Dakle, ovi grafovi zadovoljavaju uvjet 2.
- Ali u grafovima (G1, G2) i G3 nema jednak broj bridova. Dakle, grafovi (G1, G2) i G3 ne zadovoljavaju uvjet 2.
Budući da grafovi (G1, G2) i G3 krše uvjet 2. Dakle, možemo reći da ti grafovi nisu izomorfizam.
python postavka staze
∴ Graf G3 nije izomorfizam ni s grafom G1 ni s grafom G2.
Budući da grafovi G1 i G2 zadovoljavaju uvjet 2. Dakle, možemo reći da ovi grafovi mogu biti izomorfizam.
∴ Grafovi G1 i G2 mogu biti izomorfizam.
Sada ćemo provjeriti treći uvjet za grafove G1 i G2.
Uvjet 3:
- U grafu 1, stupanj niza s je {2, 2, 3, 3}, tj. G1 = {2, 2, 3, 3}.
- U grafu 2, stupanj niza s je {2, 2, 3, 3}, tj. G2 = {2, 2, 3, 3}.
Ovdje
U oba grafa G1 i G2 postoji jednak broj nizova stupnjeva. Dakle, ovi grafovi zadovoljavaju uvjet 3. Sada ćemo provjeriti četvrti uvjet.
Uvjet 4:
Graf G1 tvori ciklus duljine 3 uz pomoć vrhova {2, 3, 3}.
Graf G2 također tvori ciklus duljine 3 uz pomoć vrhova {2, 3, 3}.
Ovdje,
Pokazuje da oba grafa sadrže isti ciklus jer oba grafa G1 i G2 tvore ciklus duljine 3 uz pomoć vrhova {2, 3, 3}. Dakle, ovi grafovi zadovoljavaju uvjet 4.
Tako,
- Grafovi G1 i G2 zadovoljavaju sva četiri navedena uvjeta.
- Dakle, G1 i G2 mogu biti izomorfizam.
Sada ćemo provjeriti dovoljne uvjete da pokažemo da su grafovi G1 i G2 izomorfizam.
css tranzicijska neprozirnost
Provjera dovoljnih uvjeta
Kako smo naučili da ako su grafovi komplementa oba grafa izomorfizam, dva grafa će sigurno biti izomorfizam.
Stoga ćemo nacrtati komplementne grafove za G1 i G2, koji su opisani na sljedeći način:
U gornjim grafovima komplementa G1 i G2 možemo vidjeti da su oba grafa izomorfizam.
∴ Grafovi G1 i G2 su izomorfizam.
Primjer 3:
U ovom smo primjeru pokazali jesu li sljedeći grafovi izomorfizam.
Riješenje: Za ovo ćemo provjeriti sva četiri uvjeta izomorfizma grafa, koji su opisani na sljedeći način:
Uvjet 1:
- U grafu 1 postoji ukupno 8 vrhova, tj. G1 = 8.
- U grafu 2 postoji ukupno 8 vrhova, tj. G2 = 8.
Ovdje,
U oba grafa G1 i G2 postoji jednak broj vrhova. Dakle, ovi grafovi zadovoljavaju uvjet 1. Sada ćemo provjeriti drugi uvjet.
Uvjet 2:
- U grafu 1 ukupan broj bridova je 10, tj. G1 = 10.
- U grafu 2 ukupan broj bridova je 10, tj. G2 = 10.
Ovdje,
U oba grafa G1 i G2 postoji jednak broj bridova. Dakle, ovi grafovi zadovoljavaju uvjet 2. Sada ćemo provjeriti treći uvjet.
Uvjet 3:
- U grafu 1, stupanj niza s je {2, 2, 2, 2, 3, 3, 3, 3}, tj. G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- U grafu 2, stupanj niza s je {2, 2, 2, 2, 3, 3, 3, 3}, tj. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Ovdje
U oba grafa G1 i G2 postoji jednak broj nizova stupnjeva. Dakle, ovi grafovi zadovoljavaju uvjet 3. Sada ćemo provjeriti četvrti uvjet.
java sortiranje nizova
Uvjet 4:
- Graf G1 tvori ciklus duljine 4 uz pomoć vrhova stupnja 3.
- Graf G2 ne tvori ciklus duljine 4 uz pomoć vrhova jer vrhovi nisu susjedni.
Ovdje,
Oba grafa G1 i G2 ne tvore isti ciklus iste duljine. Dakle, ovi grafikoni krše uvjet 4.
Budući da grafovi G1 i G2 krše uvjet 4. Dakle, zbog kršenja uvjeta 4, ovi grafovi neće biti izomorfizam.
∴ Grafovi G1 i G2 nisu izomorfizam.