Skip to main content

Теория: 02 Степень вершины, чётность суммы степеней

Задание

Для графа, изображенного на рисунке, определите степени вершин. Найдите сумму степеней вершин.

Четна или нечётна найденная сумма?

Заполните таблицу:

ВершинаСтепень вершины
\(\displaystyle \bf A\)
\(\displaystyle \bf B\)
\(\displaystyle \bf C\)
\(\displaystyle \bf D\)
\(\displaystyle \bf E\)
Сумма степеней

 

Сумма степеней 

Решение

Требуется найти степени всех вершин графа, сумму степеней и определить, чётна или нечётна полученная сумма.

Определение

Степенью (порядком, валентностью) вершины графа называется количество рёбер, исходящих из этой вершины.

Найдём по рисунку степени вершин графа.

Степень вершины \(\displaystyle A\) равна \(\displaystyle \color{green}{\bf2}{\small.}\)

Видим, что из вершины \(\displaystyle A\) исходят \(\displaystyle \color{green}{\bf2}\) ребра.

Степень вершины \(\displaystyle B\) равна \(\displaystyle \color{green}{\bf2}{\small.}\)

Степень вершины \(\displaystyle C\) равна \(\displaystyle \color{green}{\bf1}{\small.}\)

Степень вершины \(\displaystyle D\) равна \(\displaystyle \color{green}{\bf3}{\small.}\)

Степень вершины \(\displaystyle E\) равна \(\displaystyle \color{green}{\bf2}{\small.}\)

Найдём сумму степеней вершин:

\(\displaystyle 2+2+3+1+3=10{\small.}\)

Заполним таблицу:

ВершинаСтепень вершины
\(\displaystyle \bf A\)\(\displaystyle 2\)
\(\displaystyle \bf B\)\(\displaystyle 2\)
\(\displaystyle \bf C\)\(\displaystyle 1\)
\(\displaystyle \bf D\)\(\displaystyle 3\)
\(\displaystyle \bf E\)\(\displaystyle 2\)
Сумма степеней\(\displaystyle \bf 10\)

 

Видим, что сумма степеней всех вершин графа чётна (\(\displaystyle 10\) – чётное число).

 

Ответ: сумма степеней всех вершин графа чётна.

Замечание / комментарий

Заметим, что каждое ребро графа имеет начало и конец.

Значит, при подсчёте степеней вершин каждое ребро подсчитано дважды:

  • для вершины, являющейся началом ребра,
  • для вершины, являющейся его концом.

Поэтому можем сделать вывод, что сумма степеней всех вершин графа всегда чётна.

Таким образом, будет верна теорема

Правило

Теорема о сумме степеней вершин

В любом графе сумма степеней всех вершин является чётным числом.