Изоморфизм графов. Один и тот же граф геометрически можно изобразить различными способами

Один и тот же граф геометрически можно изобразить различными способами. Так, на рис.2.9 приведены изображения одного и того же графа. Такие графы называют изоморфными.

Рис. 2.9.

В связи с этим возникает следующая задача. Если имеется два изображения графов, то как узнать, не представляют ли они собой один и тот же граф? Ответить на этот вопрос сразу достаточно трудно. На практике обычно предварительно определяют некоторые параметры обоих графов. Такими параметрами могут быть число вершин, число ребер, число компонент связности, последовательность степеней вершин в убывающем порядке. Если какие-то из этих параметров у двух графов различны, то эти графы различны. Однако, если все параметры у двух графов совпали, то это не гарантирует, что графы изоморфны. Например, на рис. 2.10. приведены два графа, у которых все параметры совпадают, и тем не менее они различны.

Рис. 2.10.

Поиск по сайту: