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

задан 18 Май '15 15:58

1

Это достаточно очевидный факт, который легко объясняется словами. Мы могли проехать от любого пункта до любого. Какой-то проезд закрыли. И нам говорят: вот тут есть обходной путь в обратную сторону, проезжайте по нему (это дополнительная часть цикла). Понятно, что проехать по-прежнему можно -- разве что это будет дольше.

(18 Май '15 16:37) falcao

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

(18 Май '15 16:43) sleepless_study
1

@sleepless_study: я понял, в чём состоит проблема. Сейчас подробно отвечу.

(18 Май '15 19:19) falcao
10|600 символов нужно символов осталось
1

Один из способов объяснения, если не усложнять ситуацию слишком сильно, может состоять в следующем. У нас в условии имеется некоторое ребро, являющееся частью цикла. Этот цикл можно считать простым, то есть вершины в нём не повторяются. Мы можем ввести такие обозначения для вершин и рёбер этого цикла $%v_1\to v_2\to\cdots\to v_n\to v_1$%. То ребро, которое подвергается удалению, обозначено здесь через $%v_1\to v_2$%. Для него существует путь по рёбрам цикла, идущий также из $%v_1$% в $%v_2$% в обратном направлении. Его можно обозначить в виде $%v_1\to v_n\to v_{n-1}\to\cdots\to v_2$%. Этот путь мы будем называть дополнительным для $%v_1\to v_2$%.

Теперь рассмотрим две произвольные вершины (мульти)графа. Их можно никак не обозначать, а можно считать, что это какие-то $%u'$% и $%u''$%. Поскольку исходный граф связен, в нём имеется некоторый путь из начальной вершины в конечную (то есть из $%u'$% в $%u''$%), состоящий из последовательно проходимых рёбер. Поскольку мы выбирали его произвольно, в нём может оказаться одно или несколько вхождений ребра $%v_1\to v_2$%, которое мы удаляли из графа, а также прохождений этого ребра в обратную сторону: $%v_2\to v_1$%. Теперь преобразуем путь, заменяя в нём каждое из таких вхождений на путь, дополнительный к данному ребру. Для первого случая он был определён, а для второго это будет путь $%v_2\to v_3\to\cdots\to v_n\to v_1$%. После этих замен получится путь, соединяющий те же вершины, то и раньше, целиком лежащий в подграфе, получающемся после удаления ребра.

Можете посмотреть книгу Уилсона "Введение в теорию графов" в качестве образца рассуждений такого рода. Есть и более современный подход, в духе книги Серра "Деревья" (J.-P.Serre, "Trees"). Там предлагается удобная для алгебры концепция, что у каждого ребра $%e$% имеется обратное ребро, обозначаемое $%e^{-1}$%. С геометрической точки зрения это прохождение ребра в обратном направлении. В этих терминах описание процедуры совсем короткое. Цикл имеет вид $%ep$%, где $%e$% -- ребро. Заменяем $%e$% на $%p^{-1}$%, а $%e^{-1}$% на $%p$%.

ссылка

отвечен 18 Май '15 19:38

@falcao, вау, спасибо, что бы я без Вас делала!

(18 Май '15 21:39) sleepless_study
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×398
×142
×135

задан
18 Май '15 15:58

показан
717 раз

обновлен
18 Май '15 21:39

Связанные исследования

Связанные вопросы

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru