Graf izomorfismu lze popsat jako graf, ve kterém může mít jeden graf více než jednu formu. To znamená, že dva různé grafy mohou mít stejný počet hran, vrcholů a stejnou konektivitu hran. Tyto typy grafů jsou známé jako grafy izomorfismu. Příklad grafu izomorfismu je popsán takto:
Výše uvedený graf obsahuje následující věci:
- Stejný graf je znázorněn ve více než jedné formě.
- Můžeme tedy říci, že tyto grafy jsou grafy izomorfismu.
Podmínky izomorfismu grafu
Jakékoli dva grafy budou známé jako izomorfismus, pokud splňují následující čtyři podmínky:
- V daných grafech bude stejný počet vrcholů.
- V daných grafech bude stejný počet hran.
- V daných grafech bude stejný počet stupňů.
- Pokud první graf tvoří cyklus délky k pomocí vrcholů {v1, v2, v3, …. vk}, pak musí další graf také vytvořit stejný cyklus o stejné délce k pomocí vrcholů {v1, v2, v3, …. vk}.
Poznámka: Stupňovou posloupnost grafu lze popsat jako posloupnost stupňů všech vrcholů ve vzestupném pořadí.
Důležité body
- Aby jakékoli dva grafy byly izomorfismem, nezbytnými podmínkami jsou výše definované čtyři podmínky.
- Není nutné, aby výše definované podmínky postačovaly k prokázání, že dané grafy jsou izomorfní.
- Pokud dva grafy splňují výše definované čtyři podmínky, ani potom není nutné, aby grafy byly jistě izomorfní.
- Pokud graf nesplňuje nějaké podmínky, pak můžeme říci, že grafy jistě nejsou izomorfismem.
Dostatečné podmínky pro izomorfismus grafu
Chceme-li dokázat, že jakékoli dva grafy jsou izomorfismus, existuje několik dostatečných podmínek, které nám zaručí, že tyto dva grafy jsou jistě izomorfismy. Když jsou dva grafy úspěšně vymazány všechny výše uvedené čtyři podmínky, teprve potom zkontrolujeme tyto grafy na dostatečné podmínky, které jsou popsány následovně:
příklad binárního vyhledávacího stromu
- Pokud jsou doplňkové grafy obou grafů izomorfismus, pak tyto grafy budou jistě izomorfismem.
- Pokud jsou sousední matice obou grafů stejné, pak tyto grafy budou izomorfismus.
- Pokud jsou odpovídající grafy dvou grafů získány pomocí smazání některých vrcholů jednoho grafu a jejich odpovídající obrázky v jiných obrázcích jsou izomorfismus, pak tyto grafy izomorfismem nebudou.
Když dva grafy splňují některou z výše uvedených podmínek, pak můžeme říci, že tyto grafy jsou jistě izomorfismy.
Příklady izomorfismu grafu
Existuje mnoho příkladů izomorfismu grafu, které jsou popsány takto:
Příklad 1:
V tomto příkladu jsme ukázali, zda jsou následující grafy izomorfismem.
Řešení: Za tímto účelem zkontrolujeme všechny čtyři podmínky izomorfismu grafu, které jsou popsány následovně:
Podmínka 1:
- V grafu 1 je celkem 4 počet vrcholů, tj. G1 = 4.
- V grafu 2 je celkem 4 počet vrcholů, tj. G2 = 4.
Tady,
V obou grafech G1 a G2 je stejný počet vrcholů. Tyto grafy tedy splňují podmínku 1. Nyní zkontrolujeme druhou podmínku.
Podmínka 2:
- V grafu 1 je celkem 5 hran, tj. G1 = 5.
- V grafu 2 je celkem 6 hran, tj. G2 = 6.
Tady,
V obou grafech G1 a G2 není stejný počet hran. Tyto grafy tedy nesplňují podmínku 2. Nyní nemůžeme zkontrolovat všechny zbývající podmínky.
Protože tyto grafy porušují podmínku 2. Tyto grafy tedy nejsou izomorfismem.
∴ Graf G1 a graf G2 nejsou grafy izomorfismu.
Příklad 2:
V tomto příkladu jsme ukázali, zda jsou následující grafy izomorfismem.
Řešení: Za tímto účelem zkontrolujeme všechny čtyři podmínky izomorfismu grafu, které jsou popsány následovně:
Podmínka 1:
- V grafu 1 je celkem 4 počet vrcholů, tj. G1 = 4.
- V grafu 2 je celkem 4 počet vrcholů, tj. G2 = 4.
- V grafu 3 je celkem 4 počet vrcholů, tj. G3 = 4.
Tady,
Ve všech grafech G1, G2 a G3 je stejný počet vrcholů. Tyto grafy tedy splňují podmínku 1. Nyní zkontrolujeme druhou podmínku.
Podmínka 2:
- V grafu 1 je celkem 5 hran, tj. G1 = 5.
- V grafu 2 je celkem 5 hran, tj. G2 = 5.
- V grafu 3 je celkem 4 počet hran, tj. G2 = 4.
Tady,
python nový řádek
- V obou grafech G1 a G2 je stejný počet hran. Tyto grafy tedy splňují podmínku 2.
- V grafech však není stejný počet hran (G1, G2) a G3. Takže grafy (G1, G2) a G3 nesplňují podmínku 2.
Protože grafy (G1, G2) a G3 porušují podmínku 2. Můžeme tedy říci, že tyto grafy nejsou izomorfismem.
∴ Graf G3 není izomorfismus s grafem G1 ani s grafem G2.
Protože grafy splňují G1 a G2 podmínku 2. Můžeme tedy říci, že tyto grafy mohou být izomorfismus.
∴ Grafy G1 a G2 mohou být izomorfismus.
Nyní zkontrolujeme třetí podmínku pro grafy G1 a G2.
Podmínka 3:
- V grafu 1 je stupeň posloupnosti s {2, 2, 3, 3}, tj. G1 = {2, 2, 3, 3}.
- V grafu 2 je stupeň posloupnosti s {2, 2, 3, 3}, tj. G2 = {2, 2, 3, 3}.
Tady
V obou grafech G1 a G2 je stejný počet sekvencí stupňů. Tyto grafy tedy splňují podmínku 3. Nyní zkontrolujeme čtvrtou podmínku.
Podmínka 4:
Graf G1 tvoří cyklus délky 3 pomocí vrcholů {2, 3, 3}.
Graf G2 také tvoří cyklus délky 3 pomocí vrcholů {2, 3, 3}.
Tady,
Ukazuje, že oba grafy obsahují stejný cyklus, protože oba grafy G1 a G2 tvoří cyklus délky 3 pomocí vrcholů {2, 3, 3}. Tyto grafy tedy splňují podmínku 4.
Tím pádem,
- Grafy G1 a G2 splňují všechny výše uvedené čtyři nezbytné podmínky.
- Takže G1 a G2 mohou být izomorfismus.
Nyní zkontrolujeme dostatečné podmínky, abychom ukázali, že grafy G1 a G2 jsou izomorfismus.
java datum na řetězec
Kontrola dostatečných podmínek
Jak jsme se naučili, pokud jsou grafy doplňku obou grafů izomorfismus, budou tyto dva grafy jistě izomorfismem.
Nakreslíme tedy doplňkové grafy G1 a G2, které jsou popsány následovně:
Ve výše uvedených doplňkových grafech G1 a G2 můžeme vidět, že oba grafy jsou izomorfismus.
∴ Grafy G1 a G2 jsou izomorfismus.
Příklad 3:
V tomto příkladu jsme ukázali, zda jsou následující grafy izomorfismem.
Řešení: Za tímto účelem zkontrolujeme všechny čtyři podmínky izomorfismu grafu, které jsou popsány následovně:
Podmínka 1:
- V grafu 1 je celkem 8 vrcholů, tj. G1 = 8.
- V grafu 2 je celkem 8 vrcholů, tj. G2 = 8.
Tady,
V obou grafech G1 a G2 je stejný počet vrcholů. Tyto grafy tedy splňují podmínku 1. Nyní zkontrolujeme druhou podmínku.
Podmínka 2:
- V grafu 1 je celkový počet hran 10, tj. G1 = 10.
- V grafu 2 je celkový počet hran 10, tj. G2 = 10.
Tady,
V obou grafech G1 a G2 je stejný počet hran. Tyto grafy tedy splňují podmínku 2. Nyní zkontrolujeme třetí podmínku.
Podmínka 3:
- V grafu 1 je stupeň posloupnosti s {2, 2, 2, 2, 3, 3, 3, 3}, tj. G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- V grafu 2 je stupeň posloupnosti s {2, 2, 2, 2, 3, 3, 3, 3}, tj. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Tady
V obou grafech G1 a G2 je stejný počet sekvencí stupňů. Tyto grafy tedy splňují podmínku 3. Nyní zkontrolujeme čtvrtou podmínku.
Podmínka 4:
- Graf G1 tvoří cyklus délky 4 pomocí vrcholů stupně 3.
- Graf G2 netvoří cyklus délky 4 pomocí vrcholů, protože vrcholy spolu nesousedí.
Tady,
int to char
Oba grafy G1 a G2 netvoří stejný cyklus se stejnou délkou. Takže tyto grafy porušují podmínku 4.
Protože grafy G1 a G2 porušují podmínku 4. Takže kvůli porušení podmínky 4 nebudou tyto grafy izomorfismem.
∴ Grafy G1 a G2 nejsou izomorfismus.