Вопрос школьника
Граф, не содержащий ни одной замкнутой ломаной, называется лесом. Пусть лес состоит из п деревьев и имеет В вершин и Р рёбер. Чему равно В — Р?
Ответ от учителя
Для решения задачи воспользуемся формулой Эйлера для связных графов:
V — E + F = 1,
где V — количество вершин, E — количество ребер, F — количество граней.
Для леса количество граней равно 1 (так как нет замкнутых ломаных, то и граней нет, кроме внешней).
Количество вершин в лесе равно сумме количества вершин в каждом дереве, то есть V = сумма vi, где vi — количество вершин в i-ом дереве.
Количество ребер в лесе равно сумме количества ребер в каждом дереве, то есть E = сумма ei, где ei — количество ребер в i-ом дереве.
Таким образом,
V — E + F = 1
сводится к
сумма vi — сумма ei + 1 = 1
или
сумма vi — сумма ei = 0.
Но сумма vi — сумма ei это количество вершин минус количество ребер, то есть В — Р.
Итак, В — Р = 0,
то есть количество вершин в лесу равно количеству ребер.
