2014 dxdy logo

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

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


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


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



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


07/10/15
1213
А вот пример для $s>k$
Изображение

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

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


11/12/16
212
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
1834
Аделаида
Используйте мою подсказку.

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


07/10/15
1213
Вот граф, соответствующий Вашим условиям:

Изображение

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

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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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

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


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

Изображение

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

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

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


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

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


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

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

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


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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