Изоморфные графы

Определение 3.1. Графы G₁ = (S₁, U₁) и G₂ = (S₂, U₂) называются изоморфными (G₁ @ G₂), если между множествами их вершин S₁ и S₂ можно установить такое взаимно однозначное соответствие, при котором две произвольные вершины смежны в одном из графов тогда и только тогда, когда соответствующие им вершины смежны в другом графе. В случае орграфов ориентация дуг также должна быть одинаковой.

Очевидно, что отношение «быть изоморфными» на множестве всех графов является отношением эквивалентности. Следовательно, множество всех графов разбивается на классы попарно изоморфных графов.

Замечание 3.1. Диаграмма задает граф с точностью до изоморфизма. Это означает, что все различные диаграммы, содержащие одну и ту же информацию о вершинах и ребрах (дугах) графа и их взаимном расположении, являются изображениями одного и того же графа. Например, на рис. 8 представлено изображение одного и того же графа. 

Для того чтобы различать изоморфные графы, рассмотрим понятие помеченного графа.

Определение 3.2. Граф G порядка n называется помеченным, если его вершины занумерованы натуральными числами от 1 до n.

На рис. 9 изображены три разных помеченных графа порядка 3.

Таким образом, под непомеченым (или абстрактным)графом следует понимать класс изоморфных графов.

Замечание 3.2. Структура графа однозначно определяется его матрицей смежности вершин. 

Теорема 3.1. Графы изоморфны тогда и только тогда, когда их матрицы смежности вершин получаются друг из друга в результате последовательности одновременных перестановок строк и столбцов (одновременно с перестановкой i -й и j -й строк переставляются i -й и j -й столбцы). 

Из теоремы 3.1 следует, что ранги матриц смежности вершин изоморфных графов равны. Это позволяет ввести в рассмотрение следующее определение.

Определение 3.3. Рангом графа G (rank G) называется ранг его матрицы смежности вершин P(G).

Замечание 3.3. Структура мультиграфа однозначно определяется его матрицей инциденций. 

Теорема 3.2. Мультиграфы изоморфны тогда и только тогда, когда их матрицы инциденций получаются друг из друга в результате последовательности произвольных перестановок строк и столбцов.