В связном графе на n вершинах нет мостов. Какое наименьшее количество рёбер может быть в таком графе?

Если в данном графе нет мостов, тогда нет и вершин степени 1, т.к. ребро, соединяющее такую вершину с другой будет являться мостом. Тогда степень каждой вершины хотя бы 2 ⇒ $ \sum_{i=1}^{n}{deg(v_i)} $ ≥ 2 · n.
С другой стороны $ \sum_{i=1}^{n}{deg(v_i)} $ = 2|E| ⇒ 2|E| ≥ 2n ⇒ |E| ≥ n
Пример: цикл длины n, где степень каждой вершины 2.


info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp