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

[Aritaborian]

Andrey_Kireew, вас переклинило сильнее, чем вам кажется. Если добавить в нарисованный вами куб новое ребро, соединяющее уже имеющиеся в нём вершины, количество компонент связности от этого не увеличится.

[kotenok gav]

Не увеличится, но мы будем вынуждены добавить веришну, чтобы удлевотворить требования gogoshik.

[Someone]

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

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

Это просто другое понятие. Знаете, бывают натуральные числа, и бывают целые числа. Не надо спрашивать , "что будет не так с числом $-1$", это просто не натуральное число. Точно так же мультиграф не обязан быть графом. Обсуждаемый конкретный мультиграф — не граф.

[Andrey_Kireew]

Aritaborian в сообщении #1332153 писал(а):

Andrey_Kireew, вас переклинило сильнее, чем вам кажется ...

художника обидеть может каждый ...

[Aritaborian]

Я тут немного полистал литературу... И при всём огромном уважении к вам, Someone, таки дезавуирую своё заявление о том, что мультиграф — не граф. Всё-таки «граф» это umbrella term, и графами могут называться и мультиграфы, и гиперграфы.

[gogoshik]

Ну, видимо переклинило меня. У меня почему то не получается доказательство. Подсказка kotenok gav в моем случае выглядит, как "две вершины являются концами как минимум одного ребра". Казалось бы дискретный объект, должно быть все просто. А столько путаницы с этими "графами", какая то тёмная область .

[Someone]

Aritaborian в сообщении #1332165 писал(а):

графами могут называться и мультиграфы, и гиперграфы.

Но это должно оговариваться.

[Aritaborian]

Andrey_Kireew в сообщении #1332163 писал(а):

художника обидеть может каждый ...

Вот бы вы ещё не так криво всё это рисовали... Чем вы вообще пользуетесь? MS Paint, что ли, прастихоспади?
Вот, учитесь.

[Andrey_Kireew]

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

[Aritaborian]

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

Казалось бы дискретный объект, должно быть все просто.

Фигассе себе заявленьице. То есть, вы на самом деле считаете, что дискретная математика — предмет исследования, являющийся более лёгким, чем анализ?

[Grom Hellscream]

Aritaborian в сообщении #1332181 писал(а):

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

Казалось бы дискретный объект, должно быть все просто.

Фигассе себе заявленьице. То есть, вы на самом деле считаете, что дискретная математика — предмет исследования, являющийся более лёгким, чем анализ?

А что, непрерывное это только анализ? И что вообще такое дискретная математика?

[Someone]

Grom Hellscream в сообщении #1332182 писал(а):

И что вообще такое дискретная математика?

Это "административное" понятие, аналогичное понятию "высшая математика". Надёргали фрагментов из различных областей математики (включая топологию!) и обозвали "дискретной математикой".

gogoshik, мне, конечно, очень интересно, каким образом из

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

Любое ребро соединяет ровно две вершины

можно получить

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

две вершины являются концами как минимум одного ребра

Вообще, тут уже явно начинается очередная терминологическая война. gogoshik, Вы не могли бы сформулировать определение графа из той книги, которой Вы пользуетесь?

[gogoshik]

Someone в сообщении #1332192 писал(а):

Вообще, тут уже явно начинается очередная терминологическая война. gogoshik, Вы не могли бы сформулировать определение графа из той книги, которой Вы пользуетесь?

Цитата:

Графом без петель и кратных ребер называется конечное множество $V$ вместе с набором $E$ двухэлементных подмножеств (т.е. неупорядоченных пар) множества $V$. Элементы данного множества $V$ называются вершинами. Элементы набора $E$ называются ребрами. Вершина $v$ является концом ребра $e$ если $v \in e$.

Далее автор отмечает:

Цитата:

В большей части данного текста можно пользоваться понятием графа без петель и кратных ребер. Однако все написанное справедливо для следующего обобщения, которое кое-где даже необходимо. Графом (с петлями и кратными ребрами) (или мультиграфом) называется квадратная таблица $E$ размера $V \times V$ из целых неотрицательных чисел, симметричная относительно главной диагонали. Элемент $k$ таблицы называется ребром (или петлей) кратности $k$, если соответствует паре различных (или совпадающих) вершин.

Думаю, что мне в задаче как раз и необходимо использовать понятие мультиграфа. Задача (в моей интерпретации) предполагает, что её решение будет эквивалентно решению задачи, поставленной автором в её "чистом" виде.

[Someone]

gogoshik, спасибо.

[gogoshik]

Andrey_Kireew в сообщении #1331928 писал(а):

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