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

[Someone]

gogoshik в сообщении #1332217 писал(а):

В итоге я получаю конструкцию, изображенную на этом рисунке by Andrey_Kireew. И тогда получается, что мне нужно доказать, что для мультиграфа у которого число вершин равно числу ребер $(k)$, число компонент связности не превосходит $(k/2) + 1$.

Вы собираетесь доказывать заведомо неверное утверждение. Контрпример Вам показал Andrey_Kireew. В его графе $18$ вершин, $18$ рёбер и $11$ компонент связности, а $11>\frac{18}2+1$. Для мультиграфов это тем более неверно, поскольку ничто не мешает взять $1000$ вершин, две из них соединить тысячей рёбер и получить $999$ компонент связности. А если разрешить петли, то можно получить и $1000$ компонент.

Возможно, Вы потеряли какое-то условие. Я что-то не помню, чтобы Вы приводили точную формулировку задачи.

[gogoshik]

Someone, спасибо за замечание. Ну, тогда я не могу добиться чего-то хорошего. Я не знаю как это правильно сформулировать. То есть то, что у меня конструируются в результате объекты подобные изображенному на рисунке.

[arseniiv]

Да вы просто приведите точную цитату из книги, включающую формулировку задачи целиком (если она из неё). А то действительно интересно, что с ней не так. Самостоятельно вы формулировку наверняка не исправите.

[gogoshik]

arseniiv, дело в том, что в книге задача включена в тему "Планарность дисков с ленточками". Автор развивает подход, что некоторые топологические вопросы можно переформулировать в терминах теории графов. Предварительно идет задача в которой требуется построить граф, отвечающий определенным условиям на конфигурацию объекта под названием "диск с ленточками". После такого построения (которое я уже, как думаю, правильно выполнил) необходимо выполнить доказательство оценки числа "краевых окружностей диска с ленточками", которое эквивалентно в терминах теории графов тому, что я сейчас пытаюсь сформулировать (доказать).

[Munin]

gogoshik в сообщении #1332287 писал(а):

которое эквивалентно в терминах теории графов тому, что я сейчас пытаюсь сформулировать

Видимо, всё-таки не эквивалентно.

[DeBill]

Пример Andrey_Kireew приводит к точной оценке на число компонент связности:
В полном графе на $n$ вершинах имеется $k=\frac{n(n-1)}{2}$ ребер. Добавив $k-n$ изолированных вершин, получим , что число компонент связности не превышает $k-n+1$, где $n$ определяется по $k$ указанной выше формулой (ну, целую часть надо навесить...)

[gogoshik]

Munin в сообщении #1332290 писал(а):

Видимо, всё-таки не эквивалентно.

Ну, не знаю. У меня получилась такая конструкция. Пусть нам дан "диск". Его "краевая окружность" -- это $S^1$. Край ленточки -- это прямоугольник со сторонами $a = c$ и $b = d$ (пусть $a < b$). Пусть вершины этого прямоугольника -- это точки $x, y, z, w$. Причем сторонам $a, c$ соответствуют отрезки $[x, y], [z, w]$. Приклеим ленточку к диску сторонами $a, c$. Получим "диск с ленточкой" с двумя "краевыми окружностями" -- внешней и внутренней. Внешняя "краевая окружность" ограничена двумя кривыми, которые не пересекаются и соединяют точки (вершины) $x, w$. Внутренняя "краевая окружность" ограничена двумя кривыми между точками (вершинами) $y, z$. Таким образом диск с одной ленточкой, имеющий две краевые окружности эквивалентен мультиграфу с двумя компонентами связности, где в каждой компоненте ровно 2 вершины и 2 ребра. То есть диск (имеющий одну краевую окружность) эквивалентен связному (число компонент связности $s=1$) мультиграфу с 2 вершинами и 2 ребрами. Диск с одной ленточкой, имеющий две краевые окружности эквивалентен несвязному мультиграфу $(s=2)$, где каждая компонента содержит ровно 2 вершины и 2 ребра.

Ну, и теперь требуется доказать, что число краевых окружностей (равных числу компонент связности мультиграфа) диска с $n$ ленточками не превосходит $(n+1)$. Это, как думаю, должно быть эквивалентно тому, что в мультиграфе $s \leqslant (...)+1$.

[gogoshik]

gogoshik в сообщении #1332348 писал(а):

Munin в сообщении #1332290 писал(а):

Видимо, всё-таки не эквивалентно.

Ну, не знаю. У меня получилась такая конструкция. Пусть нам дан "диск". Его "краевая окружность" -- это $S^1$. Край ленточки -- это прямоугольник со сторонами $a = c$ и $b = d$ (пусть $a < b$). Пусть вершины этого прямоугольника -- это точки $x, y, z, w$. Причем сторонам $a, c$ соответствуют отрезки $[x, y], [z, w]$. Приклеим ленточку к диску сторонами $a, c$. Получим "диск с ленточкой" с двумя "краевыми окружностями" -- внешней и внутренней. Внешняя "краевая окружность" ограничена двумя кривыми, которые не пересекаются и соединяют точки (вершины) $x, w$. Внутренняя "краевая окружность" ограничена двумя кривыми между точками (вершинами) $y, z$. Таким образом диск с одной ленточкой, имеющий две краевые окружности эквивалентен мультиграфу с двумя компонентами связности, где в каждой компоненте ровно 2 вершины и 2 ребра. То есть диск (имеющий одну краевую окружность) эквивалентен связному (число компонент связности $s=1$) мультиграфу с 2 вершинами и 2 ребрами. Диск с одной ленточкой, имеющий две краевые окружности эквивалентен несвязному мультиграфу $(s=2)$, где каждая компонента содержит ровно 2 вершины и 2 ребра.

Ну, и теперь требуется доказать, что число краевых окружностей (равных числу компонент связности мультиграфа) диска с $n$ ленточками не превосходит $(n+1)$. Это, как думаю, должно быть эквивалентно тому, что в мультиграфе $s \leqslant (...)+1$.

Возникла такая идея. Диск с одной ленточкой, имеющий две краевые окружности эквивалентен несвязному мультиграфу $(s=2)$, где каждая компонента содержит ровно 2 вершины и 2 ребра. К каждой компоненте связности применим операцию стягивания ребра. Данная операция не изменяет число компонент связности. Стянем одно ребро в каждой компоненте. Получим мультиграф с двумя компонентами связности, где каждая компонента будет содержать ровно одну вершину и одно ребро, т.е. вершину с петлёй. В таком случае диск с $n$ ленточками будет эквивалентен такому мультиграфу с количеством вершин (ребер) равным $v = n + 1$. И нам нужно показать, что в мультиграфе число компонент связности $s \leqslant n+1 = v-1+1 = v$. Очевидно, что если $s > v$, то такого не может быть.

Будет ли это доказательством?