Число компонент связности

[MAKSUS_87]

Здравствуйте.
Как найти число компонент связности может иметь граф, если у него известно число вершин и ребер ?
Спасибо.

[Mihr]

Этой информации совершенно не достаточно.

[ИСН]

Нашёл: три.

[MAKSUS_87]

ИСН

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

[ИСН]

Серьёзно? Максимум - число вершин, минимум - число вершин минус число рёбер, но не меньше одной.

[Mihr]

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

[MAKSUS_87]

ИСН
Ну допустим 10 вершин, 30 ребер, тогда ваше утверждение не верно.

[ИСН]

Моё утверждение верно, только оценка в нём - нестрогая. Вам строгую надо? Вам действительно надо это, а не число километров до Юпитера? Если да, то можно измыслить.

[ratay]

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

[MAKSUS_87]

ИСН

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

[provincialka]

ratay, вас в гугле забанили? Не надо отвлекать человека.

[ИСН]

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

[provincialka]

(to ИСН)

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

[MAKSUS_87]

ИСН

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

[provincialka]

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