Oto dodatkowe informacje na temat grafów, potrzebne w bardziej skomplikowanych algorytmach.
Kilka definicji:
Stopień wierzchołka - to liczba krawędzi do niego przyległych
Graf regularny - to graf, w którym każdy wierzchołek ma taki sam stopień
Graf planarny - to graf, który można przedstawić na płaszczyźnie tak, by żadne dwie krawędzie się nie przecinały
f-graf - to graf z ograniczonym stopniem wierzchołka, tzn. jego stopień nie może być większy niż f
Graf prosty - to graf bez pętli własnych i krawędzi równoległych
Niezmiennik grafu - to liczba lub ciąg liczb, który zależy tylko od struktury grafu a nie od sposobu jego poetykietowania (np. liczba wierzchołków, liczba krawędzi)
Liczba chromatyczna grafu - to najmniejsza liczba kolorów potrzebnych do pokolorowania wierzchołków grafu tak, by żadne dwa przyległe wierzchołki nie były tego samego koloru
Przykładu do powyższych definicji:

stopień wierzchołka 1=2, wierzchołka 2=3, graf planarny, f-graf dla f=3

graf 2-regularny, planarny

graf planarny, f-graf dla f=4

graf planarny, liczba chromatyczna wynosi 3

Teraz przejdźmy do bardzo ważnego problemu: generowania grafów losowych.
Istnieje kilka modeli grafów losowych, omówimy najważnejsze:

• model G(n,p) - n (liczba wierzchołków) jest dana, p jest tzw. prawdopodobieństwem krawędziowym (0<=p<=1). Liczba p jest określona dla każdej krawędzi, określa ono prawdzopodobieństwo, że dana krawędź znajdzie się w grafie
• model G(n,k) - n jest dana, ze zbioru wszystkich możliwych krawędzi są losowane kolejne krawędzie, lecz tu, w odróżnieniu do poprzedniego modelu, z jednakowym prawdopodobieństwem
• model G(n,f) - n jest dana, f oznacza maksymalny stopień wierzchołka, którego nie można przekroczyć.

Przy losowaniu grafów stosuje się często tzw. metodę przesiewania (lub sito, wykorzystane przez Eratostenesa przy wyznaczaniu liczb pierwszych). Dzieli się ona na kilka części:

1. wybór odpowiedniego generatora (zgodnie z powyższymi modelami)
2. każdy wygenerowany graf jest weryfikowany, czy spełnia założenia wybranego modelu (np. czy jego największy stopień nie jest większy niż f), grafy które ich nie spełniają są odrzucane, reszta jest zapisywana np. w pliku
3. po zakończeniu generowania w pliku znajdują się grafy spełniające założenia danego modelu. Należy jeszcze sprawdzić, czy grafy te są różne, tzn. czy nie ma wśród nich grafów izomorficznych

Testowanie izomorfizmu jest problemem trudnym. Nie ma żadnego szybkiego algorytmu sprawdzającego, czy dwa grafy są izomorficzne. Powodem tego jest wiele kryteriów izomorfizmu grafów, jeżeli dane grafy nie spełniają jekiegoś kryterium, należy przejść do kolejnego (co zwiększa koszt obliczeń).
Kryterium izomorfizmu grafów:

1. jednakowa liczba wierzchołków
2. jednakowa liczba krawędzi
3. jednakowy ciąg stopni wierzchołków
4. jendakowe ciągi stopni wierzchołków dla sąsiadów
5. jednakowa liczba trójkątów (cykli o długości 3)
6. tworzenie macierzy odległości

Pierwsze dwa kroki można wykonać wprawdzie w czasie Θ(n), lecz w punkcie 5 czas zaczyna gwałtownie wzrastać.