Решение

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

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

Значит, матрицы смежности изоморфных графов могут быть получены одна из другой перестановкой некоторых строк и столбцов.

Так, например, матрицы смежности изоморфных графов (задачи №4, рис.1 (а), (в)) имеют вид:

(а) и (в)

(см. задачу №7)

Если в матрице (в) поменять местами 2-й и 4-й столбец и 5-й с 6-м, а затем в полученной матрице поменять местами 2-ю и 4-ю, а также 5-ю и 6-ю строки, то мы получим матрицу (а).

Рассмотрим теперь матрицы смежности неизоморфных графов (задачи №5, рис.2(а) и (б)).

(см. задачу №7).

(а) (б)

У этих матриц совпадают соответственно строки 1-я, 2-я, 5-я и 6-я, а также столбцы с этими же номерами.

Третья строка матрицы (а) содержит две единицы во 2-м и 4-м столбцах, в матрице (б) две единицы содержатся в 4-й и 8-й строках, о в других столбцах. Поэтому, чтобы 3-я строка матрицы (а) равнялась одной из строк матрицы (б) необходимо менять местами столбцы матрицы (б); но при этом изменятся равные строки этих матриц. Таким образом, матрицу (а) нельзя получить из матрицы (б), меняя в ней местами столбцы и строки.

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

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

Таким образом, теория бинарных отношений и теория графов отличаются подходами, терминологией, но не содержанием. Тот факт, что в математике эти теории рассматриваются раздельно, объясняется отчасти привычкой и традициями, подобно тому, как в аналитической геометрии говорят о плоскости, а в алгебре этот объект называют линейным уравнением с тремя неизвестными. Однако, имеются отличия в методах этих теорий. Теория бинарных отношений рассматривается преимущественно на бесконечных множествах, теория графов – на конечных множествах.

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

№9. Описать в терминах теории графов бинарные отношения эквивалентности; частного порядка.