Готовая презентация · 9 слайдов

Степень вершины графа

Граф состоит из вершин и рёбер Вершины — объекты Рёбра — связи между объектами вершина — объект ребро — связь

Смотреть слайды

Готовая презентация

9 слайдов · PDF и PowerPoint

Скачать PDF Скачать PowerPoint

Бесплатно после входа.

Собрать свою презентацию по этой теме →

В этой презентации

Слайд 2Что такое степень вершины?Слайд 3Считаем степень по рисунку Слайд 9Главное за урок

Слайды и пояснения

Показать план

План презентации

1. Степень вершины графа

Подсказка для выступления

Объясни, что граф — это модель связей: вершины изображают объекты, рёбра — связи между ними. Например, вершины могут изображать города, а рёбра — дороги.

2. Что такое степень вершины?

Степень вершины — это количество рёбер, которые с ней соединены. Обозначение: deg(v) выделенная вершина — v степень — deg(v)=4

Подсказка для выступления

Подчеркни: считаем именно рёбра, которые подходят к вершине. Неважно, под каким углом они нарисованы и насколько длинны.

3. Считаем степень по рисунку

Пример У вершины A — 3 ребра У вершины B — 1 ребро У вершины C — 0 рёбер deg(A)=3, deg(B)=1, deg(C)=0 вершина — A вершина — B вершина — C

Подсказка для выступления

Разбери пример вслух: у вершины A три соседних вершины, значит степень A равна 3. У B одно ребро, степень 1. У C нет рёбер, степень 0.

4. Степень и соседи

Степень показывает число соседей Если вершина соединена с четырьмя другими вершинами, её степень равна 4. центральная вершина — deg(v)=4 соседи — 4

Подсказка для выступления

Объясни, что сосед вершины — это вершина, соединённая с ней ребром. В простом графе каждое ребро между двумя вершинами добавляет по одной единице к степени каждой из них.

5. Важное свойство графа

Сумма степеней всех вершин равна удвоенному числу рёбер: ∑ deg(v) = 2|E| Это свойство называют леммой о рукопожатиях. рёбра — 4 сумма степеней — 8 связь — 8=2·4

Подсказка для выступления

Сформулируй правило: каждое ребро имеет два конца и поэтому учитывается в степенях дважды. На рисунке можно посчитать степени: 3+2+2+1=8, а рёбер 4, значит 2·4=8.

6. Задание 1

Попробуй сам На рисунке найди степень каждой вершины. Затем проверь: чему равна сумма степеней? вершины — A, B, C, D

Подсказка для выступления

Попроси зрителей сначала решить самостоятельно. Ответ: степени вершин равны 2, 3, 2 и 1; сумма равна 8, поэтому число рёбер — 4.

7. Применяем формулу

Задание 2 В графе 6 рёбер. Чему равна сумма степеней всех его вершин? ∑ deg(v) = ? число рёбер — |E|=6 сумма степеней — ?

Подсказка для выступления

Ответ: сумма степеней равна 2·6=12. Одно возможное распределение степеней зависит от рисунка; важно применить формулу к указанному числу рёбер.

8. Проверяем возможность

Можно ли построить граф со степенями вершин: 1, 2, 2, 3? Подсказка: сумма степеней должна быть чётной. степени — 1, 2, 2, 3 сумма — 8

Подсказка для выступления

Попроси найти ошибку. Сумма степеней 1+2+2+3=8 — чётное число, поэтому такой набор не противоречит лемме о рукопожатиях. Но существование конкретного графа нужно проверять отдельно; например, четыре вершины со степенями 1,2,2,3 реализуются графом с рёбрами AB, AC, AD, BC.

9. Главное за урок

Запомни • Степень вершины — число связанных с ней рёбер. • Изолированная вершина имеет степень 0. • Сумма степеней равна 2|E|. • Сумма степеней всегда чётна. степень — число рёбер формула — ∑deg(v)=2|E|

Подсказка для выступления

Подведи итог: степень — число рёбер у вершины; изолированная вершина имеет степень 0; сумма степеней равна удвоенному числу рёбер и потому всегда чётна. Предложи проверить себя на новом небольшом графе.