2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Число компонент связности
Сообщение19.11.2014, 18:13 
Здравствуйте.
Как найти число компонент связности может иметь граф, если у него известно число вершин и ребер ?
Спасибо.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 18:22 
Аватара пользователя
Этой информации совершенно не достаточно.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 18:25 
Аватара пользователя
Нашёл: три. :lol: :lol:

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 18:27 
ИСН

А если серьезно ?

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 18:30 
Аватара пользователя
Серьёзно? Максимум - число вершин, минимум - число вершин минус число рёбер, но не меньше одной.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 18:39 
Аватара пользователя
MAKSUS_87,
может быть, есть дополнительные условия? Например, если граф плоский (планарный), то Ваш вопрос имеет однозначный ответ. Правда, в этом случае нужно знать ещё число граней плоского графа.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 18:39 
ИСН
Ну допустим 10 вершин, 30 ребер, тогда ваше утверждение не верно.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 19:39 
Аватара пользователя
Моё утверждение верно, только оценка в нём - нестрогая. Вам строгую надо? Вам действительно надо это, а не число километров до Юпитера? Если да, то можно измыслить.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 19:45 
А что такое компонента связности? Связность - это я понимаю. А компонента связности - это отдельный связный кусок? То есть и у дерева, и у цикла по одной компоненте? Растолкуйте. И мне полезно, и вам вреда не будет.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 19:54 
ИСН

Да. Мне нужно при 10 вершинах и 30 ребрах. Подтолкните меня, пожалуйста, на правильную волну.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 20:14 
Аватара пользователя
ratay, вас в гугле забанили? Не надо отвлекать человека.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 20:45 
Аватара пользователя
При 10 вершинах и 30 ребрах у нас компонент связности будет либо одна, либо две. Нижнюю границу я назвал точно: это $\max(\text{В$-$Р},1)$. Верхняя - что-то типа $\text{В}-\left\lceil{\sqrt{2\text{Р}}}\right\rceil$ (это тоже не совсем точно, но уже почти).

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

(to ИСН)

ИСН, вы как-то необычайно конкретны. А где подход? Намек? У меня сеть барахлит, только собралась подсказку сформулировать - а тут такое!

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 21:24 
ИСН

Честно говоря, не понял.

 
 
 
 Re: Число компонент связности
Сообщение19.11.2014, 21:27 
Аватара пользователя
MAKSUS_87. Предположим, вы построили искомый граф с $k$ компонентами связности. Внутри каждой компоненты можете добавить ребер, чтобы она стала полным графом. Общее число ребер графа не уменьшится, то есть будет не менее 30.
Ну, а для полных графов число ребер можно посчитать и посмотреть, сколько их надо взять, чтобы набрать не менее 30 ребер.

 
 
 [ Сообщений: 21 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group