Изображение графа

Один и тот же граф может быть изображен по-разному.

Пример. На данных рисунках изображен один и тот же граф.

Для предварительной проверки совпадения графов необходимо проверить следующие условия:

1) одинаковое ли число вершин в графах;

2) одинаковое ли число ребер в графах;

3) одинаковое ли в графах число вершин имеют степень k .

Необходимым и достаточным условием совпадения графов является существование такого взаимно однозначного соответствия между ними, при котором две вершины в одном соединены ребром тогда, и только тогда, когда соединены ребром соответствующие вершины в другом.