Деревья и правило умножения
Граф состоит из вершин и соединяющих их рёбер. Сумма степеней вершин неориентированного графа равна удвоенному числу рёбер. Дерево — связный граф без циклов; у дерева с n вершинами n − 1 рёбер и единственный простой путь между двумя вершинами.
В этом занятии
- Применять правило темы «Деревья и правило умножения» и объяснять проверку ответа.
Разберёмся перед практикой+
Деревья и правило умножения
Граф состоит из вершин и соединяющих их рёбер. Сумма степеней вершин неориентированного графа равна удвоенному числу рёбер. Дерево — связный граф без циклов; у дерева с n вершинами n − 1 рёбер и единственный простой путь между двумя вершинами.
Ребро учитывается у двух концов. Нельзя применять n − 1 к произвольному графу, если не известно, что это дерево.
У графа 6 рёбер. Найди сумму степеней вершин. Каждое ребро имеет два конца. Удвой число рёбер. Ответ: 12.
- Каждое ребро имеет два конца.
- Удвой число рёбер.
Читай и разбирай пример в своём темпе. К практике можно перейти, когда будешь готов.