Чему равна минимальная число ребер в графе на 12 вершинах с тремя компонентами связоности

задан 25 Май '17 15:19

@Spl35: минимальное число ребер ... с тремя компонентами связности

(25 Май '17 17:07) falcao
10|600 символов нужно символов осталось
0

Минимальное число ребер связного графа на 1 меньше числа его вершин. Значит, ответ 9.

ссылка

отвечен 25 Май '17 16:22

Можно пожалуйста по подробней

(25 Май '17 17:09) Spl35

@Spl35: если граф связен, то в нём есть поддерево, содержащее все вершины. Количество рёбер дерева на единицу меньше числа его вершин. Если вершин n, то рёбер в связном графе как минимум n-1. Если x,y,z -- число вершин в каждой из компонент связности, то рёбер в графе получается не меньше x-1+y-1+z-1=9. Пример с 9 рёбрами легко строится (например, дерево на 10 вершинах, и две изолированные точки).

(25 Май '17 17:13) falcao

Спасибо большое

(25 Май '17 17:28) Spl35
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,299
×121

задан
25 Май '17 15:19

показан
401 раз

обновлен
25 Май '17 17:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru