Graf izomorfizmu možno opísať ako graf, v ktorom môže mať jeden graf viac ako jednu formu. To znamená, že dva rôzne grafy môžu mať rovnaký počet hrán, vrcholov a rovnakú konektivitu hrán. Tieto typy grafov sú známe ako grafy izomorfizmu. Príklad grafu izomorfizmu je opísaný takto:
Vyššie uvedený graf obsahuje nasledujúce veci:
- Ten istý graf je znázornený vo viacerých formách.
- Môžeme teda povedať, že tieto grafy sú grafmi izomorfizmu.
Podmienky izomorfizmu grafu
Akékoľvek dva grafy budú známe ako izomorfizmus, ak spĺňajú nasledujúce štyri podmienky:
- V daných grafoch bude rovnaký počet vrcholov.
- V daných grafoch bude rovnaký počet hrán.
- V daných grafoch bude rovnaký počet stupňov.
- Ak prvý graf tvorí cyklus dĺžky k pomocou vrcholov {v1, v2, v3, …. vk}, potom musí ďalší graf vytvoriť rovnaký cyklus rovnakej dĺžky k pomocou vrcholov {v1, v2, v3, …. vk}.
Poznámka: Stupňovú postupnosť grafu možno opísať ako postupnosť stupňov všetkých vrcholov vo vzostupnom poradí.
Dôležité body
- Aby boli akékoľvek dva grafy izomorfizmom, nevyhnutnými podmienkami sú vyššie definované štyri podmienky.
- Nie je nutné, aby vyššie definované podmienky postačovali na preukázanie, že dané grafy sú izomorfné.
- Ak dva grafy spĺňajú vyššie definované štyri podmienky, ani potom nie je potrebné, aby grafy boli isomorfné.
- Ak graf nespĺňa žiadne podmienky, potom môžeme povedať, že grafy určite nie sú izomorfizmus.
Dostatočné podmienky pre izomorfizmus grafu
Ak chceme dokázať, že akékoľvek dva grafy sú izomorfizmus, existuje niekoľko dostatočných podmienok, ktoré nám zaručia, že tieto dva grafy sú isomorfizmus. Keď sú dva grafy úspešne vymazané všetky vyššie uvedené štyri podmienky, až potom skontrolujeme tieto grafy na dostatočné podmienky, ktoré sú popísané nasledovne:
- Ak sú doplnkové grafy oboch grafov izomorfizmus, potom tieto grafy budú určite izomorfizmom.
- Ak sú susedné matice oboch grafov rovnaké, potom tieto grafy budú izomorfizmus.
- Ak sa zodpovedajúce grafy dvoch grafov získajú pomocou vymazania niektorých vrcholov jedného grafu a ich zodpovedajúce obrázky na iných obrázkoch sú izomorfizmus, potom tieto grafy nebudú izomorfizmom.
Keď dva grafy spĺňajú niektorú z vyššie uvedených podmienok, potom môžeme povedať, že tieto grafy sú určite izomorfizmom.
Príklady izomorfizmu grafov
Existuje mnoho príkladov izomorfizmu grafov, ktoré sú opísané takto:
Príklad 1:
V tomto príklade sme ukázali, či sú nasledujúce grafy izomorfizmus.
Riešenie: Za týmto účelom skontrolujeme všetky štyri podmienky izomorfizmu grafu, ktoré sú opísané takto:
1. podmienka:
- V grafe 1 je celkovo 4 počet vrcholov, t.j. G1 = 4.
- V grafe 2 je celkovo 4 počet vrcholov, t.j. G2 = 4.
Tu,
V oboch grafoch G1 a G2 je rovnaký počet vrcholov. Takže tieto grafy spĺňajú podmienku 1. Teraz skontrolujeme druhú podmienku.
Podmienka 2:
- V grafe 1 je celkovo 5 hrán, t.j. G1 = 5.
- V grafe 2 je celkovo 6 hrán, t.j. G2 = 6.
Tu,
V oboch grafoch G1 a G2 nie je rovnaký počet hrán. Takže tieto grafy nespĺňajú podmienku 2. Teraz nemôžeme skontrolovať všetky zostávajúce podmienky.
Keďže tieto grafy porušujú podmienku 2. Takže tieto grafy nie sú izomorfizmom.
∴ Graf G1 a graf G2 nie sú grafy izomorfizmu.
Príklad 2:
V tomto príklade sme ukázali, či sú nasledujúce grafy izomorfizmus.
Riešenie: Za týmto účelom skontrolujeme všetky štyri podmienky izomorfizmu grafu, ktoré sú opísané nasledovne:
1. podmienka:
- V grafe 1 je celkovo 4 počet vrcholov, t.j. G1 = 4.
- V grafe 2 je celkovo 4 počet vrcholov, t.j. G2 = 4.
- V grafe 3 je celkovo 4 počet vrcholov, t.j. G3 = 4.
Tu,
Vo všetkých grafoch G1, G2 a G3 je rovnaký počet vrcholov. Takže tieto grafy spĺňajú podmienku 1. Teraz skontrolujeme druhú podmienku.
Podmienka 2:
- V grafe 1 je celkovo 5 hrán, t.j. G1 = 5.
- V grafe 2 je celkom 5 hrán, t.j. G2 = 5.
- V grafe 3 sú celkom 4 hrany, t.j. G2 = 4.
Tu,
- V oboch grafoch G1 a G2 je rovnaký počet hrán. Takže tieto grafy spĺňajú podmienku 2.
- V grafoch však nie je rovnaký počet hrán (G1, G2) a G3. Takže grafy (G1, G2) a G3 nespĺňajú podmienku 2.
Keďže grafy (G1, G2) a G3 porušujú podmienku 2. Môžeme teda povedať, že tieto grafy nie sú izomorfizmus.
∴ Graf G3 nie je izomorfizmus s grafom G1 ani s grafom G2.
Keďže grafy G1 a G2 spĺňajú podmienku 2. Môžeme teda povedať, že tieto grafy môžu byť izomorfizmus.
∴ Grafy G1 a G2 môžu byť izomorfizmus.
Teraz skontrolujeme tretiu podmienku pre grafy G1 a G2.
Podmienka 3:
- V grafe 1 je stupeň postupnosti s {2, 2, 3, 3}, t.j. G1 = {2, 2, 3, 3}.
- V grafe 2 je stupeň postupnosti s {2, 2, 3, 3}, t.j. G2 = {2, 2, 3, 3}.
Tu
V oboch grafoch G1 a G2 je rovnaký počet postupností stupňov. Takže tieto grafy spĺňajú podmienku 3. Teraz skontrolujeme štvrtú podmienku.
Podmienka 4:
Graf G1 tvorí cyklus dĺžky 3 pomocou vrcholov {2, 3, 3}.
Graf G2 tiež tvorí cyklus dĺžky 3 pomocou vrcholov {2, 3, 3}.
Tu,
Ukazuje, že oba grafy obsahujú rovnaký cyklus, pretože oba grafy G1 a G2 tvoria cyklus dĺžky 3 pomocou vrcholov {2, 3, 3}. Takže tieto grafy spĺňajú podmienku 4.
teda
- Grafy G1 a G2 spĺňajú všetky vyššie uvedené štyri nevyhnutné podmienky.
- Takže G1 a G2 môžu byť izomorfizmus.
Teraz skontrolujeme dostatočné podmienky, aby sme ukázali, že grafy G1 a G2 sú izomorfizmus.
Kontrola dostatočných podmienok
Ako sme sa dozvedeli, ak sú doplnkové grafy oboch grafov izomorfizmus, tieto dva grafy budú určite izomorfizmom.
Nakreslíme teda doplnkové grafy G1 a G2, ktoré sú popísané nasledovne:
Vo vyššie uvedených doplnkových grafoch G1 a G2 môžeme vidieť, že oba grafy sú izomorfizmus.
∴ Grafy G1 a G2 sú izomorfizmus.
Príklad 3:
V tomto príklade sme ukázali, či sú nasledujúce grafy izomorfizmus.
Riešenie: Za týmto účelom skontrolujeme všetky štyri podmienky izomorfizmu grafu, ktoré sú opísané takto:
1. podmienka:
- V grafe 1 je celkovo 8 vrcholov, t.j. G1 = 8.
- V grafe 2 je celkovo 8 vrcholov, t.j. G2 = 8.
Tu,
V oboch grafoch G1 a G2 je rovnaký počet vrcholov. Takže tieto grafy spĺňajú podmienku 1. Teraz skontrolujeme druhú podmienku.
Podmienka 2:
- V grafe 1 je celkový počet hrán 10, t.j. G1 = 10.
- V grafe 2 je celkový počet hrán 10, t.j. G2 = 10.
Tu,
V oboch grafoch G1 a G2 je rovnaký počet hrán. Takže tieto grafy spĺňajú podmienku 2. Teraz skontrolujeme tretiu podmienku.
otvorte ponuku nastavení
Podmienka 3:
- V grafe 1 je stupeň postupnosti s {2, 2, 2, 2, 3, 3, 3, 3}, t.j. G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- V grafe 2 je stupeň postupnosti s {2, 2, 2, 2, 3, 3, 3, 3}, t.j. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Tu
V oboch grafoch G1 a G2 je rovnaký počet postupností stupňov. Takže tieto grafy spĺňajú podmienku 3. Teraz skontrolujeme štvrtú podmienku.
Podmienka 4:
- Graf G1 tvorí cyklus dĺžky 4 pomocou vrcholov 3. stupňa.
- Graf G2 netvorí cyklus dĺžky 4 pomocou vrcholov, pretože vrcholy nie sú susediace.
Tu,
Grafy G1 a G2 netvoria rovnaký cyklus s rovnakou dĺžkou. Takže tieto grafy porušujú podmienku 4.
Keďže grafy G1 a G2 porušujú podmienku 4. Takže kvôli porušeniu podmienky 4 tieto grafy nebudú izomorfizmom.
∴ Grafy G1 a G2 nie sú izomorfizmus.