Skip to main content

Теория: 03 Свойство суммы степеней вершин, сравнение графов

Задание

Являются ли графы, представленные на рисунке, одинаковыми?

 

Решение

Определение

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

При этом, чтобы графы были одинаковыми, должны совпадать:

  • число вершин;
  • число рёбер;
  • степени соответствующих вершин.

Если данные условия выполнены, то можно попытаться передвинуть вершины и проверить, являются ли графы одинаковыми.

Шаг 1. Для начала выпишем количество вершин и рёбер в каждом графе.

Для удобства обозначим вершины буквами и пронумеруем рёбра.

Первый граф содержит \(\displaystyle 5\) вершин и \(\displaystyle 7\) рёбер.

Второй граф содержит \(\displaystyle 5\) вершин и \(\displaystyle 7\) рёбер.

Так как количество вершин и рёбер в графах совпадает, продолжим сравнение.


Шаг 2. Составим таблицы степеней вершин для каждого графа.

  Первый графВторой граф
ВершинаСтепень
\(\displaystyle \bf А\)\(\displaystyle 3\)
\(\displaystyle \bf Б\)\(\displaystyle 3\)
\(\displaystyle \bf В\)\(\displaystyle 2\)
\(\displaystyle \bf Г\)\(\displaystyle 3\)
\(\displaystyle \bf Д\)\(\displaystyle 3\)
ВершинаСтепень
\(\displaystyle \bf Е\)\(\displaystyle 2\)
\(\displaystyle \bf Ж\)\(\displaystyle \color{red}{4}\)
\(\displaystyle \bf З\)\(\displaystyle 2\)
\(\displaystyle \bf И\)\(\displaystyle \color{red}{4}\)
\(\displaystyle \bf К\)\(\displaystyle 2\)

 

Легко заметить, что во втором графе две вершина (\(\displaystyle \bf Б\) и  \(\displaystyle \bf И\)) имеют степень \(\displaystyle \color{red}{4}{\small,}\) а в первом графе ни одна из вершин степень \(\displaystyle \color{red}{4}\)  не имеет.

Поэтому связать вершины рёбрами в одном порядке, то есть получить один граф из другого не удастся.

Таким образом, графы неодинаковы. 

Ответ: неодинаковы.