2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Число компонент связности
Сообщение12.08.2018, 12:46 


07/10/15

2400
А вот пример для $s>k$
Изображение

те же самые 3 ребра, но уже 4 компоненты связности.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 13:03 


11/12/16
403
сБп
gogoshik в сообщении #1331909 писал(а):
Очень требуется помощь в одном вопросе. Помогите, плиз.

Получил некоторую оценку числа компонент связности графа, которую пытаюсь доказать.

Нужно доказать, что для графа с $k$ ребрами число компонент связности (обозначим, как $s$) $s \leqslant (k/2) +1$.
Прошу прощения за неточность.
Нужно доказать, что для графа с числом вершин равным числу ребер $k$, число компонент связности (обозначим, как $s$) $s \leqslant (k/2) +1$.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 13:10 


21/05/16
4292
Аделаида
Используйте мою подсказку.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 13:52 


07/10/15

2400
Вот граф, соответствующий Вашим условиям:

Изображение

у него $s>(k/2)+1$

Появление новых условий, после предъявления очередного контрпримера, равносильно просьбе нового доказательства.
Вы уж сначала определитесь с вопросом, а потом спрашивайте.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 13:57 


21/05/16
4292
Аделаида
Мы с gogoshik имели ввиду, что между двумя вершинами не больше одного ребра.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 14:01 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Andrey_Kireew в сообщении #1331928 писал(а):
Вот граф, соответствующий Вашим условиям
Это, уж звиняйте, не просто граф, а мультиграф. В приличном обществе подобное всегда оговаривают особо.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 14:08 


07/10/15

2400
Да Aritaborian оговаривают, причём, перед тем как пытаются что то доказать, а не поле того, как выясняется, что это доказать в рамках поставленных условий невозможно. Конечно, если речь здесь идёт о математическом доказательстве, в его стогом понимании.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 14:13 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Andrey_Kireew, вы меня не поняли. Когда говорят «граф», имеют в виду просто граф. А специально оговаривают именно тогда, когда речь идёт о мультиграфе.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 14:47 


07/10/15

2400
Ну да. А, этот граф наверное то же чем то "неправильный"?
Изображение

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 19:27 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Граф как граф. Каждая пара вершин соединена не более, чем одним ребром. Всё соответствует определению.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение12.08.2018, 21:48 


07/10/15

2400
однако у него $s=11$, $k/2+1=18/2+1=10$ и $s>k/2+1$.

То, что пытается доказать ТС, можно гарантировать только при условии, что любая компонента связности содержит не более 5 вершин. Но такая оговорка делает это правило уж слишком специфичным.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение13.08.2018, 01:12 


11/12/16
403
сБп
Andrey_Kireew в сообщении #1331928 писал(а):
Вот граф, соответствующий Вашим условиям:

Изображение

у него $s>(k/2)+1$

Появление новых условий, после предъявления очередного контрпримера, равносильно просьбе нового доказательства.
Вы уж сначала определитесь с вопросом, а потом спрашивайте.
Видимо чего то я сильно не понимаю. По моему здесь число компонент связности равно 3.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение13.08.2018, 01:39 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
gogoshik в сообщении #1332081 писал(а):
Видимо чего то я сильно не понимаю.
Это не граф, а мультиграф. Несколько выше это написано.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение13.08.2018, 02:07 


07/10/15

2400
gogoshik всё верно, это у меня что то «переклинило», в этом случае, действительно, Ваше неравенство выполняется.
Это неудачный пример, к тому же, это ещё и мультиграф, как тут справедливо отметили.

Лучше посмотрите на последнюю картинку с кубом, она полностью опровергает Ваше неравенство. И заметьте, рёбер в этот куб можно добавить ещё немало ... А каждое новое ребро - это новая точка, и соответственно - ещё одна компонента связности.

 Профиль  
                  
 
 Re: Число компонент связности
Сообщение13.08.2018, 11:08 


11/12/16
403
сБп
А что будет не так в случае мультиграфа, он уже считается патологическим?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 53 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: tolstopuz


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group