Сколько вершин содержится в графе, в котором имеются 13 рёбер и отсутствуют циклы, но можно добавить ещё 15 рёбер

  • 41
Сколько вершин содержится в графе, в котором имеются 13 рёбер и отсутствуют циклы, но можно добавить ещё 15 рёбер, чтобы он стал связным без появления циклов?
Iskander
3
Чтобы решить эту задачу, важно понять, как связаны количество рёбер и вершин в графе.

Пусть в графе имеется \(n\) вершин. Если граф является деревом (то есть связным графом без циклов), то каждое дерево с \(n\) вершинами имеет \(n-1\) рёбер.

В данной задаче граф содержит 13 рёбер и отсутствуют циклы. Чтобы он стал связным, необходимо добавить ещё 15 рёбер. Это значит, что в конечном результате граф будет содержать \(13+15 = 28\) рёбер.

Воспользуемся формулой для деревьев: \(n-1 = 28\). Решаем уравнение относительно \(n\):

\[n = 28+1 = 29.\]

Таким образом, в результирующем графе будет 29 вершин.