Izomorfismus

Co se naučíš:

• Vysvětlit pojem izomorfismus grafů, uvést příklad.
• Umět použít vztah skóre a izomorfismu.
• Rozpoznat jednoduché izomorfní a neizomorfní grafy.
• Najít a popsat izomorfismus dvou grafů.

Všichni víme, co znamaná, když jsou dvě věci stejné. Nebo ne? Během našeho zkoumání grafů jsme několikrát narazili na otázky jednoznačnosti. Lze jednu situaci zachytit více grafy? Nebo jsou v nějakém smyslu všechny grafy téže situace stejné? Má daný graf jediný zápis (např. jedinou matici sousednosti), nebo lze najít více možností? Může jeden zápis reprezentovat více různých grafů? Přišel čas tohle téma konečně rozlousknout a výsledky chytře využít.

Poznámky k průběhu hodiny

Toto téma na ostatních přímo nezávisí. Lze jej tedy zařadit kdykoliv, když o něj studenti projeví zájem (položí související otázky o jednoznačnosti grafů apod.).

Na začátku hodiny studenty motivujeme připomenutím situací, kdy už jsme na podobné otázky narazili. K jejich prozkoumání si studenti vezmou skupinu grafů, které roztřídí podle toho, které vnímají jako stejné, resp. které jsou stejné „více“ a které „méně“.

Poté s pomocí učitele „stejnost“ jednotlivých grafů popíší podrobněji. Zjistí, v čem se izomorfní grafy liší a v čem nikoliv (a že se nazývají izomorfní). Pojem zadefinujeme, což nám umožní další přesnější zkoumání. Budeme řešit úlohu, jak poznat, kdy (ne)jsou dva grafy izomorfní. Studenti se mohou pokusit formulovat obecný návod. Pro lepší pochopení pojmu nabízíme několik příkladů s grafy i několik příkladů bez grafů, kde je izomorfismus nutno chápat přeneseně.

Izomorfismus jako takový nemá mnoho přímočarých využití v nějakých „každodenních situacích“. Jeho význam ve výuce je v problematizaci a následném zpřesnění intuitivního chápání totožnosti, rovnosti, shodnosti atd. Kromě toho dá příležitost k procvičení přesného vyjadřování a samozřejmě přispěje k hlubšímu pochopení grafů a jejich struktury. Izomorfismus ukazuje, kam až sahá abstrakce: nezáleží ani na označení konkrétních vrcholů, zásadní je struktura jejich spojení hranami.

Kromě uvedeného lze téma vnímat jako přípravu na koncept převodu úlohy na jinou úlohu (zde zatím jen naznačujeme, jak lze převádět řešení úloh s izomorfními grafy). Zjišťování, jestli jsou dva grafy izomorfní, přitom představuje příklad jedné z nejtěžších úloh v informatice, o nějž se budeme moci opřít později. Další důležitý aspekt je asymetrie v možných výsledcích. Pro potvrzení izomorfismu je třeba najít příslušné zobrazení. Vyloučení izomorfismu může být buď velmi snadné, pokud mají grafy např. různý počet vrcholů, nebo naopak velmi obtížné, když tato jednoduchá pravidla nepomohou a je nutno zkontrolovat všechna možná zobrazení. Další zajímavou vlastností úlohy je fakt, že zatímco hledání izomorfismu trvá dlouho, ověření jeho správnosti je snadné a rychlé.

Průzkum

Úloha: Které grafy jsou stejné?

Které z následujích grafů jsou stejné? Proč?

Grafy roztřiďte a vysvětlete, čím se grafy v jednotlivých skupinách shodují a čím se případně liší.

SEM PATŘÍ obrázky grafů

Lze použít i jiné grafy

Jsou-li k dispozici grafy z předchozích hodin, které už studenti znají (např. z úvodních úloh), lze je použít místo zde uvedených grafů a trochu tím práci studentů urychlit. Použité grafy by měly být bez ohodnocení vrcholů či hran a neorientované. Důležité je zahrnout několik skupin grafů a několik úrovní shody: stejné nakreslení, jiné nakreslení, jiné označení vrcholů, zcela odlišný graf — podobně, jako v uvedených příkladech. (ale asi neberte ohled na ohodnocení

Jestli chcete ušetřit čas a úsilí, zauvažujte, jak si mezi sebou práci rozdělit. uvědomte si tranzitivitu, budete mnohem dřív hotovi bonus: tomu se říká tranzitivita! dej další příklady tranzitivních relací jak strukturovat výsledky? budu mít stejné-isom-různé zkontrolujte výsledky aspoň jedním dalším člověkem je snazší prokázat odlišnost, nebo stejnost?

Proč izomorfismus a ne jednoduše ekvivalence?

Pojem izomorfismus vyjadřuje, že jsou grafy „v jistém smyslu“ stejné. Někomu může připadat divné, proč nepoužijeme pojem ekvivalence. Ten přeci intuitivně vnímáme také tak: ekvivalentní není přesně stejné, je ale v nějakém smyslu totožné.

Ekvivalence je ale obecnější pojem než izomorfismus. Z nějakého hlediska můžeme za ekvivalentní považovat grafy se stejným počtem vrcholů, nebo se stejnou délkou nejdelší cesty mezi dvěma vrcholy, nebo třeba právě grafy izomorfní. Záleží na tom, jakou úlohu právě řešíme. Izomorfismus je pouze speciálním případem ekvivalence, který zachovává strukturu grafu.

Obdobně jsou pojmy ekvivalence a izomorfismu zavedeny i na dalších strukturách. Ekvivalence vyjadřuje nějaký (libovolný) druh záměnnosti. Izomorfismus je právě taková záměnnost, která zachovává strukturu. V hodinách informatiky (popř. matematiky) tedy upřednostníme přesné vyjadřování (a rozlišování obou pojmů).

problematika zápisu: grafy jsou množinové, záis určuje pořadí