Graf $G$ jest izomorficzny z grafem $H$ jeśli istnieje takie, różnowartościowe i na, przyporządkowanie (bijekcja) wierzchołków grafu $H$ wierzchołkom grafu $G$, że jeśli jakieś dwa wierzchołki są połączone krawędzią w jednym z grafów, to odpowiadające im wierzchołki w drugim grafie również łączy krawędź.

Izomorfizm grafów zachowuje właściwie wszystkie interesujące własności, na przykład: liczbę wierzchołków, liczbę krawędzi, stopnie wierzchołków, spójność, planarność. Dlatego grafy izomorficzne zwykle utożsamia się.

??? Który z grafów B lub C jest izomorficzny z grafem A?

A:
B:
C:

---

Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej