Дан связный граф на n вершинах, у которого степень любой вершины равна 1010. Доказать, что при удалении меньше чем 1010 ребер, граф не потеряет связности.

задан 7 Авг 2:08

n - некое определенное число, которое я не помню(но вроде 2020). но по моей логике оно и не играет роли.

Ведь, если граф связный и степень любой вершины 1010, то, если даже удалить 1009 смежных определенной вершине ребер, все равно одно останется, значит граф не распадется на компоненты. А если удалить 1010 исходящих из одной вершины ребер, то ясно, что граф потеряет связность. Это достаточное доказательство?

(7 Авг 2:17) classman
1

n - некое определенное число, которое я не помню(но вроде 2020). но по моей логике оно и не играет роли
Возьмите 2 полных графа с 1011 вершинами, удалите в каждом по ребру и соедините их между собой двумя ребрами (соединив вершины в которых удалили ребро). Получим граф с 2022 вершинами, степень каждой будет равна 1010, но удалив всего 2 ребра можно сделать несвязным.
В этом примере и подсказка к решению. Думайте!

(7 Авг 9:14) spades

@spades сразу понятно, что число вершин играет роль, спасибо Но не особо понятно при каком n можно гарантировать связность после удаления 1009 ребер.

(7 Авг 11:55) classman
1

для 2020. Возьмем связную компоненту после удаления ребер с наименьшим количеством вершин. Пусть этих вершин k <= 1010. Вернём удаленные ребра внутри этой компоненты, связность общего графа при этом не изменится. Сумма степеней вершин этой компоненты не превысит k * (k-1). Будем теперь добавлять ребра до исходного состояния. Так как добавление одного ребра приводит к изменению этой суммы не более чем на один, а изначально она была равна k * 1010, то удалено не менее k * (1010-k+1) >= 1010 ребер

(7 Авг 13:00) spades

@classman: желательно точное условие, чтобы не надо было угадывать, о чём хотели спросить.

(7 Авг 13:17) falcao

@falcao, мое решение проходит для любого n<=2021. Для n= 2022 привел контрпример.

(7 Авг 13:21) spades

@spades: я писал свой комментарий, когда ещё не увидел Вашего. Но я пока не понимаю, как там получается 2022.

(7 Авг 13:30) falcao

@falcao, контрпример во втором посте. Или к нему есть вопросы?

(7 Авг 13:33) spades

@spades: да, этот пример понятен, но мне пока не до конца ясно второе рассуждение. Где там получается 2020, а также что будет для 2021 вершины?

(7 Авг 13:37) falcao

@falcao, допустим, что после удаления ребер получится несвязный граф. При n<=2021 в связной наименьшей компоненте будет не больше 1010 вершин

(7 Авг 13:42) spades
1

@falcao, и да, доказательство приведено для простого графа. С петлями или кратными ребрами можно привести контрпример почти для любого количества вершин.

(7 Авг 13:54) spades

@spades: да, теперь понятно. Я упустил из виду начальное соображение, что при небольшом количестве вершин, есть небольшая связная компонента. Граф, конечно, рассматривается простой.

(7 Авг 14:13) falcao
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×477

задан
7 Авг 2:08

показан
57 раз

обновлен
7 Авг 14:13

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

по почте:

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

по RSS:

Ответы

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

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