117 Одинаковы ли графы, изображённые на рисунке 20?

Решение:

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

Граф на рисунке 20, а) (слева):

• Вершин: 4
• Рёбер: 4
• Степени вершин: 2, 2, 2, 2

Граф на рисунке 20, а) (справа):

• Вершин: 4
• Рёбер: 4
• Степени вершин: 2, 2, 2, 2

Графы на рисунке 20, а) одинаковы.

Граф на рисунке 20, б) (слева):

• Вершин: 4
• Рёбер: 3
• Степени вершин: 1, 2, 2, 1

Граф на рисунке 20, б) (справа):

• Вершин: 4
• Рёбер: 3
• Степени вершин: 1, 2, 2, 1

Графы на рисунке 20, б) одинаковы.

Сравнение а) и б):

Графы в варианте а) отличаются от графов в варианте б) количеством рёбер и степенями вершин. Поэтому графы на рисунке 20 в целом не одинаковы.

Ответ: Нет, графы на рисунке 20 не одинаковы. Графы в пункте а) одинаковы, и графы в пункте б) одинаковы, но граф а) отличается от графа б).