Question

В графе 13 рёбер и нет циклов. Известно, что в граф можно добавить ещё 15 рёбер так, что он станет связным, но при этом в нём не появится циклов. Сколько вершин в графе?

Answer 1

Ответ:

Ответ здесь не такой будет. Пусть n>1. Рассмотрим несвязный граф, в котором одна вершина ни с чем не соединена, а остальные соединены попарно. Тогда в графе (n−1)(n−2)/2 рёбер, и он не связен. Если количество рёбер увеличить на единицу, то их получится (n−1)(n−2)/2+1, и здесь уже связность графа гарантирована. Действительно, если компонент связности как минимум две, и одна из них содержит k вершин, где 1<k<n, то количество отсутствующих рёбер не меньше k(n−k). Эта величина не меньше n−1 ввиду неравенства kn−k2−n+1=(k−1)(n−(k+1))≥0, а у нас отсутствует меньше рёбер.

Пошаговое объяснение:

Надеюсь помог

Answer 2

Давайте рассмотрим данную задачу более подробно.

У нас есть граф с 13 рёбрами, и в нем нет циклов. Это означает, что данный граф является лесом (несвязным графом без циклов). Чтобы сделать его связным, нам нужно добавить достаточное количество рёбер, чтобы объединить все компоненты связности в один граф.

Поскольку в лесу без циклов каждая компонента связности представляет собой дерево, то количество вершин в каждой компоненте связности (т.е., размер каждого дерева) равно количеству вершин минус 1. Таким образом, мы можем записать следующее уравнение:

Количество вершин - 1 = Количество рёбер в каждой компоненте связности

В нашем случае у нас есть 13 рёбер, и мы хотим добавить ещё 15 рёбер, чтобы сделать граф связным. Поскольку у нас есть только одна компонента связности, мы можем записать следующее:

Количество вершин - 1 = 13 + 15

Теперь мы можем решить это уравнение:

Количество вершин - 1 = 28

Количество вершин = 28 + 1 = 29

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