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

[gogoshik]

Помогите, плиз, разобраться.

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

[mihaild]

Можете выписать определения компоненты связности и связного графа?

[gogoshik]

Определение $1$. Граф называется связным, если любые две его вершины можно соединить путем.

Определение $2$. Компонента связности графа -- некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

Определение $2^*$. Компонентой связности называется класс эквивалентности относительно связности.

Определение $2^*^*$. Рассмотрим подграфы $G_i(V_i, E_i)$ графа $G$, порожденные множествами $V_i$ , т.е. для $u, v \in V_i $ выполняется $\left\lbrace u, v \right\rbrace \in E_i \Leftrightarrow \left\lbrace u, v \right\rbrace \in E$. Так как любые две вершины из $V_i $ связаны путем в $G$, то этот путь будет связывать их и в $G_i$. Следовательно, $G_i$ -- связный граф. Нетрудно проверить, что множества $E_i $ образуют разбиение множества $E$ (возможен случай $E_i = \varnothing$ для некоторых $i$, в этом случае $G_i(V_i, E_i)$ -- тривиальный) и для графа $G$ будет выполняться $G(V, E) = G_1(V_1, E_1) \sqcup . . . \sqcup G_k(V_k, E_k)$ -- дизъюнктное объединение графов $G_1(V_1, E_1), . . . , G_k(V_k, E_k)$. При этом подграфы $G_1, . . . , G_k$ называются компонентами связности графа $G$.

-- 26.07.2018, 20:03 --

Перечитал много раз и понял, что у данного графа будет одна компонента связности. Правильно?

Почему то сначала мне захотелось разбить граф на подмножества попарных вершин и соответствующих ребер. Получилось три ребра и три отдельные вершины. Я это принял за компоненты.

[Sender]

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

Перечитал много раз и понял, что у данного графа будет одна компонента связности. Правильно?

Да.

[gogoshik]

Спасибо. Правильно понимаю, что у любого связного графа (в смысле определения 1) будет всего одна компонента связности? И эта компонента содержит все связанные вершины такого графа без одного ребра. Или что-то опять не так?

[Sender]

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

Правильно понимаю, что у любого связного графа (в смысле определения 1) будет всего одна компонента связности?

Да.

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

И эта компонента содержит все связанные вершины такого графа без одного ребра.

Не вполне улавливаю смысл данного утверждения. Компонента связности (в смысле приведённого определения 2) связного графа содержит ровно все его вершины, только и всего.

[iifat]

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

все связанные вершины такого графа без одного ребра

... из которого сделали Еву?
Согласно Википедии и моим смутным воспоминаниям, компонента связности — подграф, то бишь подмножество вершин и рёбер исходного графа — далее по тексту. А вы по какому источнику изучаете вопрос?

[gogoshik]

iifat в сообщении #1329072 писал(а):

Согласно Википедии и моим смутным воспоминаниям, компонента связности — подграф, то бишь подмножество вершин и рёбер исходного графа — далее по тексту. А вы по какому источнику изучаете вопрос?

Sender в сообщении #1329068 писал(а):

Не вполне улавливаю смысл данного утверждения. Компонента связности (в смысле приведённого определения 2) связного графа содержит ровно все его вершины, только и всего.

В моем источнике есть задача, в которой используется понятие компоненты, хотя определения в самом источнике нет. Поэтому использую google.

Вот именно это определение (определение $2$) меня запутывает. Все таки это подмножество вершин графа или подмножество вершин и ребер, которые связывают эти вершины. В первом случае действительно никакие ребра не учитываются, а во втором (и в смысле определения $2^*^*$ и такого), как будет выглядеть компонента (подграф) исходного графа $K_3$ -- треугольника? На рисунке по видимому компонента связности такого графа будет изображена как три вершины и два любых ребра их соединяющие, то есть одно ребро (произвольное) можно выкинуть.

[Munin]

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

В моем источнике

Так назовите его. Зачем секретничать?

[gogoshik]

А.Б. Скопенков. Алгебраическая топология с геометрической точки зрения.

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

[iifat]

Уточняю: компонентой связности называется максимальный связный подграф.

[gogoshik]

Очень требуется помощь в одном вопросе. Помогите, плиз.

Получил некоторую оценку числа компонент связности графа, которую пытаюсь доказать.

Нужно доказать, что для графа с $k$ ребрами число компонент связности (обозначим, как $s$) $s \leqslant (k/2) +1$.

[kotenok gav]

Любое ребро соединяет ровно две вершины. Дальше думайте сами.

[Andrey_Kireew]

Может быть $k=s$. Вот Вам пример:

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

[vpb]

kotenok gav в сообщении #1331912 писал(а):

Любое ребро соединяет ровно две вершины. Дальше думайте сами

Гм. Вообще говоря, когда есть несколько вершин, а ребер вообще нет --- это, мой юный друг, тоже таки граф (называемый дискретным графом, или кокликой.)