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  След.

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



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

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


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

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