Grafy izomorficzne

Grafy są izomorficzne, jeśli mają taką samą liczbę wierzchołków i „takie same połączenia”. Nie będziemy tu przytaczać dokładnej definicji matematycznej (można ją znaleźć np. tutaj), ale skupimy się na intuicyjnym zrozumieniu izomorfizmu grafów. Wyobraźmy sobie wierzchołki grafu jako zapałki, a krawędzie jako gumki rozciągnięte między nimi. Zapałki możemy przesuwać, ale graf będzie wciąż taki sam, ponieważ relacje pomiędzy połączeniami pozostają niezmienione. Izomorfizm grafów oznacza właśnie tego rodzaju „niezmienność”. Czy można tak długo przekształcać jeden graf, aż w końcu otrzymamy z niego inny?

Ćwiczenia dotyczące grafów izomorficznych są przydatne nie tyle ze względu na zrozumienie samego zagadnienia, ile jako trening abstrakcyjnego myślenia. Szukając grafów izomorficznych, musimy abstrahować od szczegółów (takich jak dokładny sposób narysowania krawędzi) i skupić się wyłącznie na istotnych relacjach (kto jest z kim połączony).