Skip to main content

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

Задание

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

Сколько рёбер в данном графе?

Во сколько раз сумма степеней вершин больше количества рёбер?

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

ВершинаСтепень вершины
\(\displaystyle \bf А\)
\(\displaystyle \bf Б\)
\(\displaystyle \bf В\)
\(\displaystyle \bf Г\)
\(\displaystyle \bf Д\)
Сумма степеней

 

Граф содержит  рёбер.

Сумма степеней вершин больше количества рёбер в раз(а).

Решение

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

Определение

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

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

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

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

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

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

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

Сумма степеней вершин:

\(\displaystyle 2+4+2+3+3=\color{red}{\bf 14}{\small.}\)

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

ВершинаСтепень вершины
\(\displaystyle \bf А\)\(\displaystyle 2\)
\(\displaystyle \bf Б\)\(\displaystyle 4\)
\(\displaystyle \bf В\)\(\displaystyle 2\)
\(\displaystyle \bf Г\)\(\displaystyle 3\)
\(\displaystyle \bf Д\)\(\displaystyle 3\)
Сумма степеней\(\displaystyle \color{red}{\bf 14}\)

 

Шаг 2. Определим количество рёбер графа.

Граф содержит \(\displaystyle \color{green}{\bf7}\) рёбер.

Шаг 3. Вычислим, во сколько раз сумма степеней вершин больше количества рёбер.

\(\displaystyle \frac{\color{red}{\bf 14}}{\color{green}{\bf7}}=2{\small.}\)

Таким образом, сумма степеней вершин графа больше количества его рёбер в \(\displaystyle 2\) раза.

 

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

Заметим, что каждое ребро графа имеет начало и конец. Значит, при подсчёте степеней вершин каждое ребро подсчитано дважды: для вершины, являющейся началом ребра, и для вершины, являющейся его концом.

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

Правило

Теорема

Сумма степеней всех вершин графа равна удвоенному количеству рёбер.