Контрольные задания > 3. Граф, не содержащий ни одной замкнутой ломаной, называется лесом. Пусть лес состоит из трех деревьев и имеет B вершин и P ребер. Чему равно B – P?
Вопрос:
3. Граф, не содержащий ни одной замкнутой ломаной, называется лесом. Пусть лес состоит из трех деревьев и имеет B вершин и P ребер. Чему равно B – P?
Ответ:
Для одного дерева выполняется соотношение: \(B = P + 1\), где \(B\) - число вершин, \(P\) - число ребер.
Так как лес состоит из трех деревьев, то для каждого дерева выполняется это соотношение:
Дерево 1: \(B_1 = P_1 + 1\)
Дерево 2: \(B_2 = P_2 + 1\)
Дерево 3: \(B_3 = P_3 + 1\)
Сложим эти уравнения:
\[B_1 + B_2 + B_3 = P_1 + P_2 + P_3 + 3\]
Пусть \(B = B_1 + B_2 + B_3\) и \(P = P_1 + P_2 + P_3\), тогда:
\[B = P + 3\]
Отсюда:
\[B - P = 3\]
Ответ: 3