3 Как можно проверить, одинаковы два графа или нет?

Два графа считаются одинаковыми (изоморфными), если можно установить взаимно-однозначное соответствие между их вершинами так, чтобы сохранялась смежность (наличие ребра между двумя вершинами) и несмежность (отсутствие ребра). На практике, это можно проверить, сравнив количества вершин и рёбер, а также рассматривая их структуру. Если графы имеют одинаковое количество вершин и ребер, и структуру связей между вершинами, они, вероятно, одинаковы. Полезно рассмотреть степени вершин и их связи, т.к. изоморфные графы должны иметь одинаковые степени вершин и структуру.