Верно ли утверждение? Сумма… (вероятность и статистика)

№ Сумма степеней вершин графа

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

Решение

Каждое ребро соединяет две вершины, поэтому при подсчёте степеней оно учитывается дважды: по разу для каждого из своих концов.
Значит, сумма степеней всех вершин равна удвоенному числу рёбер.
Пример: граф из двух вершин, соединённых одним ребром. Степени равны и , сумма равна , а рёбер . Утверждение не выполняется.

💡 Почему так

Лемма о рукопожатиях: сумма степеней вершин равна (число рёбер).

Ответ

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

№ Построение графа по степеням вершин

Изобразите граф, у которого 7 вершин и их степени равны 0, 1, 2, 3, 3, 3, 4.

Решение

Сумма степеней: , она чётная, поэтому граф существует. Рёбер будет .
Назовём вершины со степенями .

Вершина степени изолирована, рёбер из неё нет.
Вершину (степень ) соединяем с : рёбра .
Вершинам нужно ещё по ребра. Соединяем их попарно: .
Вершине нужно ещё ребро, вершине тоже . Соединяем их: .
Проверка степеней: — (); — (); — (); — (); — (); — (); — .
Всего рёбер : .

Ответ

Граф с вершинами и рёбрами: . Вершина изолирована. Степени: — ; — по ; — ; — ; — .

№ Элементы графа

На рисунке дан граф, выпишите следующие элементы:
а) какие-нибудь два смежных ребра;
б) все петли;
в) какую-нибудь цепь;
г) какой-нибудь простой цикл.
Является ли граф связным? Является ли граф ориентированным?

Решение

Читаем рёбра графа с рисунка: , , , , , , , . Ещё есть петли у вершин и .
а) Смежные рёбра имеют общую вершину. Рёбра и имеют общую вершину .
б) Петли — рёбра, у которых оба конца в одной вершине. Это петля при вершине и петля при вершине .
в) Цепь — путь, в котором рёбра не повторяются. Например, .
г) Простой цикл — замкнутый путь без повторения вершин. Например, (рёбра , , ).
Связность: от любой вершины можно дойти до любой другой, потому что все вершины соединены с или друг с другом. Граф связный.
Ориентированность: на рёбрах нет стрелок, граф неориентированный.

💡 Почему так

Граф связный, если между любыми двумя вершинами есть путь. Граф ориентированный, если у рёбер есть направление (стрелки).

Ответ

а) и ;
б) петли при вершинах и ;
в) цепь ;
г) цикл .
Граф связный, не ориентированный.

Помогло?

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