Графы: точки и линии

Главное

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

Правила

1. Сумма степеней = 2 · число рёбер
2. Вершин нечётной степени — чётное количество
3. Обход «одним росчерком» — если нечётных вершин 0 или 2
4. Рисуй граф, чтобы увидеть структуру задачи

Разберём пример

В классе 25 человек. Может ли у каждого быть ровно 5 друзей в классе?

Нельзя

Частые ошибки

• Считать рёбра по одному разу для каждой вершины — каждое ребро учитывается дважды.
• Путать вершины и рёбра.

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.