Az izomorfizmus gráf olyan gráfként írható le, amelyben egyetlen gráfnak több alakja is lehet. Ez azt jelenti, hogy két különböző gráfnak ugyanannyi éle, csúcsa és azonos élösszeköthetősége lehet. Az ilyen típusú gráfokat izomorfizmus gráfoknak nevezzük. Az izomorfizmus gráf példáját a következőképpen írjuk le:
A fenti grafikon a következő dolgokat tartalmazza:
- Ugyanaz a gráf több formában is ábrázolható.
- Ezért azt mondhatjuk, hogy ezek a gráfok izomorfizmus gráfok.
A gráfizomorfizmus feltételei
Bármely két gráfot izomorfizmusnak nevezünk, ha teljesíti a következő négy feltételt:
- Az adott gráfokban azonos számú csúcs lesz.
- Az adott gráfokban egyenlő számú él lesz.
- A megadott grafikonokon azonos mennyiségű foksorozat lesz.
- Ha az első gráf a {v1, v2, v3, … csúcsok segítségével k hosszúságú ciklust alkot. vk}, akkor egy másik gráfnak is ugyanilyen k hosszúságú ciklust kell alkotnia a {v1, v2, v3, … csúcsok segítségével. vk}.
Megjegyzés: A gráf foksorozata leírható az összes csúcs fokszámának sorozataként növekvő sorrendben.
Fontos pontok
- Ahhoz, hogy bármely két gráf izomorfizmus legyen, a szükséges feltételek a fent meghatározott négy feltétel.
- Nem szükséges, hogy a fent meghatározott feltételek elegendőek legyenek annak bizonyításához, hogy az adott gráfok izomorfak.
- Ha két gráf teljesíti a fent definiált négy feltételt, akkor sem szükséges, hogy a gráfok biztosan izomorfikusak legyenek.
- Ha a gráf nem tesz eleget semmilyen feltételnek, akkor azt mondhatjuk, hogy a gráfok biztosan nem izomorfizmusok.
Elegendő feltételek a gráfizomorfizmushoz
Ha be akarjuk bizonyítani, hogy bármely két gráf izomorfizmus, akkor van néhány elégséges feltétel, amellyel garantálni tudjuk, hogy a két gráf biztosan izomorfizmus. Ha a két grafikonon a fenti négy feltételt sikeresen töröljük, csak akkor ellenőrizzük azokat a grafikonokat a megfelelő feltételekre, amelyeket az alábbiak szerint írunk le:
java összehasonlítja a karakterláncokat
- Ha mindkét gráf komplementgráfja izomorfizmus, akkor ezek a gráfok biztosan izomorfizmusok lesznek.
- Ha mindkét gráf szomszédos mátrixa azonos, akkor ezek a gráfok izomorfizmusok lesznek.
- Ha két gráf megfelelő gráfjait úgy kapjuk meg, hogy egy gráf néhány csúcsát töröljük, és más képeken a megfelelő képeik izomorfizmusok, csak akkor ezek a gráfok nem lesznek izomorfizmusok.
Ha két gráf teljesíti a fenti feltételek bármelyikét, akkor azt mondhatjuk, hogy ezek a gráfok biztosan izomorfizmusok.
Példák a gráfizomorfizmusra
Számos példa van a gráfizomorfizmusra, amelyeket a következőképpen írunk le:
1. példa:
Ebben a példában megmutattuk, hogy a következő gráfok izomorfizmusok-e.
Megoldás: Ehhez ellenőrizzük a gráfizomorfizmus mind a négy feltételét, amelyek leírása a következő:
1. feltétel:
- Az 1. gráfban összesen 4 csúcs van, azaz G1 = 4.
- A 2. gráfban összesen 4 csúcs van, azaz G2 = 4.
Itt,
A G1 és G2 gráfokban azonos számú csúcs található. Tehát ezek a grafikonok kielégítik az 1. feltételt. Most ellenőrizzük a második feltételt.
2. feltétel:
- Az 1. gráfban összesen 5 él van, azaz G1 = 5.
- A 2. gráfban összesen 6 él van, azaz G2 = 6.
Itt,
Nincs egyenlő számú él a G1 és G2 gráfokban. Tehát ezek a grafikonok nem teljesítik a 2. feltételt. Most nem tudjuk ellenőrizni az összes fennmaradó feltételt.
Mivel ezek a gráfok sértik a 2. feltételt. Tehát ezek a gráfok nem izomorfizmusok.
∴ A G1 gráf és a G2 gráf nem izomorfizmus gráfok.
2. példa:
Ebben a példában megmutattuk, hogy a következő gráfok izomorfizmusok-e.
Megoldás: Ehhez ellenőrizzük a gráfizomorfizmus mind a négy feltételét, amelyek leírása a következő:
1. feltétel:
- Az 1. gráfban összesen 4 csúcs van, azaz G1 = 4.
- A 2. gráfban összesen 4 csúcs van, azaz G2 = 4.
- A 3. gráfban összesen 4 csúcs van, azaz G3 = 4.
Itt,
Minden G1, G2 és G3 gráfban azonos számú csúcs található. Tehát ezek a grafikonok kielégítik az 1. feltételt. Most ellenőrizzük a második feltételt.
adatkapcsolati réteg protokollok
2. feltétel:
- Az 1. gráfban összesen 5 él van, azaz G1 = 5.
- A 2. gráfban összesen 5 él van, azaz G2 = 5.
- A 3. gráfban összesen 4 él van, azaz G2 = 4.
Itt,
- Mindkét G1 és G2 gráfban azonos számú él található. Tehát ezek a grafikonok teljesítik a 2. feltételt.
- De a gráfokban (G1, G2) és G3-ban nincs egyenlő számú él. Tehát a (G1, G2) és G3 grafikonok nem teljesítik a 2. feltételt.
Mivel a (G1, G2) és G3 gráfok sértik a 2. feltételt. Tehát elmondhatjuk, hogy ezek a gráfok nem izomorfizmusok.
∴ A G3 gráf nem izomorfizmus a G1 és a G2 gráfokkal.
Mivel a gráfok, G1 és G2 teljesítik a 2. feltételt. Tehát azt mondhatjuk, hogy ezek a gráfok izomorfizmusok.
∴ A G1 és G2 grafikonok izomorfizmusok lehetnek.
Most ellenőrizzük a harmadik feltételt a G1 és G2 gráfokhoz.
3. feltétel:
- Az 1. grafikonon az s sorozat mértéke {2, 2, 3, 3}, azaz G1 = {2, 2, 3, 3}.
- A 2. grafikonon az s sorozat mértéke {2, 2, 3, 3}, azaz G2 = {2, 2, 3, 3}.
Itt
Mind a G1, mind a G2 gráfban azonos számú foksorozat található. Tehát ezek a grafikonok kielégítik a 3. feltételt. Most a negyedik feltételt fogjuk ellenőrizni.
4. feltétel:
A G1 gráf a {2, 3, 3} csúcsok segítségével 3 hosszúságú ciklust alkot.
A G2 gráf a {2, 3, 3} csúcsok segítségével szintén 3 hosszúságú ciklust alkot.
Itt,
Megmutatja, hogy mindkét gráf ugyanazt a ciklust tartalmazza, mert mind a G1, mind a G2 gráf a {2, 3, 3} csúcsok segítségével 3 hosszúságú ciklust alkot. Tehát ezek a grafikonok teljesítik a 4. feltételt.
És így,
- A G1 és G2 grafikonok mind a négy szükséges feltételnek megfelelnek.
- Tehát G1 és G2 izomorfizmus lehet.
Most megvizsgálunk elegendő feltételeket annak bizonyítására, hogy a G1 és G2 gráf izomorfizmus.
Elegendő feltételek ellenőrzése
Mint megtanultuk, ha mindkét gráf komplementgráfja izomorfizmus, akkor a két gráf biztosan izomorfizmus lesz.
Tehát megrajzoljuk G1 és G2 komplement gráfjait, amelyek leírása a következő:
A fenti G1 és G2 komplement gráfokon láthatjuk, hogy mindkét gráf izomorfizmus.
∴ A G1 és G2 gráf izomorfizmus.
3. példa:
Ebben a példában megmutattuk, hogy a következő gráfok izomorfizmusok-e.
Megoldás: Ehhez ellenőrizzük a gráfizomorfizmus mind a négy feltételét, amelyek leírása a következő:
1. feltétel:
fájl megnyitása java-ban
- Az 1. gráfban összesen 8 csúcs van, azaz G1 = 8.
- A 2. gráfban összesen 8 csúcs van, azaz G2 = 8.
Itt,
A G1 és G2 gráfokban azonos számú csúcs található. Tehát ezek a grafikonok kielégítik az 1. feltételt. Most ellenőrizzük a második feltételt.
2. feltétel:
- Az 1. gráfban az élek száma összesen 10, azaz G1 = 10.
- A 2. gráfban az élek száma összesen 10, azaz G2 = 10.
Itt,
Mindkét G1 és G2 gráfban azonos számú él található. Tehát ezek a grafikonok kielégítik a 2. feltételt. Most ellenőrizzük a harmadik feltételt.
3. feltétel:
- Az 1. grafikonon az s sorozat mértéke {2, 2, 2, 2, 3, 3, 3, 3}, azaz G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- A 2. grafikonon az s sorozat mértéke {2, 2, 2, 2, 3, 3, 3, 3}, azaz G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Itt
Mind a G1, mind a G2 gráfban azonos számú foksorozat található. Tehát ezek a grafikonok kielégítik a 3. feltételt. Most a negyedik feltételt fogjuk ellenőrizni.
4. feltétel:
- A G1 gráf 3-as fokú csúcsok segítségével 4 hosszúságú ciklust alkot.
- A G2 gráf nem alkot 4 hosszúságú ciklust csúcsok segítségével, mert a csúcsok nem szomszédosak.
Itt,
A G1 és a G2 gráfok nem alkotnak azonos hosszúságú ciklust. Tehát ezek a grafikonok sértik a 4. feltételt.
Mivel a G1 és G2 gráfok sértik a 4. feltételt. Tehát a 4. feltétel megsértése miatt ezek a gráfok nem lesznek izomorfizmusok.
∴ A G1 és G2 gráfok nem izomorfizmusok.