5. Связный граф В, не содержащий циклов, получен из графа А удалением шести рёбер. Число вершин у графов В и А одинаково. Найдите количество вершин в графе В, если в графе А ровно 18 рёбер.

Решение:

Граф В является связным и не содержит циклов. Это означает, что граф В является деревом.

Для любого дерева верно соотношение:

m = n - 1

где:

• m — количество рёбер в дереве;
• n — количество вершин в дереве.

Из условия задачи, граф В получен из графа А удалением шести рёбер. В графе А было 18 рёбер.

Количество рёбер в графе В:

m_B = m_A - 6 = 18 - 6 = 12

Поскольку граф В является деревом, количество вершин в нём (n_B) связано с количеством рёбер (m_B) соотношением:

m_B = n_B - 1

12 = n_B - 1

n_B = 12 + 1 = 13

Число вершин у графов А и В одинаково, поэтому количество вершин в графе А также равно 13. Проверим это:

m_A = n_A - 1

18 = 13 - 1 = 12

Это противоречие. Следовательно, граф В является не просто деревом, а лесом, состоящим из нескольких компонент связности, одна из которых является деревом. Или же условие про "связный граф В" означает, что сам граф В, полученный удалением рёбер, остался связным, но при этом мог стать деревом.

Перечитаем условие: "Связный граф В, не содержащий циклов, получен из графа А удалением шести рёбер. Число вершин у графов В и А одинаково."

Если граф В связный и не содержит циклов, то он является деревом. В этом случае:

m_B = n_B - 1

Граф А имеет 18 рёбер. Число вершин у графов А и В одинаково, обозначим его n.

В графе В: m_B = n - 1

Граф В получен из А удалением 6 рёбер, значит:

m_B = m_A - 6 = 18 - 6 = 12

Теперь подставляем в формулу для дерева:

12 = n - 1

n = 13

Таким образом, количество вершин в графе А (и, следовательно, в графе В) равно 13.

Ответ: 13