Каково минимальное число ребер у графа на 26 вершинах без циклов и изолированных вершин, ровно 5 вершин которого имеют степень равную 1?

задан 4 Фев '18 12:20

10|600 символов нужно символов осталось
1

В условии говорится о дизъюнктном объединении деревьев, каждое из которых имеет более одной вершины. Каждое дерево содержит на единицу меньше рёбер нежели вершин. Общее количество рёбер равно 26-k, где k -- число связных компонент. То есть надо максимизировать k. Поскольку в каждой связной компоненте (неодноточечном дереве) имеется как минимум 2 вершины степени 1, мы имеем k<=2. Если взять дизъюнктное объединение "трилистника" (одна вершина соединена с тремя) и линейного графа на 22 вершинах, то это даст максимальное число связных компонент, равное 2, и минимальное число рёбер, равное 24.

ссылка

отвечен 4 Фев '18 15:52

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×549

задан
4 Фев '18 12:20

показан
385 раз

обновлен
4 Фев '18 15:52

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

по почте:

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

по RSS:

Ответы

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

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